Trees and Balancing

Bart Massey

• Search Trees

  • Nodes are labeled with ordered values

  • Idea: log time search, insertion, deletion

    • Implements Dynamic-Set ADT

  • Must keep them balanced

  • Lots of freedom: same ordered set is described by many search trees
  • Invariants are enforced to limit that freedom

• Rotation

  • Single rotation - pulls right subtree up and pushes left subtree down
  • Double rotation - pulls some subtrees up, pushes others down

• Balancing

  • Keep height at each node, rotate to level: AVL trees

    • Can get by with two bits if invariant is preserved

  • Keep heights within a factor of two: Red-Black trees

    • One bit. Woohoo

  • Maintain heights implicitly: Splay trees

    • Zero bits

• Red-Black Trees

  • Intuitions:

    • Red children are siblings of black node
    • Black nodes are roots of B-Trees
    • Analogous to 234 trees

  • Algorithms:

    • Insertion
    • Deletion