Member Avatar for sobias

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
  • 7K Views
  • 8 Hours Discussion Span
  • Latest Post Latest Post by Taywin
Member Avatar for Taywin

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
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.