Atlama Listeleri

Sıralı bir dizide ikili arama $O(\log n)$’dir: ortadaki elemana doğrudan sıçranabilir. Sıralı bir bağlı listede aynı arama $O(n)$ kalır, çünkü sıçrama yoktur — ortadaki elemana ulaşmak için tüm bağların izlenmesi gerekir.

Atlama listesi (skip list), bağlantılı yapıyı korurken sıçramayı geri getirir. Yöntemi, listenin üzerine seyrek katmanlar eklemektir.

Katman Fikri

Bir demiryolu hattı düşünün: her istasyonda duran hat, birkaç istasyonda bir duran hızlı hat ve yalnızca büyük duraklarda duran ekspres hat. Uzak bir istasyona giderken önce ekspresle mümkün olduğunca yaklaşılır, sonra alt hatlara inilir.

Atlama listesi aynı düzendir. En alt katman tüm elemanları içeren sıralı bağlı listedir. Üstündeki her katman, bir alttakinin elemanlarının bir kısmını taşır. Arama en üst katmandan başlar:

1. Bulunduğun katmanda, bir sonraki eleman hedeften küçük olduğu sürece ilerle.
2. İlerleyemiyorsan bir katman aşağı in.
3. En alt katmanda dur; aranan eleman, o noktadaki bir sonraki elemandır ya da yoktur.

Her katman elemanların yaklaşık yarısını taşıyorsa, katman sayısı $\log_2 n$ olur ve her katmanda ortalama sabit sayıda adım atılır. Beklenen arama maliyeti bu nedenle $O(\log n)$’dir.

Yükseklik Nasıl Belirlenir

Katmanların düzenli tutulması gerekseydi — her ikinci eleman bir üst katmanda, her dördüncü eleman iki üst katmanda — ekleme ve silme, tüm yapıyı yeniden düzenlemeyi gerektirirdi. Bu, dengeli ağaçların çözdüğü problemin aynısıdır ve benzer karmaşıklıkta kod demektir.

Atlama listesinin çözümü farklıdır: her yeni eleman kendi yüksekliğini rastgele seçer. Yaygın kural, arka arkaya yazı gelen para atışı sayısıdır — eleman en az bir katmanda bulunur; olasılığın yarısıyla ikinci katmana, dörtte biriyle üçüncüye çıkar.

Sonuç, katman doluluklarının ortalamada istenen orana yakın çıkmasıdır. Hiçbir yeniden dengeleme yapılmaz; yapı kendiliğinden dengeli kalır.

Bedeli, güvencenin türüdür. Kötü bir rastgelelik dizisinde tüm elemanlar tek katmanda kalabilir ve arama $O(n)$’e düşebilir. Bu olasılık eleman sayısı büyüdükçe hızla azalır ama sıfır değildir. Atlama listesi beklenen maliyet güvencesi verir, en kötü durum güvencesi vermez.

Ayrım önemlidir: en kötü durum güvencesi isteyen sistemler dengeli ağaçları seçer.

Aramanın Gösterimi

Aşağıdaki yapı, yükseklikleri örnek olsun diye elle verilmiş bir atlama listesidir. Rastgelelik yerine sabit yükseklikler kullanmak, aramanın nasıl yürüdüğünü tekrarlanabilir biçimde göstermeye yarar.

class AtlamaDugumu:
    def __init__(self, deger: int, yukseklik: int) -> None:
        self.deger = deger
        self.ileri: list = [None] * yukseklik      # her katman için bir bağ


def liste_kur(elemanlar: list[tuple[int, int]], ust: int) -> AtlamaDugumu:
    """(değer, yükseklik) çiftlerinden sıralı atlama listesi kurar."""
    bas = AtlamaDugumu(-1, ust)                    # sınır düğümü
    son = [bas] * ust                              # her katmanın son düğümü
    for deger, yukseklik in elemanlar:
        dugum = AtlamaDugumu(deger, yukseklik)
        for k in range(yukseklik):
            son[k].ileri[k] = dugum
            son[k] = dugum
    return bas


def ara(bas: AtlamaDugumu, hedef: int, ust: int) -> tuple[bool, int]:
    """Hedefi arar; (bulundu, atılan adım sayısı) döndürür."""
    dugum = bas
    adim = 0
    for k in range(ust - 1, -1, -1):               # en üst katmandan aşağı
        while dugum.ileri[k] is not None and dugum.ileri[k].deger < hedef:
            dugum = dugum.ileri[k]                 # aynı katmanda ilerle
            adim += 1
        adim += 1                                  # bir katman aşağı in
    aday = dugum.ileri[0]
    return (aday is not None and aday.deger == hedef), adim


UST = 3
elemanlar = [(7, 3), (12, 1), (14, 2), (18, 1), (25, 3), (30, 1), (42, 2)]
bas = liste_kur(elemanlar, UST)

print(ara(bas, 30, UST))     # (True, 5)
print(ara(bas, 13, UST))     # (False, 5)
print(ara(bas, 7, UST))      # (True, 3)

