GATE CSE 1988 | Question: 7iii

Question

Consider the tree given in the below figure, insert $13$ and show the new balance factors that would arise if the tree is not rebalanced. Finally, carry out the required rebalancing of the tree and show the new tree with the balance factors on each mode.

Comments

Something is not right here. The balancing is switching between +2 and -2

---

why wrong? I got this

Answer 1

$13$ is less than $14$, so it is placed on the left side of $14$

Now need to be rebalanced. Here $17$ is unbalanced, So, in the $2^{\text{nd}}$ tree we need $1$ right rotation to $17$.

Now, $12$ is unbalanced.To balance it we need $1$ right rotation and $1$ left rotation

Comments

This question asks about the balance factors before and after the balancing of node 13 right??

---

@ASNR1010 Yes correct. After inserting $13$ but before rebalancing balance factors are:-

Node $17$ = $2$ // Here is the problem

Node $12,5,15,4$ = $1$ each

Other nodes = $0$

Answer 2

The insertion of 13 leads to LR imbalance at root. Note LR imbalance can be corrected by :

1. Rotate the  node(which is in 'R' side) anticlockwise.
2. After step 1, we will get LL imbalance, therefore rotate clockwise to balance it.

After this, placed the balanced portion on the remaining tree, and adjust tree(i.e greater value on right side and smaller values on left side).

Refer Below pic for answer:

Comments

Here at node 17 again there is RR imbalance.

---

Missed the node 16 to the left of 17. Otherwise this is the correct method. Only one LR double rotation is required.

Answer 3

..........

After adding $13$ balancing factor of $17=+2$ and of $12=-1$. Which will lead to $L-R$ problem and it will require $2$ rotations $(1-L\ rotation\ \&\ 1-R\ rotation)$

$1)$ $L-Rotation$

Balancing factor of $17=+2$ and of $15=+2$. Which will lead to $L-L$ problem and it will require $1-R$ rotation.

$2)$ $R-Rotation$