Bölüm 10 · Simülasyon

İkili Arama Ağacı Simülatörü

← Bölüm 10

Arama / işlem yolu

—

Gezinme sonucu

—

İkili Arama Ağacı Simülatörü

Her düğümde sol alt ağaçtaki tüm değerler düğümden küçük, sağ alt ağaçtakilerin tümü büyüktür. Arama, ekleme, silme, öncül, ardıl, minimum, maksimum ve sıralı gezinme bu sıralama kuralıyla belirlenir.

Kullanım

  • Bir tam sayı yazıp Ekle, Ara, Sil, Öncül ya da Ardıl düğmesine basın; yol boyunca ziyaret edilen düğümler vurgulanır.
  • Gezinme düğmeleri ziyaret sırasını canlandırır ve bu sırayı gezinme sonucu kutusuna yazar.
  • Örnek yükle, Rastgele ağaç ve Sıfırla ağacı değiştirir; Animasyonu durdur çalışan işlemi keser.

İkili arama ağacı kavramları

  • Arama kararları: her düğümde eşitlik aramayı bitirir. Aranan değer küçükse sola, büyükse sağa gidilir.
  • Öncül ve ardıl: öncül, değerden küçük anahtarların en büyüğü; ardıl, değerden büyük anahtarların en küçüğüdür. Bir alt ağaçta ya da atalar arasında bulunabilirler.
  • Silme: yaprak doğrudan kaldırılır; tek çocuklu düğümün yerine çocuğu geçer; iki çocuklu düğüm, sağ alt ağacının minimumunu (kök ortada ardılını) alır.
  • Bozulma: sıralı değerler eklemek bir zincir oluşturur. Ağaç geçerli kalır ama yükseklik ve işlem süresi doğrusal olur.

Gezinme sıraları

GezinmeSıraTipik kullanım
Kök ortada (inorder)Sol, kök, sağDeğerleri sıralı okumak.
Kök önde (preorder)Kök, sol, sağAğaç yapısını serileştirmek ya da kopyalamak.
Kök sonda (postorder)Sol, sağ, kökÖnce alt ağaçları silmek ya da değerlendirmek.
Düzey sırası (level-order)Düzey düzeyAğacı her seferinde bir düzey incelemek.