0

Hi,

Very fast question guys, since tomorrow is my quiz and I have to sleep now. I stompled upon an old question asking to ** remove the root of the AVL Tree** . I never tried that before, after a very fast search, I found this PDF File https://www.student.cs.uwaterloo.ca/~cs240/s10/handouts/tree-examples.pdf ** and one of the slides it asks to delete the root. I nocited that they did a swipe between the node (22) and (28) why? is it because (28) does not cause any imbalances? if yes, can I swipe the root with any other node like 28?**
of course I have to balance the tree with many rotations and such but I just want an answer for my question above.

2
Contributors
1
Reply
4
Views
4 Years
Discussion Span
Last Post by Taywin
0

The reason is the algorithm of node deletion.

"If the node is a leaf or has only one child, remove it. Otherwise, replace it with either the largest in its left sub tree (in order predecessor) or the smallest in its right sub tree (in order successor), and remove that node. The node that was found as a replacement has at most one sub tree. After deletion, retrace the path back up the tree (parent of the replacement) to the root, adjusting the balance factors as needed."

That should be enough to answer why 28 is used to replaced the node 22 -- the smallest value of the right sub tree. It doesn't matter whether or not a node is the root. Any node being deleted will follow the algorithm.

Edited by Taywin

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.