All you need to know about deleting keys from B trees

Figure 1: B Tree

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.

Figure 2: B Tree with root, internal nodes and leaf nodes

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.

Figure 3: Delete D
Figure 4: B Tree after deleting D

Case 2

If k is in the node x which is a leaf and x.n == (t-1)
Figure 5: B Tree delete generalization — Case 2

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.

Figure 6: Move G and J
Figure 7: Delete F
Figure 8: B Tree after deleting F

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.

Figure 9: Merging
Figure 10: Delete B
Figure 11: B Tree after deleting B

Case 3

If k is in the node x and x is an internal node (not a leaf)
Figure 12: B Tree delete generalization — Case 3

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.

Figure 13: Delete L and replace M with L
Figure 14: B Tree after deleting M

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.

Figure 15: Delete J and replace G with J
Figure 16: B Tree after deleting G

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.

Figure 17: Merging
Figure 18: Delete C
Figure 19: B Tree after deleting C

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
  2. B Tree - deleting a key - YouTube — https://www.youtube.com/watch?v=fKubKYzwDl0
One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.