Scribd
Upload
2 views2 pages

AVL Tree Notes

An AVL Tree is a self-balancing Binary Search Tree where the height difference between left and right subtrees is at most 1. It uses a Balance Factor to determine when rotations are needed to maintain balance, with four types of rotations available. While AVL Trees offer fast searching and guaranteed O(log n) time complexity for operations, they also incur additional complexity due to rotations and require extra memory for storing height and balance factors.

Uploaded by

Honey Neelam
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
2 views2 pages

AVL Tree Notes

An AVL Tree is a self-balancing Binary Search Tree where the height difference between left and right subtrees is at most 1. It uses a Balance Factor to determine when rotations are needed to maintain balance, with four types of rotations available. While AVL Trees offer fast searching and guaranteed O(log n) time complexity for operations, they also incur additional complexity due to rotations and require extra memory for storing height and balance factors.

Uploaded by

Honey Neelam
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

AVL Tree (Data Structures)

An AVL Tree is a self-balancing Binary Search Tree (BST) where the difference between the heights of
left and right subtrees for any node is not more than 1.
It was invented by Georgy Adelson-Velsky and Evgenii Landis in 1962.

1. Balance Factor
The Balance Factor (BF) of a node is:
BF = Height of Left Subtree − Height of Right Subtree
Possible values: -1, 0, +1
If BF becomes less than -1 or greater than +1, the tree becomes unbalanced, and rotations are used to
balance it.

2. Example AVL Tree


30
/ \
20 40
/ \
10 25

Node Left Height Right Height BF


30 2 1 +1
20 1 1 0
40 0 0 0

3. Rotations in AVL Tree


To maintain balance, 4 types of rotations are used.
1. Left Rotation (RR Case)
Before Rotation
10
\
20
\
30
After Rotation
20
/ \
10 30

2. Right Rotation (LL Case)


Before Rotation
30
/
20
/
10
After Rotation
20
/ \
10 30

3. Left-Right Rotation (LR Case)


Before
30
/
10
\
20
After
20
/ \
10 30

4. Right-Left Rotation (RL Case)


Before
10
\
30
/
20
After
20
/ \
10 30

4. Operations in AVL Tree


Operation Complexity
Search O(log n)
Insert O(log n)
Delete O(log n)

5. Advantages
• Fast searching
• Balanced structure
• Guaranteed O(log n) time

6. Disadvantages
• Rotations increase complexity
• More memory for storing height/balance factor

You might also like