AVL Tree - rotation oddity: Breaking BST property

Question

While I was working on a AVL Tree implementation, I encounter a case that a rotation breaking BST property.

I am pretty sure I am doing something wrong, but I cannot figure out what it is.

I inserted 41, 49, 21 and 47 to a AVL tree. When I added 49 one more time, it signaled "Out of Balance" as below.

                 (Out of balance !!!)
                 (   at 49 L-R      )
     41                41
    /  \              /  \
   21   49  =>      21    49
       /                 /
      47               47
                         \
                          49

Hence I tried to rotate 47 to left and 49 to right like below

          Rotate 47         Rotate 49
           to Left          to Right 
     41               41                 41
    /  \     =>      /  \      =>       /  \  
   21   49         21    49           21    49 
       /                /                  /  \
      47               49                47    49
        \             /
         49          47

The tree is better balanced, but I think I broke the BST property in lower right sub-tree by having 49 in the right side of 49

    49
   /  \
  47  49

I think the best way to balance this tree is following

     47
    /  \
  41    49
  /    /
21   49

but I don't know how to get there with 41-49-21-47-49 number add sequence. Maybe that is not the correct outcome, but I am lost here.

What would the optimal outcome and how should I get there?

Can somebody tell me what I am doing wrong?

Thanks a lot!!!

Answer 1

For your case, if keys and values coincide it could be as follows. Let's say your Node class is as follows:

class Node {
    int value;     //Value
    int height;    //Height
    Node left;     //Left child
    Node right;    //Right child
    int count = 1; //keeps track of how many duplicate values were inserted
}

Then, when inserting a new value you could increment count if there's a new value equal a value from the current node. Below is my implementation for an AVL tree insertion:

public Node insert(Node root, int value) {
    if (root == null) {
        root = new Node();
        root.value = value;
        return root;
    } else if (root.value > value) {
        root.left = insert(root.left, value);
        root.height = Math.max(root.height, root.left.height + 1);
    } else if (root.value < value) {
        root.right = insert(root.right, value);
        root.height = Math.max(root.height, root.right.height + 1);
    } else {
        // consider duplicates the same node
        root.count++;
    }

    Node a = root;
    //left subtree must be rebalanced
    if (balanceFactor(root) == 2) {
        Node b = a.left;
        //it's a left left case
        if (balanceFactor(b) == 1) {
            Node b2 = b.right;
            b.right = a;
            a.left = b2;
            a.height = getHeight(a);
            b.height = getHeight(b);
            return b;
        } else {//it's a left right case
            Node c = b.right;
            Node c1 = c.left;
            Node c2 = c.right;
            a.left = c2;
            c.right = a;
            c.left = b;
            b.right = c1;
            a.height = getHeight(a);
            b.height = getHeight(b);
            c.height = getHeight(c);
            return c;
        }
    } else if (balanceFactor(root) == -2) {//right subtree must be rebalanced
        Node b = a.right;
        //it's a left left case
        if (balanceFactor(b) == -1) {
            Node b1 = b.left;
            b.left = a;
            a.right = b1;
            a.height = getHeight(a);
            b.height = getHeight(b);
            return b;
        } else {//it's a left right case
            Node c = b.left;
            Node c1 = c.left;
            Node c2 = c.right;
            c.right = b;
            c.left = a;
            b.left = c2;
            a.right = c1;
            a.height = getHeight(a);
            b.height = getHeight(b);
            c.height = getHeight(c);
            return c;
        }
    }

    return root;
}

private static int getHeight(Node node) {
    int l = (node.left == null ? 0 : node.left.height + 1);
    int r = (node.right == null ? 0 : node.right.height + 1);
    return Math.max(l, r);
}

private static int balanceFactor(Node node) {
    int left = node.left == null ? -1 : node.left.height;
    int right = node.right == null ? -1 : node.right.height;

    return left - right;
}

This way, you don't really have duplicates anymore :)

Answer 2

You didn't actually do anything wrong.

In comments, you say "I thought L side is smaller or equal to current node value and R side is bigger value. Am I wrong about this?"

...and yes, you are wrong about that.

For trees with duplicate values, the condition that the right branch contains only strictly larger elements is not compatible with balancing operations. Try this: link 20 copies of the same value into a tree. If you can only link equal values on the left then you have to make a singly-linked list. Your tree will be 20 levels deep and completely unbalanced.

The way to think about duplicate values in the tree is that there really aren't any duplicate values in the tree :-) A BST defines a total ordering, and valid rebalancing operations like rotations preserve this total ordering.

When you insert that 2nd 49 into the tree, you'll put it either to the left or right of the first 49. If you put it on the left, then it will be smaller according to the ordering of the tree, and it will always be smaller after any rebalancing. If you put it on the right, then it will be larger, and will stay larger according to the tree's ordering.

If you think about it, it has to be this way because the balancing operations don't even look at the values in the nodes. The way they're linked together determines the ordering, and the ordering doesn't change.