Anasayfa » Algoritmalar, Veri Yapıları

Kırmızı – Siyah Ağaç Yapıları ( Red – Black Trees)

2 Aralık 2011 7.019 kez okundu 7 yorum
1 Star2 Stars3 Stars4 Stars5 Stars (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.

  1. Her node ya kırmızı ya siyahtır.
  2. Her yaprak (leaf)  ve root siyahtır.
  3. Eğer bir node kırmızı ise iki çocuğuda siyahtır.
  4. 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.
  1. Eklenen elemanın root olması durumu,
  2. Eklenen elemanın ebeveyninin siyah olması durumu,
  3. Eklenen elemanın ebeveyninin ve amcasının kırmızı olması durumu,
  4. Eklenen elemanın ebeveyninin kırmızı amcasının siyah olması ve kendisinin sağ çocuk ebeveyninin sol çocuk olması (veya tam tersi) durumu,
  5. 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:
void insert_case1(struct node * n)
{
	if(n->parent==NULL)
		n->color='B';
	else
		insert_case2(n);
}
Durum2:
void insert_case2(struct node * n)
{
	if(n->parent->color =='B')
		return;
	else
		insert_case3(n);
}
Durum3:
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);
}
Durum4:
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);
}
Durum5:
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);
}
Ayrıca ebeveyni ve dedesini bulan algoritmalar;
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;
}
Ş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.

<<< Önceki:

Sonraki: >>>


Facebookta Paylaş

7 yorum »

  • *_* dedi ki:

    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?

  • admin dedi ki:

    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
    }

  • yusuf dedi ki:

    Merhaba ;
    Red and Black Tree javascript uygulamasını nasıl yapabilirim?

  • admin dedi ki:

    yusuf, sorduğunuz soru çok genel, daha özel bir soru sorarsanız yardımcı olabilirim. (Örneğin javascriptte sağ sol kolları nasıl tasarlayabilirim)

  • Fatih GÖKÇE dedi ki:

    İ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.

  • nauru dedi ki:

    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…..

  • yaman dedi ki:

    Tebrikler Müthiş bir Anlatım..

Yorum Bırakın!

Yorum yaz, yada kendi sitende trackback (Geri besleme) olarak ekle. Ayrıca RSS ile bu konuya üye olabilirsin. .

Nazik olun. Temiz tutun. Konu dışına çıkmayın. Spam yaratmayın.

Bu tagları kullanabilirsiniz:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Bloğumuz gavatarı desteklemektedir. Kendi gavatarınızı edinmek için lütfen Gravatar a üye olun.