CODEWITHSUNDEEP
algorithmbinary-search-tree
Kay
Kay

Reputation: 1485

Binary Search Tree, How should I rotate this tree to balance

I am trying to rotate a tree to keep it balanced, but I am having hard time with this example. I am not so sure what I am doing wrong here.

I have below tree with L/R height difference 1 at node 30. So, I guess this tree is balanced.

     30
    /  \
   20  60
  /  \
 10  25

I am adding 22 here and this is what I get after adding 22.

     30
    /  \
   20  60
  /  \
 10  25
    /
   22

At node 20, L/R height difference is 1, but at node 30 it is 2. So, I guess it is not balanced any more. I am trying to right rotate the tree to balance it, but I am getting below tree.

    20
   /  \
  10  30
     /  \
    25  60
   /
  22

After the rotation, node 20 has L/R height difference of 2 still.

Where am I doing wrong? Can this tree be balanced using rotation?

I can balance the tree using sorted array method like below, but I am really confused about rotation balance in this example.

     22              25
    /  \            /  \
   20   30         20   30
  /    /  \       /  \   \
 10   25  60     10  22   60

What am I doing wrong here?

Thanks a lot!!

Upvotes: 4

Views: 1099

Answers (2)

Dhiral Kaniya
Dhiral Kaniya

Reputation: 2051

There are basically four type of rotation in the AVL Tree.

  • Right-left
  • Left-Right
  • Left-Left
  • Right-Right

In your case, Left-Right should be applicable.

Here you need to perform two steps.

1:- Left rotate from 20 node. So your tree should like as below.

         30
        /  \
      25  60
     / 
   20 
  /  \
 10  22

2:- Right rotate from 30 node. So your tree should be like as below.

     25
    /  \
   20   30 
  /  \   \
 10  22  60

You can refer the N website to understand the behavior. Here is one of the best link

Upvotes: 4

David Eisenstat
David Eisenstat

Reputation: 65458

This case requires a double rotation: rotate 25 up twice. I'm assuming that you're thinking about AVL trees, but all of the standard balanced binary trees need double rotations in some cases.

Upvotes: 4

Related Questions