30 değeri aranırken üst katmandaki 25 düğümüne tek adımda ulaşılır; alt katmanlara inildiğinde geriye yalnızca birkaç eleman kalmıştır. Aynı arama tek katmanlı sıralı bir listede, altı bağ izlemeyi gerektirirdi.

İkinci çağrı, listede bulunmayan bir değeri arar ve aynı yolu izler; arama başarısız olsa da maliyet aynı mertebededir.

Ekleme ve Silme

Ekleme, aramanın kendisidir: her katmanda durulan son düğüm kaydedilir, yeni düğümün yüksekliği belirlenir ve o yükseklik kadar katmanda bağlar yeniden yazılır. Beklenen maliyet yine $O(\log n)$’dir.

Silme aynı biçimde yürür; düğümün bulunduğu her katmanda bağ atlanır.

Dikkat çekici olan, hiçbir işlemin yeniden dengeleme içermemesidir. Dengeli ağaçlarda ekleme sonrası uygulanan dönme işlemleri burada yoktur; denge, olasılıktan gelir. Bu, atlama listesinin kodunun dengeli ağaçlardan belirgin biçimde kısa olmasının nedenidir.

İkinci pratik üstünlük eşzamanlılıktadır: değişiklikler yerel olduğu için, birden çok iş parçacığının aynı yapı üzerinde çalışması dengeli ağaçlara göre daha az kilitleme gerektirir. Bazı veritabanı ve bellek içi depo gerçekleştirimlerinde sıralı dizin yapısı olarak seçilmesinin nedeni budur.

Katman Sayısının Sınırlanması

Yükseklik rastgele seçildiğinde, kuramsal olarak çok yüksek bir düğüm üretilebilir. Gerçekleştirimler bu nedenle bir üst sınır koyar: katman sayısı, beklenen eleman sayısının logaritması dolayında sabitlenir.

Sınırın etkisi ihmal edilebilir. Bir elemanın $k$ katmana çıkma olasılığı $2^{-k}$ mertebesinde olduğundan, milyon elemanlık bir yapıda yirmi katmanın üzerine çıkma olasılığı yok denecek kadar küçüktür. Sınır, yalnızca bellek düzenini öngörülebilir tutar: her düğümün taşıyabileceği en fazla bağ sayısı bilinir.

İkinci pratik ayrıntı, üst sınırın veri büyüklüğüne göre seçilmesidir. Çok küçük seçilirse katmanlar doygunlaşır ve arama doğrusala yaklaşır; çok büyük seçilmesinin maliyeti ise yalnızca birkaç boş bağdır. Bu asimetri nedeniyle sınır, cömert seçilir.

Olasılıksal Veri Yapıları

Atlama listesi, daha geniş bir ailenin ilk örneğidir: olasılıksal veri yapıları. Ortak özellikleri, kesin güvence yerine olasılıksal güvence vermeleri ve karşılığında daha basit veya daha ucuz olmalarıdır.

Aile, üyeliği yanlış pozitif olasılığıyla sınayan süzgeçleri ve tekil eleman sayısını küçük bellekle kestiren sayıcıları da içerir. Bu yapılar, kesin yanıtın gerekmediği veya maliyetinin kabul edilemez olduğu ölçeklerde kullanılır ve veri yoğun sistemlerin tasarımında ayrı bir konudur.

Maliyet Tablosu

Yapı	Arama	Ekleme	Silme	Güvence
Sıralı dizi	$O(\log n)$	$O(n)$	$O(n)$	Kesin
Sıralı bağlı liste	$O(n)$	$O(1)$*	$O(1)$*	Kesin
Atlama listesi	$O(\log n)$	$O(\log n)$	$O(\log n)$	Beklenen

* Konum elde tutuluyorsa.

Özet

• Sıralı bağlı listede ikili arama yapılamaz; atlama listesi, üzerine seyrek katmanlar ekleyerek sıçramayı geri getirir.
• Arama en üst katmanda ilerler, ilerleyemeyince bir alt katmana iner; katman sayısı logaritmiktir.
• Yükseklik her eleman için rastgele seçilir; böylece yeniden dengeleme gerekmez.
• Verilen güvence beklenen maliyettir, en kötü durum değildir; kesin güvence isteyen sistemler dengeli ağaçları seçer.
• Kodun kısalığı ve eşzamanlılıkta daha az kilitleme gerektirmesi, yapının pratik üstünlükleridir.
• Atlama listesi, olasılıksal veri yapıları ailesinin bir üyesidir.

Sonraki Adım

Bu konu boyunca arama, en iyi durumda logaritmik kaldı: eleman sayısı büyüdükçe maliyet büyümeye devam ediyor. Oysa bir değerin nerede saklandığı, değerin kendisinden hesaplanabilirse arama tek adıma inebilir. Sonraki konu, bu fikri kuran karma tablolarını ve fikrin sınırlarını ele alacak.