algorithmdata-structurestreeavl-treetree-balancing

Balancing an AVL tree

I'm having trouble with a balancing-AVL tree question, since my solution appears to conflict with the back-of-the-textbook solution. I've looked at online visualizations of AVL trees, and they suggest mine is correct. Is my textbook wrong?

This is the tree: enter image description here

I then have to insert 65 into this AVL tree. This causes an imbalance, and from my understanding, a rightleft rotation is required.

Here is what I come up with, and have confirmed via http://robinsswei.github.io/VisGraphs/avltree.html: enter image description here

And here is what my textbook states is the correct answer:

enter image description here

Which one is the right answer?

Solution

  • AVL Tree Diagram

    Hey there, I actually think that both solutions are correct. I think there's just a couple reasons why your book might have it different. After insertion of the node, you will find that 2 different nodes have a balance factor of two. That was node 34 and 45. How that algorithm works is after insertion, it follows that path back to the root node checking the balance factors along with updating their node height. I think because the root was last to be accessed and flagged for rotation is why it did it that way. Another potential reason is that for the root node, the rotation only required a simple rotation whereas the one you did requires a double rotation. Regardless I feel both answers are adequate.

    I'll try to explain this problem for those who may not know what AVL trees are. I tried to label an illustration of this as well. The first thing you want to do is make sure your starting AVL tree meets the requirements before inserting the new node in. I would just label the height of each node and then get the height differences of your children nodes per parent.

    AVL Trees require heights of left and right children of every node to differ by at most +1 or -1. (-1,0,1)

    For example in the first figure, before inserting, Id start from bottom to top. Node 87 doesn't have any children to this would be 0. Node 45 has only one child so we tally 87's 0 height. Node 3 has no children so this would be 0 as well. Node 34 has two children, 3 and 45. Their difference is only 1. All nodes have passed the AVL Tree test.

    Next just insert the node by traversing it just like a Binary Search Tree.

    Re-label the heights of your nodes after insertion and compare them again for each node. This time we see that node 34 (our root node) has a "2" difference between children(2-0). We know now that a rotation is necessary for node 34.
    Executed a simple left rotation and AVL properties were met.