Bölüm 10 · Simülasyon

Kırmızı-Siyah Ağaç Simülatörü

← Bölüm 10

Örnek kırmızı-siyah ağaç yüklendi. Bir işlem seçin.

Düğüm0
Düzey sayısı0
Siyah yükseklik0
Döndürme0

İşlem yolu

—

Dengeleme adımları

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

Kırmızı-Siyah Ağaç Simülatörü

Kırmızı-siyah ağaç kendini dengeleyen bir ikili arama ağacıdır. Her düğüm kırmızı ya da siyahtır; boş (NIL) çocuklar siyah yaprak sayılır. Ekleme ve silmeden sonra yeniden renklendirme ve döndürmeler aşağıdaki özellikleri geri getirir; böylece yükseklik O(log n) kalır.

Kullanım

  • Bir tam sayı yazıp Ekle, Ara ya da Sil düğmesine basın. Yol vurgulanır; her yeniden renklendirme ve döndürme dengeleme adımlarında listelenir.
  • Doğrula ikili arama ağacı sırasını ve tüm kırmızı-siyah özelliklerini denetler.
  • Örnek yükle, Rastgele ağaç ve Sıfırla ağacı değiştirir; Durdur çalışan animasyonu keser.

Kırmızı-siyah özellikleri

  • Siyah kök: kök her zaman siyahtır.
  • Kırmızı-kırmızı yok: kırmızı düğümün kırmızı çocuğu olamaz.
  • Eşit siyah yükseklik: bir düğümden NIL yapraklara giden her yolda aynı sayıda siyah düğüm bulunur.

Ekleme onarımı

Yeni düğüm kırmızı eklenir. Ebeveyni de kırmızıysa amcaya (ebeveynin kardeşi) bakılır:

  • Amca kırmızı: ebeveyn ve amca siyaha, büyük ebeveyn kırmızıya boyanır; denetim büyük ebeveynden yukarı sürer.
  • Amca siyah, üçgen: ebeveynde yapılan döndürme, üçgeni düz çizgiye çevirir (çift döndürmenin ilk adımı).
  • Amca siyah, düz çizgi: büyük ebeveynde döndürme yapılır; ebeveyn siyah, büyük ebeveyn kırmızı olur.
  • Sonunda kök kırmızıysa siyaha boyanır.

Silme onarımı

İki çocuklu düğümün yerine kök ortada ardılı kopyalanır. Kaldırılan düğüm kırmızıysa özellik bozulmaz; siyahsa ve kırmızı çocuğu varsa çocuk siyaha döner. Aksi hâlde yerine geçen düğüm çift siyah olur ve kardeşe göre onarılır:

DurumKardeşİşlem
Durum 1KırmızıYeniden renklendirme, ebeveynde döndürme; Durum 2–4'e geçilir.
Durum 2Siyah, çocukları siyahKardeş kırmızıya boyanır, çift siyah yukarı çıkar.
Durum 3Siyah, uzak çocuk siyahKardeşte döndürme; Durum 4'e geçilir.
Durum 4Siyah, uzak çocuk kırmızıYeniden renklendirme, ebeveynde döndürme; onarım biter.