Tag: balanced-trees

Adelson-Velsky and Landis showed in 1962 that a binary search tree could repair its own shape after updates, guaranteeing logarithmic search and insertion through local rotations.

William Pugh’s skip lists replaced rotation-based balancing with randomized levels, offering expected logarithmic search and update performance through a structure that behaves like a hierarchy of linked-list express lanes.

Red-black trees emerged from a lineage that began with Rudolf Bayer’s symmetric binary B-trees and was recast by Leonidas Guibas and Robert Sedgewick as a two-color framework for balanced binary search trees.