Balanced Trees & AVL Trees | Data Structures & Algorithms
Balanced & AVL Trees
Introduction to Balanced and AVL Trees
Data Structures & Algorithms — Complete Study Notes
1. Introduction to Balanced Trees
A Balanced Tree is a type of binary tree in which the structure is maintained in such a way that
the height difference between left and right subtrees remains small, ensuring efficient
operations.
A balanced tree prevents the tree from becoming skewed (linked-list like structure)
and maintains logarithmic height.
1.1 Why Balance is Important?
If a binary search tree becomes skewed:
10
\
20
\
30
\
40
This behaves like a linked list, making operations:
• Search → O(n)
• Insert → O(n)
• Delete → O(n)
Balanced trees solve this problem by maintaining:
Height ≈ log n
2. Characteristics of Balanced Trees
A tree is considered balanced if:
• Height difference of subtrees is small
• Operations remain efficient (O(log n))
• Tree remains approximately symmetric
• No extreme skewing occurs
Page 1 of 8
, Balanced Trees & AVL Trees | Data Structures & Algorithms
3. Types of Balanced Trees
There are several types:
3.1 AVL Tree
• Strictly balanced BST
• Balance factor is maintained
3.2 Red-Black Tree
• Loosely balanced
• Used in libraries (STL maps/sets)
3.3 B-Trees
• Used in databases and file systems
Focus: In this lecture, we focus on AVL Trees (most important for exams)
4. AVL Trees (Adelson-Velsky and Landis Tree)
4.1 Definition
An AVL Tree is a self-balancing Binary Search Tree where:
For every node, the difference between heights of left and right subtrees is at most 1.
4.2 Balance Factor
Balance Factor (BF) is defined as:
BF = Height(Left Subtree) - Height(Right Subtree)
4.3 Condition for AVL Tree
A tree is AVL if:
• BF = -1, 0, or +1 → Balanced
• BF < -1 or > +1 → Unbalanced
Page 2 of 8
Balanced & AVL Trees
Introduction to Balanced and AVL Trees
Data Structures & Algorithms — Complete Study Notes
1. Introduction to Balanced Trees
A Balanced Tree is a type of binary tree in which the structure is maintained in such a way that
the height difference between left and right subtrees remains small, ensuring efficient
operations.
A balanced tree prevents the tree from becoming skewed (linked-list like structure)
and maintains logarithmic height.
1.1 Why Balance is Important?
If a binary search tree becomes skewed:
10
\
20
\
30
\
40
This behaves like a linked list, making operations:
• Search → O(n)
• Insert → O(n)
• Delete → O(n)
Balanced trees solve this problem by maintaining:
Height ≈ log n
2. Characteristics of Balanced Trees
A tree is considered balanced if:
• Height difference of subtrees is small
• Operations remain efficient (O(log n))
• Tree remains approximately symmetric
• No extreme skewing occurs
Page 1 of 8
, Balanced Trees & AVL Trees | Data Structures & Algorithms
3. Types of Balanced Trees
There are several types:
3.1 AVL Tree
• Strictly balanced BST
• Balance factor is maintained
3.2 Red-Black Tree
• Loosely balanced
• Used in libraries (STL maps/sets)
3.3 B-Trees
• Used in databases and file systems
Focus: In this lecture, we focus on AVL Trees (most important for exams)
4. AVL Trees (Adelson-Velsky and Landis Tree)
4.1 Definition
An AVL Tree is a self-balancing Binary Search Tree where:
For every node, the difference between heights of left and right subtrees is at most 1.
4.2 Balance Factor
Balance Factor (BF) is defined as:
BF = Height(Left Subtree) - Height(Right Subtree)
4.3 Condition for AVL Tree
A tree is AVL if:
• BF = -1, 0, or +1 → Balanced
• BF < -1 or > +1 → Unbalanced
Page 2 of 8
