B-trees in 6 minutes - Deletions
HTML-код
- Опубликовано: 7 сен 2022
- Step by step instructions for deleting a key from a B-tree.
Code: github.com/msambol/dsa/blob/m...
Sources:
1. Introduction To Algorithms, Third Edition (CLRS) [www.amazon.com/Introduction-A...]
2. www.programiz.com/dsa/deletio...
LinkedIn: / michael-sambol
Don't get discouraged. Please keep uploading these!
full steam ahead
in the case 3b can't we just directly delete 17 as it won't break any of the properties of b tree??
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
I watched your whole playlist for B-Trees. They are very helpful. Good job Michael! Wish me good luck for my data management exam on tomorrrow :)
Your B tree and red black tree video I think are the best that I can find on RUclips. Please keep uploading these video. I like your teaching a lot.
Thank you! More coming. Hope the audio was OK, I had some issues in there. I appreciate you watching!
@@MichaelSambol The audio is very clear but I think louder a little bit will be great!
Cool, will make adjustments!
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
thank you MIchael, watched all the playlist, good teaching
The legend and saviour is back 😇
Was looking for review before my final tomorrow, this clears up everything! Thank you!
How’d it go?
@@Learn-jz1sc There was only 1 question on B trees lmao, otherwise well
May you explain graphs? 🙏
I don't get why we care about the parent in the recursion path in 3b. Wouldn't the tree still be perfectly valid?
we would have 6 siblings, but only 4 keys, so it means we have to have 5 keys
Why and what did we do in case 3B? I mean I don't understand the need to merge the two nodes! please help !!!!
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.
@@MichaelSambol The node has four keys and the t = 3 so 3-1 = 2 no?
why do we care about root in 3b ? explain someone pls
ahaa, cuz we would have 6 siblings, but only 4 keys, so it means we have to have 5 keys
Thank you, your code is so clean and clear! Yet, I'm still not clever enough to understand all...
Which part do you have questions on and how can I help ? 🙂
2:20 Bookmark
t=m/2
where maximum nodes can be m-1
So for m=5 max nodes 4 and min nodes=t=2
good video
thank u Thad Castle
😂
What happened to the reverb? It gave you a ton of gravitas! (Thanks for the great videos btw).
I moved and had some audio issues 🤦🏻♂️
Thank you!
Great video. It would have been great if you can visualize the code functions line by line. Nevertheless, This video is great.
what does t stands for :/ ?
Go back a few vids in the playlist, I explain it in the intro video
The series is over tho :(
A lot more coming :)
binomial trees and heaps also please
Here's my plalist on heaps: ruclips.net/p/PL9xmBV_5YoZNsyqgPW-DNwUeT8F8uhWc6
you just know shit like this takes 2k loc to implement efficiently when even high level explanation isnt trivial
github.com/msambol/dsa/blob/master/trees/b_tree.py 312 loc ;)
Hard
Slight formal error at 3a: it should be 2*(t-1) not 2t-1
nope