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
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:
- 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.
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
- 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.
- Pfaff, Ben (June 2004). "Performance Analysis of BSTs in System Software" (PDF). Stanford University. 10 Ekim 2012 tarihinde kaynağından arşivlendi. http://web.archive.org/web/20121010045127/http://www.stanford.edu/~blp/papers/libavl.pdf.
- Okasaki, Chris. "Red-Black Trees in a Functional Setting" (PS). 7 Mart 2012 tarihinde kaynağından arşivlendi. http://web.archive.org/web/20120307074747/http://www.eecs.usma.edu/webs/people/okasaki/jfp99.ps.
| |||||||||||||||||||||||||||