Splay trees, skip lists and treaps

Splay trees move an accessed node to the root using zig, zig-zig or zig-zag rotations. Individual operations may be linear, while sequence costs are amortised O(log n). Adaptation to recent access does not automatically implement LRU eviction.

Skip lists add random-height express lanes over an ordered list. Traverse right until overshooting, then descend. Independent geometric heights give expected logarithmic operations and linear space, not worst-case guarantees.

Treaps combine BST key order with heap order on random priorities. Rotations, split and merge support ordered operations. Priorities must be independent of keys for expected balance. Implicit treaps derive positions from subtree sizes and need correct lazy-tag propagation for sequence edits.

from random import Random
rng = Random(42)
def random_height():
    h = 1
    while rng.random() < 0.5: h += 1
    return h
heights = [random_height() for _ in range(8)]
assert all(h >= 1 for h in heights)