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
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?
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.
Don't get discouraged. Please keep uploading these!
full steam ahead
Your B tree and red black tree video I think are the best that I can find on UA-cam. 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!
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 :)
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
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
The legend and saviour is back 😇
thank you MIchael, watched all the playlist, good teaching
4:09 why can't we just delete 17 from the leaf? After the deletion keys amount in this node will equal to 3 (which is equal to t)
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
4:37 what if root had more than one key? would we still move only one key from the root, or all of them?
in case 3b how are you sure that if u merge it wont violate upper bound property cause there maybe 2 or 3 keys in root right?
Please Clarify
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
Great video❤
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
@@mizit8864why so?
thank u Thad Castle
😂
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
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?
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?
God bless you
t=m/2
where maximum nodes can be m-1
So for m=5 max nodes 4 and min nodes=t=2
Great video. It would have been great if you can visualize the code functions line by line. Nevertheless, This video is great.
can someone explain 3b stage
May you explain graphs? 🙏
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!
what does t stands for :/ ?
Go back a few vids in the playlist, I explain it in the intro video
good video
The series is over tho :(
A lot more coming :)
binomial trees and heaps also please
Here's my plalist on heaps: ua-cam.com/play/PL9xmBV_5YoZNsyqgPW-DNwUeT8F8uhWc6.html
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