# All you need to know about deleting keys from B trees

B tree is a self-balancing search tree (the tree adjusts itself so that all the leaves are at the same depth) and contains multiple nodes which keep data in sorted order. Each node has 2 or more children and consists of multiple keys.

Following are the 5 properties of a B tree.

1. Every node x has the following:

— x.n (Number of keys)

— x.key_i (The keys stored in ascending order)

— x.leaf (Whether x is a leaf or not)

2. Every node x has (x.n + 1) children.

3. The keys x.key_i separate the ranges of keys stored in each sub-tree.

4. All the leaves have the same depth, which is the tree height.

5. Nodes have lower and upper bounds on the number of keys that can be stored. Here we consider a value t>=2, called minimum degree (or branching factor) of the B tree.

— The root must have at least one key.

— Every other node must have at least (t-1) keys and at most (2t-1) keys. Hence, every node will have at least t children and at most 2t children. We say the node is full if it has (2t-1) keys.

So now we have an idea what B trees are, let’s look in to the delete operation, which is much more complicated than insertion. When deleting, you have to make sure that the five B tree properties are preserved. We consider 3 cases when deleting the key k from a B tree.

### Case 1

If k is in the node x which is a leaf and x.n>=t

Here you can straightaway delete k from x.

Let’s delete D from the B tree given in figure 1.

### Case 2

If k is in the node x which is a leaf and x.n == (t-1)

#### Case 2a:

`Find the immediate sibling y of x, the extreme key m of y, the parent p of x and the parent key l of k`
`If y.n >= t:     Move l into x     Move m into p     Delete k from x`

Let’s delete F from the B tree given in figure 1.

#### Case 2b:

`Find the immediate sibling y of x, the extreme key m of y, the parent p of x and the parent key l of k`
`If y.n == t-1:     Merge x and y     Move down l to the new node as the median key     Delete k from the new node`

Let’s delete B from the B tree given in figure 1.

### Case 3

If k is in the node x and x is an internal node (not a leaf)

#### Case 3a:

`Find the child node y that precedes k (the node which is on the left side of k)`
`If y.n >= t:     Find the key k’ in y which is the predecessor of k     Delete k’ recursively. (Here k’ can be another internal node as well. So we have to delete it recursively in the same way)     Replace k with k’ in x`

Let’s delete M from the B tree given in figure 1.

#### Case 3b:

`Find the child node y that precedes k`
`If y.n < t (or y.n == (t-1)):     Find the child node z that follows k (the node which is on the right side of k)     If z.n >= t:          Find k’’ in z which is the successor of k          Delete k’’ recursively          Replace k with k’’ in x`

Let’s delete G from the B tree given in figure 1.

#### Case 3c:

`Find the child node y that precedes k and the child node z that follows k`
`If y.n == (t-1) AND z.n == (t-1):     Merge k and z to y     Free memory of node z     Recursively delete k from y`

Let’s delete C from the B tree given in figure 1.

Hope you all got an idea on how to delete keys from a B tree… :)

### References

1. Introduction to Algorithms (Third Edition) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Livest andClifford Stein