AVL TREES

AVL Tree Overview

• Self-balancing binary search tree.

• Every node has a balance factor (height of left subtree - height of right subtree).

• Balance factors can be -1, 0, or +1 for a balanced tree.

Insertion Procedure

• Insert the node and check the height and balance factor from the inserted node up to the root.

  • Example:

    • Insert 10:

      • Height = 0, Balance Factor = 0.

      • Tree is balanced.

    • Insert 20:

      • Insert to the right of 10.

      • Height of 10 becomes 1 (max(0, 0) + 1). Balance Factor = -1 (0 - 0).

      • Tree is still balanced.

    • Insert 30:

      • Height of 20 becomes 1. Balance Factor of 10 becomes -2 (0 - 1), indicating unbalance.

      • Perform left rotation on node 10.

      • New tree:

        • 20 becomes root, 10 becomes left child, and 30 becomes right child.

      • Update heights and balance factors.

Rotation Scenarios

• Single Rotation (LL):

  • Triggered when the left child has an insertion on its left.

• Single Rotation (RR):

  • Triggered when the right child has an insertion on its right.

• Double Rotation (LR):

  • Triggered when the left child has an insertion on its right.

• Double Rotation (RL):

  • Triggered when the right child has an insertion on its left.

Insertion Example Continued

• Insert 40:

  • Height and balance factors remain valid.

• Insert 35:

  • After insertion, tree becomes unbalanced (balance factor of 30 becomes -2).

  • Perform RL rotation (first right at 30, then left at 20).

  • New Structure:

    • 35 becomes root, 30 as left child, 40 as right child.

Deletion Procedure

• Similar to insertion, check balance after deletion as it might unbalance the tree.

  • Delete Scenarios:

    • Node has no children: simply remove the node.

    • Node has one child: replace the node with its child.

    • Node with two children: replace with inorder successor.

• After deletion, check balance factor from deleted node up to root.

• Perform necessary rotations to restore balance.

Performance Complexity

• Insertion and deletion operations both have a time complexity of O(log n) due to the balanced nature of AVL trees, while a binary search tree can degrade to O(n) in worst-case scenarios when unbalanced.

• Single rotations are O(1), thus overshadowed by the O(log n) complexity of traversing the tree during insertions or deletions.

Conclusion

• AVL trees combine the benefits of binary search trees with the efficiency of balancing to ensure operations happen in logarithmic time.

• Important for scenarios where frequent inserts and deletes occur while maintaining sorted data.