Kırmızı – Siyah Ağaç Yapıları ( Red – Black Trees)
2 Aralık 2011
15.368 kez okundu
7 yorum
(1 oy,5 üzerinden : 5,00 )
Loading...
(1 oy,5 üzerinden : 5,00 )Loading...
Bu yazımda sizlere red black tree lerden yani kırmızı siyah diye adlandırılan ağaç yapılarından bahsedeceğim. Red Black Tree ler aslında binary search tree yapısıdır. Binary search treelerden tek farkı, extradan her nodun rengini tutan yapının olmasıdır. Bu renkler isimden de anlaşılacağı gibi kırmızı veya siyahtır.
Red black tree ler dengeli ağaçlardır. Bu yüzden en kötü zamanda bile n elemanlı bir ağaca ekleme, silme arama gibi işlemler O(logn) zamanda yapılabilir.
Her nodun bildiğimiz gibi değeri, sağ çocuğu, sol çocuğu, ebeveyni (parent) ve rengi vardır. Ayrıca red black treelerde yapraklar nill dir.
Red Black Tree lerin 4 maddelik özelliği vardır.
- Her node ya kırmızı ya siyahtır.
- Her yaprak (leaf) ve root siyahtır.
- Eğer bir node kırmızı ise iki çocuğuda siyahtır.
- Belli bir node üzerinden başlamak kaydıyla, yapraklara giden tüm yollardaki siyah node sayısı eşittir. (Bu özelliğe black height (siyah yüksekliği) denebilir.)
Bu yazımda sizlere arama (search) ve ekleme (insertion) işlemlerini göstereceğim.
SEARCH (ARAMA)
Arama işlemi aynı binary search tree lerdeki gibi yapılır. Aranan node şu anki noddan büyükse sağa küçükse sol çocuğa gidilerek devam eder. Ya istenilen değere ulaşılır ya da null geldiği için arama sonucunda herhangi bir şey bulunamaz. En basit işlemlerdendir.
INSERTION (EKLEME)
Insertion işlemini 5 durumda inceleyeceğiz.
- Eklenen elemanın root olması durumu,
- Eklenen elemanın ebeveyninin siyah olması durumu,
- Eklenen elemanın ebeveyninin ve amcasının kırmızı olması durumu,
- Eklenen elemanın ebeveyninin kırmızı amcasının siyah olması ve kendisinin sağ çocuk ebeveyninin sol çocuk olması (veya tam tersi) durumu,
- Eklenen elemanın ebeveyninin kırmızı amcasının siyah olması ve kendisinin ve ebeveyninin beraber sol çocuk olması (veya tam tersi) durumu,
Şimdi bu 5 durum için algoritmalar yazacağız.
Durum1:
Durum2:
Durum3:
Durum4:
Durum5:
Ayrıca ebeveyni ve dedesini bulan algoritmalar;
Şimdi bir örnek üzerinden gidelim. 3 – 5 – 7 – 12 -8 ekleyelim.
3 ekiyoruz:
1. durum geçerli root olduğu için siyah yapıyoruz.
5 ekliyoruz:
2.durum, ebeveyni siyah olduğu için öylece bırakıyoruz.
7 ekliyourz:
5.durum, ebeveyn kırmızı amcası (nill) siyah ayrıca node ebeveynin sağında, ebeveyn de dedenin sağında. Yani tek sıra halindeler gibi(dede baba çocuk doğrusal) düşünülebilir. Bu durumda 5.durumu uyguluyoruz yani ebeveyni siyah dedeyi kırmızı yapıyoruz ve ebeveyn üzerinde left rotation uyguluyoruz.
12 ekliyoruz:
3.durum geçerli yani ebeveyni ve amcası kırmızı olma durumu. Bu durumda ebeveyni ve amcayı siyah yapıp dedeyi kırmızı yapıyoruz.
Ardından birinci durumu dede için çağırıyoruz. Birinci durumda dede root olduğu için siyah yapıyoruz.
8 ekliyoruz:
4.durum geçerlidir yani ebeveyn kırmızı, amca siyah (nill) kendisi sol çocuk ebeveyni dedenin sağ çocuğu (yani dede,baba,çocuk doğrusal değil). Bu durumda ebeveyn üzerinde right rotate yapıyoruz.
Ardından 5.durumu node ile çağırıyoruz. Yani 8 ile. 5.durumda ebeveyni red amcası siyah, kendisi sağ çocuk, ebeveyni de dedesinin sağ çocuğu (doğrusal). Bu durumda ebeveyni siyah, dedeyi kırmızı yapıyoruz. Ardından dede üzerinde left rotate yapıyoruz.
Bu sayede tüm durumları kullanmış olduk. Buradan red black tree lerin c kaynak kodunu bulabilirsiniz.
Bunlara da Göz Atmak İsteyebilirsiniz.
Rica: Sitemizin Google'da daha üst sıralarda çıkması için lütfen alttaki Google+ veya Begen butonuna tıklayınız , ya da yazılarımızı Facebookta Paylaş butonu ile paylaşabilirsiniz.
Yazılarımızı okuyan okurlarımızın yorumlarını bizimle paylaşmaları, bizi daha çok yazı yazmaya teşvik edecektir. Lütfen yorumlarınızı, görüşlerinizi, eleştirilerinizi bizden esirgemeyin.
<<< Önceki: Csharp ile Ms Access Veritabanı Bağlantısı
Sonraki: Csharp Delegate (Temsilci ) Kullanımı >>>
Ben java’da red black tree insert metodu yazmaya çalışıyorum. Tree’nin bir elemanına onun sağ ve sol çocuğunu ve parentını nasıl anlatacağımı bilmiyorum, yardımcı olabilir misiniz?
Eğer her node nesne tipinde olacaksa, ki büyük ihtimal öyle yapıyorsun. sağ,sol çocuk ve parent aynı kendisi gibi nesne tipinde olması gerekiyor. Ben buradan csharp örneğini vereyim, java halide çok benzer olacaktır. En azından fikir oluşturur.
private class Node {
// Fields
private T item; // Generic object held by each node
private Node left, right, parent; // Links to children and parent
private bool red = true; // Color of node
// Constructor
public Node(T item, Node parent) {
this.item = item;
this.parent = parent;
left = right = null;
}
// Properties
public Node Left {
get {
return left;
}
set {
left = value;
}
}
public Node Right {
get {
return right;
}
set {
right = value;
}
}
public Node Parent {
get {
return parent;
}
set {
parent = value;
}
}
// Similar get/set properties for Item and Red
}
Merhaba ;
Red and Black Tree javascript uygulamasını nasıl yapabilirim?
yusuf, sorduğunuz soru çok genel, daha özel bir soru sorarsanız yardımcı olabilirim. (Örneğin javascriptte sağ sol kolları nasıl tasarlayabilirim)
İyi günler. Ben bu 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.
c#’ ta N ve M (thread sayısı) sayı degerlerini girip 1 den N e kadar tüm sayıların toplamını thread ile hesaplayıp M, N ve t (run time) ı kullanarak 3 boyutlu bir grafik çizdiren programı nasıl yazabilirim??? Yardımcı olabilir misiniz…..
Tebrikler Müthiş bir Anlatım..
Yorum Bırakın!
En Son Yazılanlar
Codeigniter Dersleri
Kategoriler
Teknoloji Haberleri
Android Dersleri
Arşiv
Sitemizin QR Kodu
Yeniliklerden İlk Sizin Haberiniz Olsun
KodMerkezi.Net Facebookta
En Çok Okunanlar
En Son Aranan Kelimeler
En Çok Oy Alanlar
Etiket Bulutu
İlginizi Çekecek Siteler
Arşiv
Yönetim
En Son Yapılan Yorumlar
En Çok Okunanlar