Trees and Balancing

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
Last modified: Tuesday, 22 April 2014, 11:27 AM