Yazan : Şadi Evren ŞEKER

Lütfen dikkat: Özellikle 147 adet yazımı kopyalayan ve hiçbir mailime cevap vermeyen is34.net sitesi yöneticisi başta olmak üzere, yazılarımı kopyalayan site yöneticileri. Emek ve vakit harcayarak ürettiğim yazılarımı lütfen kopyalamayınız. Şayet bu tip yazıları üreten insanların emeğini basit bir iki tıklama ile kopyalayarak web yayıncılığı yaptığınızı düşünüyorsanız, ve telif hakları yasasına saygınız yoksa, ve içerik üreten insanları bu işten bezdirmek istiyorsanız yaptığınız hırsızlığa devam ediniz, ancak bundan sonra yazılarımın izinsiz bir şekilde kopyalanması durumunda hukuki işlem başlatacağımı belirtmek isterim.

Bilgisayar bilimlerinde, veriyi ağaçta (tree) tutarken, ağacın dengeli (balanced) olmasını sağlayan bir algoritmadır. Algoritma, veriyi tutuş şekli sayesinde, arama, ekleme veya silme gibi temel işlemlerin en kötü durum analizi (worst case analysis) O(logn)’dir, yani algoritma n elman için bu işlemleri en kötü O(logn) zamanda yapmaktadır.

Kırmızı-siyah ağaçlar (red-black trees) tanım itibariyle ikili arama ağaçlarıdır (binary search tree) ve bu anlamda, herhangi bir düğümün solunda kendisinden küçük ve sağında ise büyük verilerin durması beklenir. Ağaçta ayrıca her düğüm için bir renk özelliği tutulur. Yani bir düğüm kırmızı veya siyah renk özelliği taşıyabilir. Ağaçtaki düğümlerin taşıması gereken bu özellikler aşağıdaki şekilde sıralanabilir:

1. Ağaçtaki her düğüm kırmızı ya da siyahtır
2. Kök düğüm (root node) her zaman için siyahtır.
3. Bütün yaprak düğümler (leaf nodes) siyahtır
4. Herhangi bir kırmızı düğümün bütün çocukları siyahtır.
5. Herhangi bir düğümden, yaprak düğüme kadar gidilen bütün yollarda eşit sayıda siyah düğüm bulunur.

Yukarıdaki bu kurallar ışığında, herhangi bir düğümden, yapraklara kadar olan yolun, gidilebilecek en kısa yolun iki mislinden kısa olduğu garanti edilebilir. Diğer bir deyişle, ağacın aynı seviyedeki düğümleri aynı renktir. Ayrıca ağaçtaki renklendirme kökten başlayarak, siyah – kırmızı – siyah – kırmızı sıralamasıyla değişmektedir.

Örneğin aşağıdaki ağacı ele alalım:

Yukarıda görülen örnek ağaçta, kök düğüm siyah, yapraktaki boş düğümler (null) siyah ve bu düğümler dışındaki her düğümün çocukları, kendisinin ters rengindedir. Örneğin kırmızı olan 13 düğümünün çocukları siyah, siyah olan 25 düğümünün çocukları ise kırmızıdır. Bu anlamda kutu ile gösterilen yaprak düğümler göz ardı edilirse, aynı seviyedeki düğümler aynı renkte olmaktadır.

Arama işlemi (search)

Ağaç üzerinde bir değerin aranması, ikili arama ağacında (binary search tree) gibi yapılır. Yani aranan değer önce kök düğümde (root node) aranır, şayet aranan değer daha büyükse sağa, küçükse sola devam edilir. Nihayetinde aranan değer bulunana veya boş (null) değere ulaşılana kadar bu işlem devam eder.

Ekleme işlemi (insertion)

Ağaca bir düğümün nasıl eklendiğini algoritmasal olarak aşağıdaki şekilde açıklayabiliriz:

Ekleme işlemi normal bir ikili arama ağacına (binary search tree) ekler gibi başlar. Bu işlem sırasında yeni düğümün kırmızı olacağını kabul ederiz.

Ekleme işlemi sırasında uyulması gereken 3 temel kural vardır:

• Kök düğüm (root node) her zaman için siyahtır.
  
• Herhangi bir düğümden, yapraklara kadar uzanan herhangi bir yolda, eşit sayıda siyah düğüm bulunur.
  
• Bir kırmızı düğümün, kırmızı çocuğu bulunamaz.
  

Yukarıdaki istenmeyen durumlardan birisi oluştuğunda, ağaçtaki düğümlerin rengi değiştirilir ya da değiştirilemiyorsa ağaçta dengelemek için döndürme (rotation) işlemi yapılır.

Örneğin, yukarıdaki şekilde gösterildiği üzere 16 sayısını ağaca eklemek isteyelim.

16 değeri, 17′den küçük olduğu için, klasik bir ikili arama ağacında hareket eder gibi , ağacın sol tarafında devam edilecek ve 13 ile karşılaştırılacak.

13′ten büyük olduğu için sağa bakılıyor. Ve 15′ten de büyük olduğu için 15′in sağına ekleniyor.

