Scribd
Upload
347 views5 pages

AVL Tree Left-Right Rotation Explained

The document discusses using a left-right rotation to balance an AVL tree after an insertion causes imbalance. A single right rotation is not enough to balance the tree in some cases. Performing a left rotation followed by a right rotation, known as a left-right rotation, restores the balanced property. The algorithm for a left-right rotation involves first performing a left rotation on the left child of the unbalanced node, followed by a right rotation on the unbalanced node. An example is provided to illustrate the process.

Uploaded by

RajContent
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
347 views5 pages

AVL Tree Left-Right Rotation Explained

The document discusses using a left-right rotation to balance an AVL tree after an insertion causes imbalance. A single right rotation is not enough to balance the tree in some cases. Performing a left rotation followed by a right rotation, known as a left-right rotation, restores the balanced property. The algorithm for a left-right rotation involves first performing a left rotation on the left child of the unbalanced node, followed by a right rotation on the unbalanced node. An example is provided to illustrate the process.

Uploaded by

RajContent
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Left-Right Rotation (Inside Case):

Sometimes a single left or single right rotation is not sufficient to balance an


unbalanced tree. Lets see with the help of an example.
Insertion of node Y cause the balance factor of node Z to

become equal to 2, hence tree is unbalanced, so some kind of


rotation is clearly necessary, so which rotation we have to

use, single right or single left. As we can see that tree is left
heavy so we can use only right rotation. But Single right

rotation does not make the tree balanced. Let us see why?

X
Right Rotation

Unbalanced Tree

Unbalanced Tree

From above example we can see that single right rotation doesnt make the
tree balanced. Right rotation produces another unbalanced tree having
BF =-2 (node X). So single rotation is not enough to restore back its
balanced property, so we need double rotation. (Left-Right rotation)
Lets perform double rotation (Left-Right rotation) on a tree as given
below.
Z

Z
Left Rotation
at Node X

Right Rotation
at node Z

X
Y
Unbalanced Tree

Balanced Tree

If you still have a confusion in performing Left-Right rotation, lets have a


look at below given detailed explanation of Left-Right rotation.

Right Rotation at
Node Z

Left Rotation at
Node X

Y
Z

NULL

NULL

Note: Double Left Right rotation = First perform Single Left Rotation at left Child of node Z

Followed by Single Right Rotation at node Z

Example

8
Left Rotation
at node 4

4
6

6
Right Rotation
at node 8

6
4

Insert 2

Insert 3

6
8

Right Rotation
at node 4

4
Left Right Rotation

Left Right Rotation

6
3

6
8

Left Rotation
at node 2

2
3

Let us take a more complex scenario of double Left-Right rotation.


BF = 2 - 0 = 2

Y
B

Insertion of node C in the AVL tree leave


behind the tree unbalanced. We can also

see from balance factor of node Y (BF = 2),


So Double Left-Right rotation is required

to restore its AVL-ness property.


C
Unbalanced Tree

Y
B
A

Y
Z

Left Rotation

X
Z

Right Rotation

B
C

A
C

Left Right Rotation

OR
Y
B
A

Y
Z

Left Rotation

B
X

C
Z

Right Rotation

X
A

A
Left Right Rotation

Double Left-Right Rotation Algorithm

Perform Right
rotation around
P (node Z)
P

P->left
Perform left
rotation around
P->left (node X)

Left Rotation

Right Rotation

X
Y

X
Null

node double_left_right_rotate(node P)
{
node Q;

//pass node with BF = 2 to this function

P->left = single_left_rotate(p->left);

/* perform left rotation around p->left, and


store new root node returned by function
single_left_rotate in p->left. */

Q = single_right_rotate(P);

/* perform right rotation around node P, and


store new root node returned by function
single_right_rotate in Q, and return Q as
a new root node of the tree. */

return Q;
}

Perform right
rotation around Y

P->left

B
A

Left Rotation

X
Z

Right Rotation

B
A

Left Right Rotation

Example:BF = 2 - 0 = 2

20
30

10

15

20
Insert 13

30

10

15

15

20

10

Left-Right Rotation

13

Insert 11, 12

15

15

15
Insert 4

10

Left-Right Rotation

20

10

20

10

30

13

20
BF = 2

30

12

11

11

13

30

12

30

13
11

13

12
Insert 14

BF = 2

15

5
4

30

12
11

Left Rotation

20

10

12

15

14

30

13

10

13

20 Right Rotation

12

11

14

10
5

Left Right Rotation

15

11

13

20
14

30

You might also like