William. This is undoubtedly the simplest and the most authentic explanation of an AVL tree node deletion and I could show it to my brother. It helped him a lot. Thanks to you.
Isn't what you call "left tree successor" called predecessor? I'm not sure if I understand it right, but I though that successor of node N was the node with the smallest key in the right subtree, and predecessor was the largest node in the left subtree
What if I want to remove node 3 then node 1 from tree shown at 7:44? There needs to be some kind of rebalancing, that seems hardest for me. Because that brach will have a height difference of 2.
Please see the description for the previous videos explaining the update and balance methods. Otherwise removing from an AVL tree is identical to removing from a BST. Please check out the next video (source code video) if you are still struggling to piece together how removals work. Hope this helps!
Question.. you call delete on 8, the code recurses through the tree until it finds the element with value "8", which sets up this video. Next you recurse from node 8 to determine a valid replacement (if any). This is determined to be 11 as it's the smallest element on the right side. From here you simply assign the value of the "smallest element" to the "element being replaced", that's easy, 8 becomes 11. At 7:19 you say we need to recurse through the tree one more time to remove the 11, but I don't believe this step is necessary. 11 is already determined to have no left-children, and you have it's location in memory. So wouldn't you simply do this.. nodeToDelete = find(8); // address of node in question nodeToReplace = nodeToDelete.findReplacement(); // address of replacement node // ~~some logic here to handle no replacements being found, e.g. node being replaced has no children ~~ nodeToDelete.value = nodeToReplace.value; // assign the value of the replacement node to the found node nodeToReplace.right.parent = nodeToReplace.parent // point the replacement RIGHT to the replacement PARENT nodeToReplace.parent.left = nodeToReplace.right // point the replacement PARENT to the replacement RIGHT free(nodeToReplace); // free up memory of the moved node If node(11) is already in memory I don't see a reason to recursively find it again
That's not right bro, 4:55 in this case, 9 have to be removed and replaced with 8, then rotate LL from 8, because of 8 is bigger than 7 so it'll still be an avl binary tree
The example in the video satisfied the BST invariant. So it is correct. BSTs does not need to have unique solutions. Since it is balanced, no further action is needed even if its an AVL tree.
William. This is undoubtedly the simplest and the most authentic explanation of an AVL tree node deletion and I could show it to my brother. It helped him a lot. Thanks to you.
Sir you are a lifesaver. Just before my exam I am able to clear my doubts just because of you.
very insightful, I love the format of this content, very straightforward and concise, saved me a lot of time.
5:44 the largest value in the left subtree is usually called the predecessor
4:29 is not an AVL tree, because balance factor of 9 is -2 (left subtree is greatrer)
Correct, Im not sure why he didn’t mention balance, since its the primary property of AVL trees lol
I was also wondering that
Watched it on 2x speed, thanks for summarizing in 5 mins the lecture what my university couldnt explain in 45 mins.
You and every other genius on youtube watches it at 2x speed and then complains when they get 50 on the exam.
This video helpd me pass my final exam.Thanks lot!
Thank you So much for this explanation, you are so underrated ❤❤
Isn't what you call "left tree successor" called predecessor? I'm not sure if I understand it right, but I though that successor of node N was the node with the smallest key in the right subtree, and predecessor was the largest node in the left subtree
How did you create these amazing slides, especially those BSTs and step-by-step explanations of the algorithms? I would like to create for myself
High quality video! Really helped me. Thanks in advance.
Amazing explanation!!
At 7:52. Which node do you use on the rebalancing when you rebalance the tree? Is it the new root of the tree which is the new "11"?
In the case of a normal BST, couldn’t you just do the two subtrees case for one subtree?
Thanks For the easy explaining what professor made it hard to understand
How does AVL balancing different from red-black balancing?
What if I want to remove node 3 then node 1 from tree shown at 7:44? There needs to be some kind of rebalancing, that seems hardest for me. Because that brach will have a height difference of 2.
thank you! :)
so underrated♥
9 minutes > my teacher 6 hours
Quality video.
but the tree isn't even balanced initially?
it's not
avl
Please see the description for the previous videos explaining the update and balance methods. Otherwise removing from an AVL tree is identical to removing from a BST. Please check out the next video (source code video) if you are still struggling to piece together how removals work. Hope this helps!
Keep it up!
Question.. you call delete on 8, the code recurses through the tree until it finds the element with value "8", which sets up this video.
Next you recurse from node 8 to determine a valid replacement (if any). This is determined to be 11 as it's the smallest element on the right side.
From here you simply assign the value of the "smallest element" to the "element being replaced", that's easy, 8 becomes 11.
At 7:19 you say we need to recurse through the tree one more time to remove the 11, but I don't believe this step is necessary. 11 is already determined to have no left-children, and you have it's location in memory. So wouldn't you simply do this..
nodeToDelete = find(8); // address of node in question
nodeToReplace = nodeToDelete.findReplacement(); // address of replacement node
// ~~some logic here to handle no replacements being found, e.g. node being replaced has no children ~~
nodeToDelete.value = nodeToReplace.value; // assign the value of the replacement node to the found node
nodeToReplace.right.parent = nodeToReplace.parent // point the replacement RIGHT to the replacement PARENT
nodeToReplace.parent.left = nodeToReplace.right // point the replacement PARENT to the replacement RIGHT
free(nodeToReplace); // free up memory of the moved node
If node(11) is already in memory I don't see a reason to recursively find it again
This deserves more views
4:50 how is the predessecor is 7? it should be 8
That's not right bro, 4:55 in this case, 9 have to be removed and replaced with 8, then rotate LL from 8, because of 8 is bigger than 7 so it'll still be an avl binary tree
The example in the video satisfied the BST invariant. So it is correct. BSTs does not need to have unique solutions. Since it is balanced, no further action is needed even if its an AVL tree.
the last implementation of AVL tree is slow...
why would it be slow?