Anasayfa » Algoritmalar, Veri Yapıları

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

2 Aralık 2011 14.663 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:
?View Code C
void insert_case1(struct node * n)
{
	if(n->parent==NULL)
		n->color='B';
	else
		insert_case2(n);
}
Durum2:
?View Code C
void insert_case2(struct node * n)
{
	if(n->parent->color =='B')
		return;
	else
		insert_case3(n);
}
Durum3:
?View Code C
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:
?View Code C
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:
?View Code C
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;
?View Code C
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.

Bunlara da Göz Atmak İsteyebilirsiniz.

<<< Ö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?

    # 3 Aralık 2011 saat 13:13
  • 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
    }

    # 3 Aralık 2011 saat 14:45
  • yusuf dedi ki:

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

    # 14 Mart 2012 saat 11:09
  • 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)

    # 14 Mart 2012 saat 15:53
  • 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.

    # 12 Kasım 2014 saat 22:40
  • 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…..

    # 28 Kasım 2014 saat 10:43
  • yaman dedi ki:

    Tebrikler Müthiş bir Anlatım..

    # 2 Haziran 2015 saat 22:50

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.