Yazan : Şadi Evren ŞEKER
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:
- Ağaçtaki her düğüm kırmızı ya da siyahtır
- Kök düğüm (root node) her zaman için siyahtır.
- Bütün yaprak düğümler (leaf nodes) siyahtır
- Herhangi bir kırmızı düğümün bütün çocukları siyahtır.
- 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:
- İki kırmızı düğüm arka arkaya
- 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.
Hocam son durumda ağaçta 17 -> 13 -> 9 şeklinde gidildiğinde üçüde siyah oluyor. Bu kuralı bozmaz mı?
Hayır olmaz. Bakın kuralları hatırlayalım:
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.
1. kural bozulmuyor çünkü 3 düğümün de siyah olması durumunda düğümlerimiz ya siyah ya da kırmız olmuş oluyor
2. kök düğüm siyah ve kural yine bozulmaz
3. Bahsettiğiniz düğümlerden hiçbiri yaprak değil dolayısıyla bu kuralı da bozan bir durum yok
4. bu kural için de bir durum yok. Yani bu düğümlerden birisi kırmızı olsa, çocukları siyah mı diye kontrol edecektik ama böyle bir durum yok
5. Bu kurala da uyuyor çünkü YAPRAKLARA kadar olan yolda eşit miktarda siyah düğüm bulunuyor. Bakın bu kural, her düğüme kadar olan yol değil, YAPRAKLARA kadar olan yol, dolayısıyla örneğin
17 > 13 > 9 > 6 yolu veya 17 > 25 > 23 > 18 yolunun veya kökten yaprağa kadar olan herhangi başka bir yolun üzerinde hep 3 adet siyah düğüm bulunmaktadır.
Kısacası herhangi bir kural ihlali bulunmuyor.
başarılar
peki ya, son resimde, yaprakların hepsi siyah değil. Haliyle yapraklar siyah olmalıdır kuralıyla çelişmiyor mu? (19 – 29)
Son resimde yaprakların hepsi siyah. Bakın bütün düğümlerin en sonunda Boş düğüm bulunuyor (null) ve bu düğümler siyah kabul ediliyor. Dolayısıyla ağacın yaprak düğümleri (yani son düğümleri, yani boş düğümler) siyah olmuş oluyor ve kurallar ile bir çelişki bulunmuyor.
başarılar
hocam bu algoritmanın c# kodunu nerden tedaik edebilirim?
Ezgi Hanım, sizin için C# kodunu yazıp sitede yayınlamayı çok isterdim ancak şu anki yoğunluğumdan dolayı bunu ağustos ayına kadar ertelemem gerekiyor. Şayet sizin için çok acilse, elinizden geldiği kadarıyla yazıp bana mail atın, hatalarınızı ve eksiklerinizi düzelterek size yardımcı olmaya çalışayım. Sonuçta çıkan kodu da buradan yayınlar herkese faydalı olmaya çalışırız.
başarılar
Yazilariniz gercekten cok mükemmel bir Kaynak!.
Ben Bilgisayar Mühendisiyim fakat Almanya’da okudugum icin, Bilgisayar aleminin dilini türkce olarak da okumak istiyorum.
Ayni zamanda önceden ögrendigim, fakat zamanla unuttugum bir cok bilgiyi de sayenizde tazeliyorum.
Bos zamanlarimi degerlendirmek adina bir tavla programi yazmayi düsünüyorum. Bu konuda sizin yazilariniz da yardimci olacaktir eminim.
Algoritmalari, kücük bir proje (mesela tavla programi veya benzer bir oyun) esliginde islemeniz mümkün olsa, daha da mükemmel olurdu.
Tebrikler ve tesekkürler!
Kemal Cavdar
Sınav öncesi güzel bir kaynak oldu.
Sadece aynı seviyedeki tüm node’ların aynı renk olması gerektiğini düşünüyordum ama değilmiş 🙂 Öğrendiğim iyi oldu.
hocam bir düğümün siyah yükseliğini bulan algoritmayı yazabilir misiniz?
Siyah yükseklik (black height), bir düğümden, bu düğümü saymaksızın yaprağa kadar olan herhangi bir yoldaki siyah düğümlerin (nodes) sayısıdır. En uzun siyah yükseklik, 2*log(n+1) formülü ile bulunur. Kodlama için ikili arama ağacındaki (binary search tree) dolaşma yöntemleri kullanılabilir. Herhangi bir düğüm için sürekli sola giderek siyah yükseklik bulan kod ise aşağıdaki şekilde yazılabilir:
Özyineli (recursive) olarak:
int siyahyükseklik(düğüm x){ if(x==NULL) return 0; if(x->renk == siyah) return 1 + siyahyükseklik (x->sol); return siyahyükseklik (x->sol); }iteratif olarak
int siyahyükseklik (düğüm x){ int say=0; while(x!= NULL){ if(x->renk==siyah) say++; x = x->sol; } return say; }başarılar
merhabalar red black tree de silme işleminin nasıl yapıldığını anlatan bir yer varsa bilgilendirir misiniz ya da keşke onu da anlatsaydınız…
İyi günler. Ben bir uygulamayı red black ağacını ve binary search tree yi ayrı iki program olarak yapıp sonrada aynı verilerle performans karşılaştırması yapmak istiyorum. Bunu Visual Studio da nasıl yapıcam. Yardımı olurmusunuz. Tşklr.
Sitenizi çok beğendim emeğinize sağlık. Bir sorum olacak. n farklı düğüme sahip bir kırmızı-siyah arama ağacında bir ekleme işlemi için kaç anahtar kıyaslaması yapılmalıdır?
Şimdiden teşekkür ederim.
Anahtar kıyaslama sayısı ekleme işlemi tamamlanana kadar kaç anahtara bakılacağıdır. Dolayısıyla dengeli bir iki arama ağacındaki ekleme için gereken eleman bakma sayısı ile aynıdır. Bu değer ise çoğu zaman ağacın derinliği ile aynıdır. Dolayısıyla genel durum için O(log2n)’dir denilebilir.
Ancak daha detaylı bir analiz istiyorsanız, ağacın ilave satır içereceği ve derinliğin log2n değerinden 1 fazla olacağı durumları düşünebilirsiniz. Ayrıca bu durumlarda dengeleme işlemi yapılacağı için ilave bir kaç bakmadan daha bahsedebiliriz ancak sorunuz şayet en kötü durum analizi (worst case analysis) altında bir değer ise kabaca O(logn)’dir denilebilir.
Aşağıdaki yazılar ilginizi çekebilir:
http://www.bilgisayarkavramlari.com/2008/12/22/en-kotu-durum-analizi-worst-case-analysis/
http://bilgisayarkavramlari.sadievrenseker.com/2010/06/17/karmasiklik-siniflari-complexity-classes/