Bölüm 10 · Simülasyon

AVL Ağacı Simülatörü

← Bölüm 10

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

Düğüm0
Yükseklik0
En büyük |DF|0
Döndürme0

İşlem yolu

—

Döndürme geçmişi

  1. Döndürme gerekmedi.

AVL Ağacı Simülatörü

AVL ağacı kendini dengeleyen bir ikili arama ağacıdır. Her düğüm alt ağacının yüksekliğini tutar ve denge faktörü DF = yükseklik(sol) − yükseklik(sağ) her zaman −1, 0 ya da 1 olmalıdır.

Kullanım

  • Bir tam sayı yazıp Ekle, Ara ya da Sil düğmesine basın. Önce yol vurgulanır, sonra dengeyi geri getirmek için gereken her döndürme canlandırılır ve döndürme geçmişine yazılır.
  • Her düğümün altında yüksekliği (h) ve denge faktörü (DF) görünür. Bu simülatörde yükseklik düğüm sayısıyla ölçülür (yaprakta h = 1); notlarda kenar sayısı kullanıldığı için h değerleri bir fazla çıkar, DF değişmez. Doğrula sıralamayı, tutulan yükseklikleri ve dengeyi denetler.
  • Örnek, Rastgele ve Sıfırla ağacı değiştirir; Durdur çalışan animasyonu keser.

AVL kavramları

  • Tutulan yükseklikler: yükseklikler özyinelemeli ekleme ve silmeden sonra ve her döndürmede güncellenir.
  • Tek döndürme: LL dengesizliği sağa döndürmeyle, RR dengesizliği sola döndürmeyle giderilir.
  • Çift döndürme: LR ve RL dengesizliklerinde ağır çocuk ters yöne yattığı için iki döndürme gerekir.
  • Silme sonrası onarım: silme birden çok atayı dengesiz bırakabilir; bu yüzden denge denetimi köke kadar sürer.

AVL değişmezleri

DeğişmezKoşul
İkili arama ağacı sırasıSoldaki değerler küçük, sağdakiler büyüktür.
Doğru tutulan yükseklik1 + max(sol yükseklik, sağ yükseklik)
DengeDenge faktörünün mutlak değeri en çok 1'dir.
Tekrar politikasıTekrarlanan anahtarlar reddedilir.

Yükseklik O(log n) kaldığı için arama, ekleme ve silmenin tümü O(log n) sürer.