Lecture: Binary Trees (Part 2)

Review of Binary Trees

• Binary Tree Structure: Each node has:
  • An item stored
  • A left pointer to another node
  • A right pointer to another node
  • A parent pointer
• Tree Example:
  • B and C are A's children (root is A)
  • Height: Length of the longest downward path (edges counted)
  • Height of the entire tree is the height of the root node.

Operations and Traversal

• Operations in Order H Time:
  • Subtree insert, delete, first, and last
  • Compute predecessor and successor nodes
• Traversal Order:
  • Implicit order defined recursively:
    • Traverse left subtree
    • Output the root
    • Traverse right subtree
  • Example order: F, D, B, E, A, C

Improving Efficiency

• Goal: Convert operations to run in Order log n Time
• AVL Trees: Introduce height balance to ensure H = log n
• Set Data Structure:
  • Maintain traversal order in increasing key order
  • Efficiently perform find and predecessor, successor operations

Maintaining Sequence Order

• Sequence Binary Trees:
  • Maintain order for sequence operations like insert at
• Search Algorithm:
  • Based on subtree sizes to find the node at index I.

Subtree Augmentation

• Subtree Properties:
  • Properties computed from the node’s left and right children
  • Example: Size of a node’s subtree
• Maintain Properties Efficiently:
  • Update properties using a downward-looking algorithm on changes

Rotation Operations

• Preserving Traversal Order:
  • Use rotations to rebalance trees
• Right and Left Rotations:
  • Transformations that maintain traversal order
  • Useful for tree balance maintenance

AVL Tree Structure

• Height Balance Property:
  • Difference in height between left and right subtrees is at most one
• Ensuring Logarithmic Height:
  • Maintain height balance through rotations
• Maintaining Balance:
  • Check and correct tree balance post-insertions or deletions

Balancing Using Rotations

• Imbalance Correction:
  • Identify and correct lowest out-of-balance node
• Cases for Rotations:
  • Case 1 & 2: Simple single rotation
  • Case 3: Requires a double rotation

Conclusion

• Through augmentation and rotations, AVL trees maintain balance
• Operations run efficiently in O(log n) time