Fri Jun 27 06:35:35 PM +08 2025#0

The idea of balancing a search tree is due to Adel’son-Vel’skiĭ and Landis, who introduced a class of balanced search trees called AVL trees in 1962. Another class of search trees, called 2-3 trees, was introduced by J. E. Hopcroft in 1970. A 2-3 tree maintains balance by manipulating the degrees of nodes in the tree. Bayer and McCreight later generalized 2-3 trees to form B-trees. Red-black trees were invented by Bayer under the name symmetric binary B-trees. Guibas and Sedgewick studied their properties in detail and introduced the red/black color convention. Andersson proposed a simpler-to-code variant of red-black trees, which Weiss later called AA-trees. An AA-tree is similar to a red-black tree except that left children may never be red. Treaps were proposed by Seidel and Aragon. They became the default implementation of a dictionary in LEDA, a well-known collection of data structures and algorithms. Other variations on balanced binary trees include weight-balanced trees, k-neighbor trees, and scapegoat trees. One of the most intriguing is the splay tree introduced by Sleator and Tarjan, which is self-adjusting. Splay trees maintain balance without any explicit balance conditions. Instead, splay operations involving rotations are performed within the tree every time an access is made. The amortized cost of each operation on an n-node tree is logarithmic. Skip lists provide an alternative to balanced binary trees. A skip list is a linked list augmented with additional pointers, allowing dictionary operations to run in expected logarithmic time.