Tree Balancing (AVL Tree)

Tree Balancing (AVL Tree)

Why Tree Balancing?

  • BST operations are efficient when the tree is balanced because the operation time is proportional to the path length.
  • Unbalanced BSTs can resemble linked lists, leading to inefficiency due to long path lengths.
  • Balancing BSTs ensures short path lengths and faster search times.

AVL Tree

  • Definition: A binary search tree that maintains balance by ensuring that for each node, the height difference between the left and right subtrees is at most one, i.e., |hL-hR|<2.
  • Conditions:
    • It is a BST (L < C < R).
    • Height balancing condition: |hL-hR|<2.

Tree Balancing Steps

  • Given an unbalanced BST, perform a post-order balancing operation.
  • Check the balancing condition only when a node is visited the third time in post-order traversal.
    • Check if a subtree (e.g., TX) starting from a node (e.g., X) is not balanced, i.e., |hL-hR|>1.
  • For unbalanced sub-tree (e.g. TX), cut short the longest path in order to make |hL-hR|<2.
  • Post-order Traversal:
    • Fix the deepest node that is not balanced first.
    • Check balance or not.
    • Cut short the longest path.

Tree Balancing Operation

  • Classify turnings along the longest path (from node X) as LL, LB, LR, RR, RB, or RL.
  • Disconnect nodes X, Y, and Z (the first 3 nodes along the longest path), and rearrange them to balance the tree.
  • Left Taller Cases:
    • LL, LB, and LR cases.
    • Raise Y up and lower X to cut short the longest path.
    • Reconnect subtrees without changing connection ordering.
  • LR Case:
    • Raise Z up between Y and X.
    • Make Y and X the left and right sons of Z.

Pseudo-code for Balancing

  1. Compute the height for each sub-tree and record it at each root.
  2. Do a post-order tree traversal and process each node, X.
  3. If the height difference of the left-subtree and right- subtree of X is larger than 1.
  4. Then:
    • Label 3 nodes along the longest path as X, Y, and Z.
    • Label 2 links along the longest path using L (left taller) R (right taller) and B(balance), and consider the followings
    • Cases LL or LB, disconnect X and Y from their subtrees, T1, T2, T3 (from left to right). Move Y up to be the parent of X (becomes the right son of Y). Create 3 links, L1, L2, L3 (from left to right) from this new combination.
    • Case LR, disconnect X, Y and Z from their subtrees, T1, T2, T3, T4 (from left to right). Move Z up to be the parent of Y (becomes the left son of Z) and X. Create 4 links, L1, L2, L3, L4 (from left to right) from this new combination.
    • Cases RR or RB, (similar description of LL)
    • Case RL, (similar description of LR)
    • Each operation will need to reconnect back the sub-trees T1, T2, T3 and T4 to Links L1, L2, L3 and L4 correspondingly.

Summary

  • Tree height balancing is crucial for efficient information search in BSTs.
  • An AVL tree is a BST with a balanced height.
  • Unbalanced BSTs must be balanced in a post-order manner by classifying each lowest unbalanced subtree into LL, LB, LR, RR, RB, RL cases and handling each accordingly.