CODEWITHSUNDEEP
treeavl-tree
sundq
sundq

Reputation: 763

The AVL tree four rotate is not works

We know for keep a binary tree balance, we can use RR LL RL LR foure rotate to make the unbalance tree to balance, But if we have a balance tree as fllows:

        885
        / \
       /   \
     659   912
     / \     \
    /   \    934
  212   759
  / \
 /   \
11   344

if we add a node (168) to this tree and the tree like this:

        885
        / \
       /   \
     659   912
     / \     \
    /   \    934
  212   759
  / \
 /   \
11   344
 \
 168

the tree is not balance, but I can not use any of four rotate(RR, LL ,RL, LR) to make the tree balance again. anyone TELL me why?

Upvotes: 0

Views: 70

Answers (1)

guymaor86
guymaor86

Reputation: 466

The tree is left heavy, but the tree's left subtree is not left heavy, you only need to do a right rotation. After doing a right rotation the tree will look as follows:

                 659
                /   \
               /     \
             212      885
             / \      /  \
            /   \    /    \
           11   344  759   912
             \               \
              \               \
               168             934

Try using the following algorithm for deciding which method to do:

IF tree is right heavy {
 IF tree's right subtree is left heavy {
   Perform Double Left rotation
 }
 ELSE{
   Perform Single Left rotation
 }
}
ELSE IF tree is left heavy {
 IF tree's left subtree is right heavy {
   Perform Double Right rotation
 }
 ELSE {
   Perform Single Right rotation
 } 
}

Upvotes: 1

Related Questions