Efficient Trees : AVL Tree
Efficient trees, particularly balanced trees like AVL trees, are crucial in computer science for maintaining fast search, insertion, and deletion operations. Unlike unbalanced binary search trees, which can degrade to linear time complexity in worst-case scenarios (e.g., a sorted insertion sequence), balanced trees guarantee logarithmic time complexity for these operations.
Drawback of Binary Search Tree
The primary drawback of a standard Binary Search Tree is its potential for imbalanced growth. This occurs when elements are inserted (or deleted) in a way that skews the tree, causing it to resemble a linked list rather than a balanced tree.
In the worst-case scenario of an imbalanced BST, the search time complexity deteriorates to O(n), equivalent to a linear search, negating the benefits of a tree structure. This is why self-balancing algorithms, such as those used in AVL trees, are essential for maintaining efficient search, insertion, and deletion operations, typically O(log n) time complexity.
Balanced Trees
A balanced tree maintains a specific height-balancing property, preventing it from becoming skewed. This balance ensures efficient operations regardless of the input data sequence. Various types of balanced trees exist, each with its own balancing strategy. AVL trees, named after their inventors Adelson-Velsky and Landis, are one of the earliest and most widely known types of balanced binary search trees
AVL Trees
An AVL tree is a binary search tree with the following additional property: for every node, the height difference between its left and right subtrees is at most 1. This height difference is known as the balance factor of a node, and it can be -1, 0, or 1 in a valid AVL tree.
An AVL tree is a self-balancing binary search. When an insertion or deletion causes this balance factor to exceed 1, rotations are performed to restore balance.
How to computer balance Factor of a node.
In an AVL Tree, the Balance Factor (BF) of a node is computed as:
BF = Height of Left Subtree − Height of Left Subtree.
Steps to Compute the Balance Factor:
- Find the height of the left subtree.
- Find the height of the right subtree.
- Subtract the right subtree height from the left subtree height.
Example of an imbalanced AVL Tree:
A
\
B
\
B
- Height of Left Subtree of A = 0 (no left child).
- Height of Right Subtree of A = 2 (B → C).
- Balance Factor of A = 0 – 2 = -2 (imbalanced because |BF| > 1).
General Rules for AVL Tree:
- BF = -1, 0, or 1 → The node is balanced.
- BF < -1 or BF > 1 → The node is imbalanced and requires rotation.
When an insertion or deletion causes this balance factor to exceed 1, rotations are performed to restore balance. There are four types of rotations: Left Rotation (RR imbalance), Right Rotation (LL imbalance), Left-Right Rotation (LR imbalance), and Right-Left Rotation (RL imbalance).
1. Left Rotation (RR Imbalance)
This rotation is performed when a node becomes unbalanced due to an insertion in the right subtree of its right child.
Example:
Consider the following AVL tree:
30
/ \
20 40
/ \
35 50
- Insert 55 into the tree.
- The tree becomes imbalanced at node 30 (balance factor = 2).
- Perform a Left Rotation on node 30.
30
/ \
20 40
/ \
35 50
\
55
After Rotation:
40
/ \
30 50
/ \ \
20 35 55
2. Right Rotation (LL Imbalance)
This rotation is performed when a node becomes unbalanced due to an insertion in the left subtree of its left child.
Example:
Consider the following AVL tree:
30
/ \
20 40
/ \
10 25
- Insert 5 into the tree.
- The tree becomes imbalanced at node 30 (balance factor = 2).
- Perform a Right Rotation on node 30.
30
/ \
20 40
/ \
10 25
/
5
After Rotation:
20
/ \
10 30
/ / \
5 25 40
3. Left-Right Rotation (LR Rotation- LR Imbalance)
This rotation is performed when a node becomes unbalanced due to an insertion in the right subtree of its left child. It involves two steps:
- Perform a Left Rotation on the left child.
- Perform a Right Rotation on the imbalanced node.
Example:
Consider the following AVL tree:
30
/ \
20 40
/ \
10 25
- Insert 22 into the tree.
- The tree becomes imbalanced at node 30 (balance factor = 2).
- Perform a Left Rotation on node 20, then a Right Rotation on node 30.
30
/ \
20 40
/ \
10 25
/
22
First left rotation : on 20.
30
/ \
25 40
/
20
/ \
10 22
Second right rotation on 30.
After Rotation:
25
/ \
20 30
/ \ \
10 22 40
4. Right-Left Rotation (RL Rotation- RL Imbalance)
This rotation is performed when a node becomes unbalanced due to an insertion in the left subtree of its right child. It involves two steps:
- Perform a Right Rotation on the right child.
- Perform a Left Rotation on the imbalanced node.
Example:
Consider the following AVL tree:
30
/ \
20 40
/ \
35 50
- Insert 33 into the tree.
- The tree becomes imbalanced at node 30 (balance factor = 2).
- Perform a Right Rotation on node 40, then a Left Rotation on node 30.
30
/ \
20 40
/ \
35 50
/
33
First perform right rotationon 40 ;
30
/ \
20 35
/ \
33 40
\
50
Then perform left rotation on 30.
After Rotation:
35
/ \
30 40
/ \ \
20 33 50
