01
William Pugh and Skip Lists: Balancing Search with Probability
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.
↗