javadata-structuresbinary-treeavl-tree

How do I balance a large AVL tree?


I am trying to relearn how to balance AVL trees. After watching many tutorials, I thought I got the gist of it, but then I came across a particular scenario and now I'm stumped.

I am building an AVL tree using the numbers 5, 2, 3, 9, 4, 1, 6, 8, 10, 7, inserted in that order. The tree balances without any issues all the way up to 10, but my algorithm cannot balance the tree after adding 7. Here is what the tree looks like before I balance it after adding 7:

    3
  ┌─┴──┐
  2    8 <-- Unbalanced subtree
┌─┘  ┌─┴──┐
1    5    9
    ┌┴─┐  └─┐
    4  6   10
       └─┐
         7 <-- Node causing the tree to be unbalanced 

I know from using USFCA's AVL Tree Visualizer that my tree is suppose to look like this after I balance it, but I do not know how to achieve this result:

      5
   ┌──┴───┐
   3      8
  ┌┴─┐  ┌─┴──┐
  2  4  6    9
┌─┘     └─┐  └─┐
1         7   10

This tutorial indicates that I should perform a left-right rotation on 8, which results in something inconsistent with the desired result:

     8
   ┌─┴──┐
   3    9
  ┌┴─┐  └─┐
  2  4   10
┌─┘  └─┐
1      5
       └─┐
         6
         └─┐
           7

This is the logic I am using to determine which rotations to use for a given node (let me know if I should include the code for my rotate methods - I am not sure if it is necessary for an MCVE):

private void balance(Node node) {
    if (node == null)
        return;

    int balanceFactor = balanceFactor(node);
    if (balanceFactor > 1) {
        // Left subtree is heavier
        balanceFactor = balanceFactor(node.left);
        if (balanceFactor > 0) {
            rightRotate(node.left.left);
        } else {
            leftRotate(node.left.right);
            rightRotate(node.left);
        }
    } else if (balanceFactor < -1) {
        // Right subtree is heavier
        balanceFactor = balanceFactor(node.right);
        if (balanceFactor > 0) {
            leftRotate(node.right);
            rightRotate(node.right.left);
        } else {
            leftRotate(node.right);
        }
    }

    balance(node.parent);
}

It would seem to me that the logic works well until the root node becomes right-heavy.

What do I need to do differently to balance this tree?


Solution

  • The code block for the case where balanceFactor < -1 should mirror the other block in terms of left/right and balance factor comparisons. This is currently not the case. So change it to:

    } else if (balanceFactor < -1) {
        // Right subtree is heavier
        balanceFactor = balanceFactor(node.right);
        if (balanceFactor <= 0) {
            leftRotate(node.right.right);
        } else {
            rightRotate(node.right.left);
            leftRotate(node.right);
        }
    }
    

    Note that I used <=. This can also be done in the first case (>=), as even when the balance factor at the child is zero, you can suffice with one rotation.

    See also Wikipedia on rebalancing. Be aware that they use an opposite sign for the balance factor.