Bölüm 10 · Simülasyon

Splay Ağacı Simülatörü

← Bölüm 10

Örnek splay ağacı yüklendi. Bir işlem seçin.

Düğüm0
Düzey sayısı0
Kök—
Döndürme0

Erişim yolu

—

Splay adımları

  1. Henüz splay adımı yok.

Splay Ağacı Simülatörü

Splay ağacı kendini düzenleyen bir ikili arama ağacıdır. Her ekleme ya da erişim, ilgili düğümü döndürmelerle köke taşır (splay); böylece yakın zamanda erişilen değerlere daha hızlı ulaşılır.

Kullanım

  • Bir tam sayı yazıp Ekle, Ara + splay ya da Sil düğmesine basın. Minimum splay ve Maksimum splay en küçük ya da en büyük anahtarı köke taşır.
  • Erişim yolu ve her zig, zig-zig ve zig-zag adımı sağda listelenir. Doğrula ikili arama ağacı sırasını denetler.
  • Örnek, Rastgele ve Sıfırla ağacı değiştirir; Durdur çalışan animasyonu keser.

Splay ağacı kavramları

  • Başarılı erişim: bulunan düğüm köke taşınır; aynı ya da yakın anahtarlara tekrar tekrar erişildiğinde bu işe yarar.
  • Başarısız arama: aranan değer yoksa son ziyaret edilen düğüm köke taşınır; bu, uygulamada yaygın bir uzlaşımdır.
  • Denge bilgisi tutulmaz: AVL ya da kırmızı-siyah ağaçların aksine splay ağacı yükseklik, denge faktörü ya da renk tutmaz.
  • Amortize garanti: tek bir işlem doğrusal sürebilir, ama bir işlem dizisinin amortize maliyeti logaritmiktir.

Döndürme kalıpları

KalıpDurumDöndürmeler
ZigEbeveyn köktürBir sola ya da sağa döndürme
Zig-zigSol-sol ya da sağ-sağAynı yönde iki döndürme
Zig-zagSol-sağ ya da sağ-solTers yönlerde iki döndürme