Data structure & algorithms (AVL Tree notes)

Data Structures and Algorithm
(CC-2042)
Lecture 25
E N G R. D R B I L A L A S H FA Q A H M E D
S C H O O L O F S Y S T E M S A N D T E C H N O LO GY ( S S T )
C O M P U T E R S C I E N C E FA C U LT Y

, AVL Tree
 An AVL Tree is a Self-Balancing
Binary Search Tree (BST) wher
 the height difference (or balan
factor) between the left and ri
subtrees of any node is at mos
 Named after its inventors Adel
Velsky and Landis.
 Ensures all operations like sea
insertion, and deletion are 𝑂(l
where 𝑛 is the number of node



09/06/2025 DS

, Key Concepts
1. Balance Factor:
Balance Factor = Height of Left Subtree - Height of Right Subtree.
For any node:
 Balance Factor =−1,0,or 1 : The tree is balanced.
 Balance Factor <−1 or >1 : The tree is unbalanced.

2. Rotations:
To rebalance the tree, rotations are performed:
 Left Rotation (LL Case): Right-heavy tree.
 Right Rotation (RR Case): Left-heavy tree.
 Left-Right Rotation (LR Case): Left subtree of the right child is
heavy.
 Right-Left Rotation (RL Case): Right subtree of the left child is
heavy.

09/06/2025 DS