-1
$\begingroup$

I have the following AVL tree and want to AVL-INSERT a node 5 into the tree. Since the middle branch will be unbalanced, I'm guessing that it will require a right rotation, then a left rotation to rebalance the tree. However, what would the actual steps to rebalance the tree look like?

Before insert (balanced):

    3
   / \
  2   7    
 /   / \  
1   4   8  
      \  
       6  

After insert, but before balancing (unbalanced):

    3
   / \
  2   7    
 /   / \  
1   4   8  
      \  
       6  
      /
     5 
$\endgroup$
  • $\begingroup$ I suggest you follow the algorithm. $\endgroup$ – Raphael Jan 30 '18 at 22:00
0
$\begingroup$

the first step is notice that 4 node is unbalanced with balancing factor of $-2$, and a RL case
What you need to do is to do a RR rotation on the child of unbalanced node, that is 6 node.
the aspect of your tree should be this:

    3
   / \
  2   7    
 /   / \  
1   4   8
     \  
      5  
       \
        6

After, you have to do a LL rotation on the 4 node, and your tree should become like this:

    3
   / \
  2   7    
 /   / \  
1   5   8
   / \  
  4   6

And you have rebalanced your tree.

$\endgroup$
  • $\begingroup$ Wouldn't node 4 have a balancing factor of +2? $\endgroup$ – Paradox Feb 1 '18 at 20:05
  • $\begingroup$ No, in an AVL tree, balancing factor is the difference between the height of the left subtree and the right subtree, and in this case, the left subtree has an height of -1, and the right subtree has an height of 1, so -1 - (1) = -2 $\endgroup$ – Lorenzo Tagliabue Feb 1 '18 at 20:12
  • $\begingroup$ Node 4 has no nodes in the left subtree and its right subtree has a height of 2 since it has 6 and 5 below it. So wouldn't it still be +2 since +2 - 0 = +2? I'm referring to the second tree in my question, once the node has been inserted. BalanceFactor(N) := Height(RightSubtree(N)) – Height(LeftSubtree(N)) from en.wikipedia.org/wiki/AVL_tree#Balance_factor $\endgroup$ – Paradox Feb 1 '18 at 20:15
  • $\begingroup$ You have done two wrong things. First, you have to do the difference between the left subtree and the right subtree, not the contrary. Second, a common error is consider the subtree height of an unbalanced node as the height from the unbalanced node to down. And that is an error, because in this case, right subtree is the height from 5 to 6, so is of 1. With regards to the left subtree, when there is not a subtree, the height is commonly considered as -1. So, the left subtree -1 minus the right subtree of 1, results -2, that is balancing factor of 4 node $\endgroup$ – Lorenzo Tagliabue Feb 1 '18 at 20:31
  • $\begingroup$ Wikipedia and my lec notes both show the formula that I gave you, to subtract the h(left subtree) from the right. However, tutorialspoint shows the balance factor to be how you describe. So this seems that it's a matter of preference as it can be implemented both ways. But when comes to height, my professor's notes show a NULL node to be h=-1, a single node to be a h=0 and two nodes to be a h=1 because height is the number of edges. One node has 0 edges, 2 nodes have 1 edge. Tutorialspoint says the same: tutorialspoint.com/data_structures_algorithms/… $\endgroup$ – Paradox Feb 1 '18 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.