Tag: skip-lists

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.