Self-Balancing Binary Search Tree

Binary Search Trees can become unbalanced, which is why different techniques exist to balance them automatically.

Ideally, we want to them to be balanced, i.e. the height of the tree is $O(\log n)$

Types of Balanced Search Trees

• AVL Trees Adel’son-Velsii and Landis 1962
• B-Trees/2-3-4 Trees Bayer and McCreight 1972 (see CLRS 18)
• BB[α] Trees Nievergelt and Reingold 1973
• Red-black Trees CLRS Chapter 13
• (A) — Splay Trees Sleator and Tarjan 1985 (current research topic, see 6.854 (Advanced Algorithms) and 6.851 (Advanced Data Structures))
• (R) — Skip Lists Pugh 1989
• (A) — Scapegoat Trees Galperin and Rivest 1993
• (R) — Treaps Seidel and Aragon 1996

(R) = use random numbers to make decisions fast with high probability (A) = “amortized”: adding up costs for several operations $\to$ fast on average