balancing an AVL tree (C++)

Question

I'm having the hardest time trying to figure out how to balance an AVL tree for my class. I've got it inserting with this:

Node* Tree::insert(int d)
{
    cout << "base insert\t" << d << endl;
    if (head == NULL)
        return (head = new Node(d));
    else
        return insert(head, d);
}

Node* Tree::insert(Node*& current, int d)
{
    cout << "insert\t" << d << endl;
    if (current == NULL)
        current = new Node(d);
    else if (d < current->data) {
        insert(current->lchild, d);
        if (height(current->lchild) - height(current->rchild)) {
            if (d < current->lchild->getData())
                rotateLeftOnce(current);
            else
                rotateLeftTwice(current);
        }
    }
    else if (d > current->getData()) {
        insert(current->rchild, d);
        if (height(current->rchild) - height(current->lchild)) {
            if (d > current->rchild->getData())
                rotateRightOnce(current);
            else
                rotateRightTwice(current);
        }
    }

    return current;
}

My plan was to have the calls to balance() check to see if the tree needs balancing and then balance as needed. The trouble is, I can't even figure out how to traverse the tree to find the correct unbalanced node. I know how to traverse the tree recursively, but I can't seem to translate that algorithm into finding the lowest unbalanced node. I'm also having trouble writing an iterative algorithm. Any help would be appreciated. :)

Solution 1

You can measure the height of a branch at a given point to calculate the unbalance

(remember a difference in height (levels) >= 2 means your tree is not balanced)

int Tree::Height(TreeNode *node){
     int left, right;

     if(node==NULL)
         return 0;
     left = Height(node->left);
     right = Height(node->right);
  if(left > right)
            return left+1;
         else
            return right+1;
} 

Depending on the unevenness then you can rotate as necessary

void Tree::rotateLeftOnce(TreeNode*& node){
     TreeNode *otherNode;

     otherNode = node->left;
     node->left = otherNode->right;
     otherNode->right = node;
     node = otherNode;
}


void Tree::rotateLeftTwice(TreeNode*& node){
     rotateRightOnce(node->left);
     rotateLeftOnce(node);
}


void Tree::rotateRightOnce(TreeNode*& node){
     TreeNode *otherNode;

     otherNode = node->right;
     node->right = otherNode->left;
     otherNode->left = node;
     node = otherNode;
}


void Tree::rotateRightTwice(TreeNode*& node){
     rotateLeftOnce(node->right);
     rotateRightOnce(node);
}

Now that we know how to rotate, lets say you want to insert a value in the tree... First we check whether the tree is empty or not

TreeNode* Tree::insert(int d){
     if(isEmpty()){
         return (root = new TreeNode(d));  //Is empty when root = null
     }
     else
         return insert(root, d);           //step-into the tree and place "d"
}

When the tree is not empty we use recursion to traverse the tree and get to where is needed

TreeNode* Tree::insert(TreeNode*& node, int d_IN){
     if(node == NULL)  // (1) If we are at the end of the tree place the value
         node = new TreeNode(d_IN);
     else if(d_IN < node->d_stored){  //(2) otherwise go left if smaller
         insert(node->left, d_IN);    
         if(Height(node->left) - Height(node->right) == 2){
            if(d_IN < node->left->d_stored)
                rotateLeftOnce(node);
            else
                rotateLeftTwice(node);
         }
     }
     else if(d_IN > node->d_stored){ // (3) otherwise go right if bigger
        insert(node->right, d_IN);
        if(Height(node->right) - Height(node->left) == 2){
            if(d_IN > node->right->d_stored)
                rotateRightOnce(node);
            else
                rotateRightTwice(node);
        }
     }
     return node;
}

You should always check for balance (and do rotations if necessary) when modifying the tree, no point waiting until the end when the tree is a mess to balance it. That just complicates things...

---

UPDATE

There is a mistake in your implementation, in the code below you are not checking correctly whether the tree is unbalanced. You need to check whether the height is equals to 2 (therefore unbalance). As a result the code bellow...

if (height(current->lchild) - height(current->rchild)) { ...

if (height(current->rchild) - height(current->lchild)) {...

Should become...

if (height(current->lchild) - height(current->rchild) == 2) { ...

if (height(current->rchild) - height(current->lchild) == 2) {...

---

Some Resources

• AVL Tree ~ Imprementation in C++
• AVL Tree ~ Applet

Solution 2

Wait, wait, wait. You aren't really going to check the "height" of every branch each time you're inserting something, are you?

Measuring the height means transversing all the sub-branch. Means - every insert into such a tree will cost O(N). If so - what do you need such a tree? You may use a sorted array as well: it gives O(N) insertion/deletion and O(log N) search.

A correct AVL handling algorithm must store the left/right height difference at each node. Then, after every operation (insert/remove) - you must make sure none of the affected nodes will be too much unbalanced. To do this you do the so-called "rotations". During them you don't actually re-measure the heights. You just don't have to: every rotation changes the balance of the affected nodes by some predictable value.

Solution 3

goto http://code.google.com/p/self-balancing-avl-tree/ , all usual operations like add, delete are implemented, plus concat and split

Solution 4

Commented out is the code right rotate above and left rotate, below is my working right rotate and my working left rotate. I think the logic in the rotate above is inversed:

 void rotateRight(Node *& n){
    //Node* temp = n->right;
    //n->right = temp->left;
    //temp->left = n;
    //n = temp;
    cout << "}}}}}}}}}}}}}}}}}}}}}ROTATE RIGHT}}}}}}}}}}}}}}}}}}}}}" << endl;
    Node *temp = n->left;
    n->left = temp->right;
    temp->right = n;
    n = temp;
}

void rotateLeft(Node *& n){
    //Node *temp = n->left;
    //n->left = temp->right;
    //temp->right = n;
    //n = temp;
    cout << "}}}}}}}}}}}}}}}}}}}}}ROTATE LEFT}}}}}}}}}}}}}}}}}}}}}" << endl;
    Node* temp = n->right;
    n->right = temp->left;
    temp->left = n;
    n = temp;
}

View more solutions

Comments

[gregghz]

Thanks for the detailed comment. It is very helpful. However, I don't think I understand your insert method. What is the purpose the the first parameter? In the code I show above, I start at the head and loop until I find the correct location for the tree. Is that a bad method of doing this? It seems with your insert method, you already know before hand where the node belongs.

[Carlos]

see the edit hopefully it will help. Looping is not the best choice, use recursion instead, as it is easier to manipulate the nodes of the tree.

[gregghz]

So when I run this code, I get a seg fault at node = new TreeNode(d_IN); in the second insert method, what might cause that?

[Carlos]

update your question for a moment with your implementation to check

[Carlos]

i have updated my answer, there was a mistake on ur code, however i not really sure why are you getting seg fault. Sorry buddy

[dhruvbird]

You will never have a case where abs(the difference in height) > 2. It will always be one of [0, 1, 2], which means that you can change the description to: "(remember a difference in height (levels) >= 2 means your tree is not balanced)"

[Terrenium]

@Carlos I just don't understand the part where you are doing this: Code: "if (d_IN > node->right->d){rotateRightOnce} else{rotateRightTwice}". can you explain it a bit. It would be much of a favor.