Skip List
William Pugh, 1990
O(log n) expectedIntroduced by William Pugh (1990), skip lists use randomized tower heights so searches can hop quickly along upper levels then descend—similar expected performance to balanced trees with simpler code.
William Pugh, 1990
O(log n) expectedIntroduced by William Pugh (1990), skip lists use randomized tower heights so searches can hop quickly along upper levels then descend—similar expected performance to balanced trees with simpler code.