Skip list nedir ve O(log n) aramasını nasıl başarır?

Question

Accepted Answer

A **skip list**, birden fazla **"express lane"** seviyesiyle arttırılmış sıralı bir bağlı listedir. Daha yüksek seviyeler birçok düğümü atlar, bu nedenle arama aşağı iner ve sağa hareket eder, **O(log n)** beklenen zaman elde eder — dengeli bir ağaca göre daha basit, olasılıksal bir alternatif gibi. ## Yapı ```text L3: head ------------------------> 30 -------> NIL L2: head ----------> 17 ---------> 30 -------> NIL L1: head ----> 9 --> 17 --> 25 --> 30 --> 42 -> NIL L0: head -> 3->9->12->17->25->30->39->42 ----> NIL (full list) ``` Her düğüm, `p` olasılığı (genellikle 0.5) ile daha yüksek seviyelere yükseltilir, bu nedenle ortalama olarak her seviyenin altındaki seviyeden yarı kadar düğümü vardır. ## Arama ```text search(25): start top-left, move RIGHT while next <= target, else drop DOWN a level. Repeat to level 0. ``` ```python import random def random_level(p=0.5, max_level=16): lvl = 1 while random.random() < p and lvl < max_level: lvl += 1 # coin flips decide a node's height return lvl ``` ## Karmaşıklık | İşlem | Beklenen | Alan | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## Dengeli ağaçlara karşı ödünleşmeler - **Güçlü taraflar:** red-black/AVL'den uygulanması çok daha basit; dönüş yok; kolay eşzamanlı sürümler (Redis sıralanmış kümelerinde, Java `ConcurrentSkipListMap` içinde kullanılır). - **Zayıf taraflar:** olasılıksal garantiler (en kötü durum değil); düğüm başına ekstra işaretçiler. ## Neden önemli Skip lists, çok daha az kod ve kolay kilit içermeyen eşzamanlılık ile ağaca benzer O(log n) sıralı işlemler sağlar, bu nedenle Redis gibi gerçek sistemler bunları seçer. Bunlar, karmaşık deterministik dengeleme mantığını değiştirmek için **randomizasyonu** kullanmanın harika bir örneğidir.