Kırmızı – Siyah Ağaç Yapıları ( Red – Black Trees)
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.)
- 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,
void insert_case1(struct node * n) { if(n->parent==NULL) n->color='B'; else insert_case2(n); } |
void insert_case2(struct node * n) { if(n->parent->color =='B') return; else insert_case3(n); } |
void insert_case3(struct node * n) { struct node * u = uncle(n), *g; if(u!=NULL && u->color == 'R') { n->parent->color = 'B'; u->color = 'B'; g = grandparent(n); g->color = 'R'; insert_case1(g); } else insert_case4(n); } |
void insert_case4(struct node * n) { struct node * g = grandparent(n); if((n==n->parent->right)&&(n->parent==g->left)) { rotate_left(n->parent); n = n->left; } else if((n==n->parent->left)&&(n->parent==g->right)) { rotate_right(n->parent); n = n->right; } insert_case5(n); } |
void insert_case5(struct node * n) { struct node * g = grandparent(n); n->parent->color='B'; g->color='R'; if((n==n->parent->left) && n->parent==g->left ) rotate_right(g); else rotate_left(g); } |
struct node * grandparent (struct node * n) { if(n!=NULL && n->parent!=NULL) { return n->parent->parent; } else return NULL; } struct node * uncle (struct node * n) { struct node * g = grandparent(n); if(grandparent == NULL) return NULL; else if(n->parent==g->left) return g->right; else return g->left; } |

Bunlara da Göz Atmak İsteyebilirsiniz.
<<< Ö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
İstatistikler
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