AVL Trees Lecture Notes

1. Introduction to Binary Search Trees (BST)

• Definition: A binary search tree is a binary tree in which each node has a key, and for any node:
  • All elements in the left subtree are smaller.
  • All elements in the right subtree are greater.
  • Example: For node 30, elements are arranged as follows:
    • Left: 10, 20
    • Right: 40, 50

2. Searching in BST

• Process: Start from the root and make comparisons to find a key.
  • If key < current node, go left.
  • If key > current node, go right.
  • Performance: Time complexity depends on the height of the tree:
    • Minimum height: log n (balanced tree)
    • Maximum height: n (linear, unbalanced tree)
  • Drawback: Search may require multiple comparisons, especially in unbalanced trees.

3. Drawbacks of Binary Search Trees

• Height Control: Height is not controlled, leading to:
  • Poor performance in unbalanced trees (similar to linear search).
  • Different Structures: Same keys can create different BST shapes:
    • Example: Inserting keys in varying orders leads to different heights.

4. Improvement over BSTs

• AVL Trees: Introduced to maintain balanced height.
  • Rotations: To maintain balance, perform rotations on nodes that become unbalanced after insertions.
    • Types of Rotations:
      • Single Rotations: LL (Left-Left) and RR (Right-Right).
      • Double Rotations: LR (Left-Right) and RL (Right-Left).

5. AVL Tree Characteristics

• Definition: An AVL tree is a height-balanced binary search tree.
  • Balance Factor: Defined as height of left subtree - height of right subtree.
    • AVL trees maintain balance factors in the range of -1, 0, 1 for all nodes.
  • Balancing: When any node's balance factor is outside this range (-2 or +2), rotations are performed.

6. Types of Rotations

• LL Rotation: Used when there’s a left-left imbalance.
  • RR Rotation: Used when there’s a right-right imbalance.
  • LR Rotation: Used when there’s a left-right imbalance (requires two steps).
  • RL Rotation: Used when there’s a right-left imbalance (requires two steps).

7. Creating an AVL Tree

• Procedure: Insert keys one by one while maintaining balance:
  1. Insert 40 → Balanced.
  2. Insert 20 → Balanced.
  3. Insert 10 → Imbalance detected, perform LL rotation.
  4. Continue inserting and checking balance factors, performing rotations as necessary.
  • Example Insertion Sequence:
    • 40, 20, 10, 25, 30, 22, 50 → Maintain balance after each insertion.

8. Performance of AVL Trees

• Height: AVL trees generally maintain height around 1.44 * log n, ensuring quicker search times compared to unbalanced BSTs.
  • Efficiency: Searching, inserting, and deleting operations remain efficient with time complexity of O(log n).*

9. Comparison with Red-Black Trees

• Red-Black Trees: Another type of balanced binary search tree.
  • Differences: Less strict balancing rules than AVL trees, resulting in fewer rotations.
  • Both AVL and Red-Black trees are efficient but are used in different contexts depending on performance needs.

Conclusion

• AVL trees provide a self-balancing mechanism for binary search trees, ensuring logarithmic height and efficient operations, making them a valuable data structure for various applications.