Görüldüğü üzere yeni eklenen 16, 15′ten büyük ve sağındaki boş yere yerleştirilmiştir. Bu yerleştirme sonucunda iki ardışık kırmızı durumu oluşmadığı için sorun yoktur. Yani bir siyah düğüm altına kırmızı düğüm eklenmiştir. Şimdi örnek olarak sırasıyla 30 ve 32 sayılarını ekleyelim.

Ağaca yukarıdaki şekilde 30 değeri eklenince, ağacın en sağına yerleşmekte ve istenmeyen bir durum olan iki kırmızı arka arkaya gelmektedir. Çözüm olarak ağaçtaki düğümlerin rengi değiştirilmelidir.

Öncelikle, 30′un hemen üzerinde bulunan 27 düğümü, iki kırmızı düğüm arka arkaya olamayacağı için siyaha çevrilir. Siyaha çevrilen 27 numaralı düğümün büyük babası 23 numaralı düğümdür. Dolayısıyla 27 numaralı düğümün amcası 18 numaralı düğüm olur. 25 numaralı düğümün kırmızıya çevrilmesi, 23 numaralı büyük baba için problem oluşturur çünkü bir kırmızı düğümün çocukları siyah olmalıdır. Aynı zamanda problem 17 numaralı düğümden yaprağa kadar giden yolda da eşit miktarda siyah düğüm bulunmalıdır. Yukarıdaki örnekte 23 numaralı düğümün siyah kalması durumunda, 17 numaralı düğümden gidilebilen sağ yol ile sol yol arasında düğüm sayıları farklı olmaktadır.

Çözüm olarak 17 numaralı düğüm kırmızı yapılabilir ancak bu durumda da kök düğümün kırmızı olamayacağı kuralı ile ihtilafa düşülür. Dolayısıyla bu adımda çözüm 13 ve 23 numaralı düğümlerin siyah yapılmasıdır.

Ağacın çalışma şeklini daha iyi anlayabilmek için ağaca bir de 32 değerinde bir düğüm eklemeyi deneyelim:

Yukarıdaki örnekte görüldüğü üzere, 32 değeri, bir önceki adımda eklediğimi 30 değerinin sağına gelmektedir. Hemen dikkat edilebilecek bir problem, 30-32 ikilisinin arka arkaya kırmızı olmasıdır. Bu durumda 30 düğümünün siyah yağılması veya 32 düğümünün siyah yapılması problemi çözmez çünkü kökten yapraklara kadar giden yolda eşit sayıda siyah düğüm bulunmalıdır. Bu yola yeni bir siyah düğüm eklenmesi bu dengeyi bozar. Çözüm olarak saat yönünün tersine döndürme işlemi uygulanıp çocukların siyah yapılması gerekir. Bu durumu aşağıdaki şekil üzerinden açıklamaya çalışalım:

Yukarıdaki 2 problem bulunuyor:

1. İki kırmızı düğüm arka arkaya
   
2. Yolda tek siyah düğüm bulunmasına izin verilmiş, yapraklara kadar giden ikinci bir siyah düğüm çıkarma hakkımız yok.
   

Yukarıdaki yeni halinde, kural bozulmaksızın hem tek siyah ile yaprağa ulaşılıyor hem de iki kırmızı ihlalinden kurtulunuyor.

Benzer bir çözüm aşağıdaki şekilde olabilirdi:

Ancak yukarıdaki bu yeni halimiz ağacın bütünüyle uyuşmamaktadır. Yani döndürme işleminin yapıldığı ağacın üst düğümü 25 olduğu ve kırmızı olduğu için bu ikinci çözüm yeni bir kırmızı kırmızı komşuluğu doğuracaktır. Dolayısıyla ilk örnekte olduğu gibi problemi çözebiliriz:

Yukarıdaki yeni halimizde kuralların tamamına uyarak ağaca yeni sayıyı eklemiş bulunuyoruz. Benzer bir durumu oluşturup daha yukarıdan döndürme (rotation) işleminin nasıl yapıldığını, ağaca 29 sayısını ekleyerek görebiliriz. Bakın 29 sayısı eklenince de yapılan işlem aslında aynıdır sadece daha büyük bir döndürme işlemi gerçekleştirilmiş olacaktır:

İki kırmızı durumu oluşuyor. Bu noktada artık ikisinden birisinin siyah olması sorunu çözmez çünkü yaprağa kadar olan yolda her halükarda bir fazla siyah düğüm oluşur.

Çözüm olarak sırasıyla kırmızı-siyah dönüşümü yapıyoruz:

Görüldüğü üzere köke kadar giden yolda kırmızı-kırmızı durumunu engellemek için düğümler bir kırmızı bir de siyah sırasına dönüştürüldü. Şimdi problem 23 numaralı düğümün sağ ve sol taraflarındaki yol uzunluğunun farklı olması. Yani 23 numaralı düğümün sol tarafındaki problem çözülürse 17 numaralı düğüm için bir problem yok

Döndürme işlemi gerçekleştiriyoruz:

Yukarıda görüldüğü üzere 25 numaralı düğüm23 ve 30 numaralı düğümler arasındayken, bu düğümlerin atası durumuna geçmiştir.