Step by step instructions for deleting a key from a B-tree. Code: github.com/msa... Sources: 1. Introduction To Algorithms, Third Edition (CLRS) [www.amazon.com...] 2. www.programiz.... LinkedIn: / michael-sambol
yes, but he decreased the height of the tree while deleting 17, improving the tree over all. this was not possible before, because the leaf with 17 in it was bigger (size 4) than 2t-1 (size 3) for a tree with t=2
It is essentially done to decrease steps in the future because we don't really know how many keys there will be before we reach that node(if that has 2 then we will have to do the same operation but making it much more complicated, travelling down a tree is much easier than to go up
do we check this recursive if keys = min_keys for the root node as well? because technically there is nothing to shift, so nothing would change? Also what if that node we need to shift into is even deeper, do we shift then all the siblings' keys and every key in every node that's above? And If resulting node has too many keys we just do median and move up until the property is satisfied?
Excellent vids on b trees, you've come in clutch for pretty much my entire CS degree now haha, from first year all the way to my final now. Appreciate it a tonne. Just one important thing about this algorithm to note to most people reading (I believe it wasn't mentioned in the video but I may be wrong & too lazy to check lol): deletion can only happen with a case 1, every other case really just sets up the b tree in a "neater" format and recursively calls delete until a case 1 is invoked and the desired element can be deleted. Another thing that took me some time to realise - for case 2a and 2b -> you do not replace with simply the left/right most element of the righ/left child but you must traverse and actually find the immediate predecessor/successor to the element you're trying to delete. Anyways, best of luck to everyone on their DSA journeys
We made the assumption in the beginning that we only call delete on a node with t keys. The delete method is recursive and starts at the root. On our way down to delete key 17, we encountered a node with t-1 keys, hence the need for case 3B.
