First I thought this explanation was going bad because the quality of the picture you put is low. But that's actually one of best explanations I've seen, thank you.
Great! This was a really clear review. Except for case 3 you only talked about finding the min of the right subtree. One can also replace the target node with the max of the left subtree. Either method works in keeping the tree in order.
Excellent video ... Best way to learn is to sit patiently, watch and practice the mind along with the video (pausing video at various points to do self analysis)..... Reply ·
Very succinct and to the point. Good video! I loved also the style for representing the different cases so I can rebuild the algorithm my own head without need to memorize anything else.
But what happens to nodes labeled 34 and 36 when we remove their father( when we replaced 30 by 32) Now 34 and 36 should be placed on the left subtree of 40 and not on its right, how to deal with it algorithmically?
When we replaced 30 with 32 we had to have deleted 32 so it is only in the tree once! To see what happens to 34 and 36 in that case, you can watch the video at 2 minutes and 50 seconds (ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-wcIRPqTR3Kc.htmlm50s) where I had shown 32 being removed. Node 34 would be the new left child of node 40 (and node 40 would be the parent of node 34). Does that make sense?
if I implement the remove method recursively, how can I remove a leaf ? Since by the time the recursion gets to the leaf, we lose access to the parent node
If we start with the tree at the very beginning of the video and delete 32, then we're deleting a node that has only one child. That's a simpler case (than if it had two children) and we can just make 40's left child be 34, which effectively removes 32. We just keep the same connection between 34 and 36, because in general we try to avoid restructuring binary search trees. Does that help?
colleen lewis yes. so while deleting 30 why do u choose to swap 32 in place of 30? we can choose 20. that can work too? while deleting 70 we can replace by 65. which is next smaller that too maintain tree property.? does it always have to be next bigger element?
That's just a convention for what you do when you delete a node with two children. I have chosen to use the next biggest rather than the next smallest, but either would work just fine. Does that make sense?
Two answers: Usually we'd just implement either the next biggest or the next smallest. Not both. We never have duplicate keys in our BST - so that never comes up. If we try to add a key that is already in the BST, we would just replace the old value associated with that key.
