Kırmızı-siyah ağaç

Kırmızı-siyah ağaç bilgisayar biliminde bir çeşit kendini-dengeleyen ikili arama ağacı veri yapısıdır. Orijinali ilk olarak 1972 yılında yapıyı "simetrik ikili B-ağaçları" olarak adlandıran Rudolf Bayer tarafından bulunmuştur. Bugünkü ismini 1978 yılında Leo J. Guibas ve Robert Sedgewick tarafından yayımlanan bir makaleyle almıştır. Karmaşık ancak çalışma süresi en kötü durumda bile iyi ve pratikte verimlidir: O(log n) (n ağaçtaki eleman sayısını gösterir) zamanda arama, ekleme ve çıkarma işlemleri yapabilir.

Teknik Terimler

Bir kırmızı-siyah ağaç, bilgisayar biliminde karşılaştırılabilir veri parçalarını (sayılar gibi) organize etmek için kullanılabilen özel bir ikili ağaç türüdür.

Özellikleri

İkili ağaç şekli. Siyah kök düğüm iki kırmızı çocuğa ve dört siyah toruna sahiptir. Torunların çocuk düğümleri ya siyah "boş" göstergelerdir ya da siyah "boş" göstergelere sahip kırmızı düğümlerdir.
Kırmızı-siyah ağaç örneği

Kırmızı-siyah ağaçlar, her düğümün, değeri kırmızı veya siyah olabilen bir renk niteliğine sahip olduğu ikili arama ağacıdır. İkili arama ağaçlarının sahip oldukları gereksinimlerin yanında, şu aşağıdaki ek özelliklere de sahiptirler:

  1. Her düğüm ya kırmızıdır ya da siyah.
  2. Kök düğüm siyahtır. (Bu kural bazı tanımlarda kullanılırken bazılarında kullanılmaz. Kök düğüm her zaman kırmızıdan siyaha değiştirilebileceği, ancak tersi geçerli olmadığı için analizlerde çok az etkisi bulunur.)
  3. Bütün yapraklar siyahtır.
  4. Kırmızı düğümlerin her iki çocuğu da siyahtır.
  5. Bir düğümden atalarına doğru giden tüm basit yollar aynı sayıda siyah düğüm içerir.

Bu kısıtlar kırmızı-siyah ağaçların önemli bir özelliğini zorlar: kökten herhangi bir yaprak düğüme giden en uzun yol, herhangi başka bir yaprağa giden en kısa yolun iki katıdan fazla olamaz. Bunun sonucu olarak ağaç kabaca dengeli olur. Ekleme, silme ve değerleri bulma operasyonlarının en-kötü durum zamanları ağacın boyuyla orantılı olduğundan, boya getirilen bu teorik üst sınır, kırmızı-siyah ağaçların en kötü durumda bile verimli işlemler yapmalarını sağlar. Bu durum ikili arama ağaçlarında geçerli değildir.

Yukarda sayılan özelliklerin kırmızı-siyah ağaçlara bu önemli özelliği kazandırmasının nedenini görmek için, 4. özellikten dolayı herhangi bir yolda iki ardışık kırmızı düğüm olamayacağını görmek yeterlidir. En kısa yol, sadece siyah düğümlerden oluşan bir yoldur, ve en uzun muhtemel yol da kırmızı ve siyah düğümlerin sırasıyla geldiği yoldur. 5. özellikten dolayı tüm uzun (kökten, yapraklara kadar olan) yollar aynı sayıda siyah düğüm içerdiğinden, herhangi bir yolun, bir başka yoldan iki katından daha uzun olamayacağı açıktır.

Referanslar

This article is issued from Vikipedi - version of the 1/6/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.