1) Define AVL Trees. Explain its four rotation types. Explain AVL tree with an example. Give worst case efficiency of operations on aviary construct an avail tree of the list of keys 5683247 indicating each step of key insertion and rotation
Answer:
An AVL tree is a binary search tree in which the balance factor of every node—defined as the difference between the heights of the node’s left and right subtrees—is either 0, +1, or −1.
(The height of an empty tree is defined as −1. The balance factor can also be computed as the difference between the number of levels in the left and right subtrees.)
The binary search tree in Figure 6.2(a) is an AVL tree, but the one in Figure 6.2(b) is not.
Rotations
If the insertion of a new node makes an AVL tree unbalanced, the tree is restored by a rotation. A rotation is a local transformation applied to a subtree rooted at the node where the balance factor becomes either +2 or −2.
If multiple such nodes exist, the rotation is performed at the lowest (i.e., closest to newly inserted node) unbalanced node.
There are four types of AVL rotations, of which two are mirror images of the other two.
Four types of rotation:
1. Single Right Rotation (R-Rotation)
Performed when a node becomes unbalanced due to insertion in the left subtree of its left child.
2. Single Left Rotation (L-Rotation)
This is the mirror image of the R-rotation. It is performed when a node becomes unbalanced due to insertion in the right subtree of its right child.
Note: The general diagram for L-rotation is left for exercise.
3. Double Left-Right Rotation (LR-Rotation)
This is a combination of:
- A single L-rotation on the left child, followed by
- A single R-rotation on the node itself.
It is performed after inserting into the right subtree of the left child of the unbalanced node.
4. Double Right-Left Rotation (RL-Rotation)
This is the mirror of the double LR-rotation and is performed after insertion in the left subtree of the right child of the unbalanced node. [Left for exercise in the textbook.]
When tracing the operations, remember: If there are multiple nodes with balance factors of ±2, the rotation is applied to the lowest such node (closest to the newly inserted leaf).
Efficiency of AVL Trees
The critical factor in AVL tree performance is its height. It is mathematically proven that the height h of an AVL tree with n nodes satisfies:
log₂(n) ≤ h < 1.4405 * log₂(n + 2) − 1.3277
These constants are derived from the golden ratio and Fibonacci numbers.
- This implies that search and insertion operations take O(log n) time in the worst case.
- The average height for an AVL tree created from random keys is approximately:
1.01 * log₂(n) + 0.1
This means searching in an AVL tree is almost as efficient as binary search in a sorted array.
Deletion in AVL Trees
- Deletion is more complex than insertion but still takes O(log n) time.
- It may also require rotations to restore balance.
Drawbacks of AVL Trees
Despite their efficiency, AVL trees come with some drawbacks:
- Frequent rotations during insertions and deletions.
- Additional overhead in maintaining balance factors for each node.
These issues have prevented AVL trees from being the default choice for dictionary implementations.
However, the core idea of rebalancing through rotations has inspired many other tree structures like Red-Black Trees, Splay Trees, and B-Trees.