Scribd
Upload
4 views10 pages

AVL Tree Rotations Explained

The document discusses AVL trees, focusing on the calculation of balance factors and the types of rotations used to maintain balance. It outlines four types of rotations: Right-Right, Left-Left, Right-Left, and Left-Right, along with their respective transformations. The content is aimed at providing a foundational understanding of AVL tree balancing techniques.

Uploaded by

sahuanshika557
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
4 views10 pages

AVL Tree Rotations Explained

The document discusses AVL trees, focusing on the calculation of balance factors and the types of rotations used to maintain balance. It outlines four types of rotations: Right-Right, Left-Left, Right-Left, and Left-Right, along with their respective transformations. The content is aimed at providing a foundational understanding of AVL tree balancing techniques.

Uploaded by

sahuanshika557
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

DATA STRUCTURE

AVL Trees

Rita Nagar
Assistant Professor, CSE Department MPGI
prerequisite
AVL Tree
Calculation of Balance Factor in AVL
Outlines –
• Rotation in AVL tree
• Four transformation or Rotation
[Link] – Right
[Link] – Left
[Link] Left
[Link] Right
Imbalanced Tree

0–2=–2
8
0–1=–1
9
0–0=0
10

Only three rotations can be done to balance tree


Rotations –
Rotations

Single Rotation Double Rotation

Left Left Right


Rotation Rotation

Right Right Left


Rotation Rotation
R-R Rotation
8 , 9 , 10

0–2=–2
8
1–1= 0
0–1=–1
Anti clockwise
9
9 direction

0–0=0
8 10
10 0–0=0 0–0=0

R-R Transformation
L - L Rotation 10 , 9 , 8

10 2–0= 2
1–1= 0
Clockwise 9
9 1–0= 1 direction

8 10
8 0–0=0
0–0=0 0–0=0
R - L Rotation 10 , 12 , 11

10 0–2= -2 10 0–2=–2

R
R
RL→RR 11
12 1–0= 1 11 0–1=–1

L R
10 12
11 0 – 0 = 0 12 0–0=0
L - R Rotation 10 , 8 , 9

10 2–0= 2
10 2–0= 2

L 9
LR→LL
8 1–0= 1 9
R 8 10
9 0–0=0 8

You might also like