Facebook

Deletion In B-Trees

In order to delete elements from B-Tree we need to ensure that their properties(Refer : http://letslearncs.com/b-trees/ does not get violated.It should remain a binary search tree and number of pointers must be according to the order and keys should be one less than the order in each and every node.

Example

Consider a B-tree of Fig 1.Say we want to delete 2,21,10,3 and 4 step by step from the tree.

Fig 1 : B-Tree

 

Delete 2

  • 2 is present in node b.Deletion of 2 do not violate any property of B-tree,so we delete 2 directly from node b.(Fig 2)

 

Fig 2 : Delete 2

 

Delete 21

  • Deletion of 21 cannot be done directly.It causes node e to underflow so elements are redistributed among c,g and e(Fig 3).
    • 10 remains in c.
    • 12 is stored in g and 13 is stored in e.

 

Fig 3 : Delete 21

 

Delete 10

  • Deletion of 10 again cannot be done directly.It causes node c to underflow which further causes parent node g to combine with f and a and tree shrinks by one level.3,7 and 9 are stored in a,1 in b,4 and 5 in d,8 in h ,12 and 13 in e (Fig 4).
Fig 4 : Delete 10

 

Delete 3

  • Deletion of 3 causes 4 to move in a (Fig 5).
Fig 5 : Delete 3

 

Delete 4

  • Deletion of needs redistribution of the keys in the subtrees of 4; however, nodes b and d do not have enough keys to redistribute without causing an underflow. Thus, nodes b and d are combined together(Fig 6).
Fig 6 : Delete 4
Rate this post

Comments

So empty here ... leave a comment!

Leave a Reply

Your email address will not be published. Required fields are marked *

Sidebar