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

[bullvar_katip]

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 küçükresim|350px|Kırmızı-siyah ağaç örneği|sağ|alt=İ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çlar, her düğümün, değeri kırmızı veya siyah olabilen bir renk niteliğine sahip olduğu İkili 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: Her düğüm ya kırmızıdır ya da siyah. 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.) Bütün yapraklar siyahtır. Kırmızı düğümlerin her iki çocuğu da siyahtır. 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. Yukarıda 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. Kaynakça Bilgisayar Kavramları : Kırmızı Siyah Ağaçları Mathworld: Red-Black Tree San Diego State University: CS 660: Red-Black tree notes , by Roger Whitney Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7 . Chapter 13: Red-Black Trees, pp.273–301. Kategori:İkili ağaçlar Kategori:Kanıt içeren maddeler