Splay, skip list ve treap

Splay tree erişilen düğümü zig, zig-zig veya zig-zag rotation'larıyla root'a taşır. Her işlem worst-case doğrusal olabilir; işlem dizisi üzerinde amortize O(log n) sınırı vardır. Yakın zamanda erişilen öğelere uyum sağlaması onu cache ile ilişkilendirir ama LRU eviction politikasını kendiliğinden uygulamaz.

Skip list sıralı bağlı listenin üstüne rastgele yükseklikli hızlı şeritler ekler. En üstten sağa git, hedefi aşacaksa aşağı in. Bağımsız geometrik yüksekliklerle beklenen logarithmic maliyet ve doğrusal alan elde edilir; worst-case garanti değildir. Rastgele seed testlerde tekrar üretilebilirliği sağlar.

Treap anahtarda BST, rastgele priority'de heap invariant'ı tutar. Rotation, split ve merge ile sıralı küme işlemleri yapılır. Priority'lerin anahtardan bağımsız olması beklenen denge için önemlidir. İmplicit treap sıra indeksini subtree size'dan üretir; reverse gibi lazy işlemler için tag yayılımı gerekir. Bu yapıların farklı garantilerini tek “dengeli tree” etiketi altında gizleme.

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)