[prev] 129 [next]

Summary

  • Binary search tree (BST) data structure
  • Tree traversal
  • Tree operations
    • insertion, join, deletion, rotation
    • tree partition, rebalancing
  • Self-adjusting trees
    • Splay trees
    • AVL trees
    • 2-3-4 trees
    • Red-black trees

  • Suggested reading (Sedgewick):
    • BSTs … Ch. 12.5-12.6
    • rotation, partition, deletion, join … Ch. 12.8-12.9
    • self-adjusting trees … Ch. 13.1-13.4