Bağlı listeler (Linked List), diziler (array), yığınlar (stack) ve kuyruklar (queue) doğrusal veri yapılarıdır. Ağaçlar (tree) ise doğrusal olmayan veri yapılarıdır. Doğrusal veri yapılarında içerideki veri sayısı arttığı zaman bir işlem gerçekleştirme zamanı da doğrudan artar (O(n)). Fakat bu durum ağaçlarda böyle değildir. Ağaçlarda bir hiyerarşi olduğu için özellikle arama işlemleri çok daha kısa sürmektedir (O(logn)). Ağaç yapısının kullanıldığı örnekler:
- İşletim sistemlerindeki klasör hiyerarşisi
- Veri tabanlarında satıların anahtar sütunları için
- Veri sıkıştırma uygulamalarında (Winrar, 7-Zip vs)
- Derleyici tasarımlarında (Syntax Tree)
Ağaçlardaki Temel Kavramlar
Ağaç yapısında kullanılan bir kaç kavram vardır:
- Alt Düğüm: Herhangi bir düğümün altında kalan düğümlerdir. D ve E B’nin Alt Düğümleridir.
- Kök Düğüm: Ağacın en üstündeki düğümdür. A düğümü ağacın Kök Düğümüdür.
- Yaprak Düğümler: Kendilerinden aşağıda herhangi bir düğüm olmayan düğümlerdir. K, L, M, N, O ve P ağacın yaprak düğümleridir.
- Alt Ağaç: Kök olmayan herhangi bir düğüm varolan ağacın alt ağacıdır.
- Ağaç Seviyesi: Kök düğümden en aşağıdaki düğüme kadar geçilen düğüm sayısıdır. Ağacın seviyesi: 5.
Ağaçlardaki Temel İşlemler
Ağaçlar bir nevi bağlı listelere benzeler; bağlı listelerde olduğu gibi burada da bir düğüm (Node) yapısı vardır. Fakat ağaçlarda sonraki düğüm yerine sağ ve sol düğümler bulunur (Genel Olarak). Bundan dolayı da doğrusal bir yapıdan çıkarlar. Ağaçlarda temel olarak 3 işlem vardır:
- Ekleme
- Arama
- Dolaşma
- Pre Order Dolaşma
- In Order Dolaşma
- Post Order Dolaşma
C# ile BST (Binary Search-Tree) Uygulaması
İlk önce düğüm (Node) sınıfını tasarlayalım. Bir düğüm içinde 2 tane düğüm objesi olmalı (Sağ ve Sol Düğümler). Bir tane de değeri tutacağımı değişken. Ben kolay olması açısından tamsayı (int) değerler kullanacağım.
public class Dugum
{
public Dugum SolDugum { get; set; }
public Dugum SagDugum { get; set; }
public int Deger { get; set; }
public Dugum(int Deger)
{
SolDugum = null;
SagDugum = null;
this.Deger = Deger;
}
}
Ağaç yapısında elemanları eklemek için:
Değeri büyük olan sayılar her zaman ağacın sağ tarafında, küçük olanlar ise her zaman sol tarafında olacak şekilde ilerleyeceğiz.
public class Agac
{
private Dugum KokDugum;
public Agac()
{
KokDugum = null;
}
public void DegerEkle(int Deger)
{
if (KokDugum == null)
{
KokDugum = new Dugum(Deger);
return;
}
Dugum tmpDugum = KokDugum;
while (tmpDugum != null)
{
if (Deger > tmpDugum.Deger)
{
if (tmpDugum.SagDugum == null)
{
tmpDugum.SagDugum = new Dugum(Deger);
return;
}
tmpDugum = tmpDugum.SagDugum;
}
else
{
if (tmpDugum.SolDugum == null)
{
tmpDugum.SolDugum = new Dugum(Deger);
return;
}
tmpDugum = tmpDugum.SolDugum;
}
}
}
public int AgacYuksekligi()
{
return AgacYuksekligi(KokDugum);
}
private int AgacYuksekligi(Dugum dugum)
{
return dugum == null ? 0 :
Math.Max(AgacYuksekligi(dugum.SolDugum), AgacYuksekligi(dugum.SagDugum)) + 1;
}
public void PreOrderYazdir()
{
PreOrderYazdir(KokDugum);
}
private void PreOrderYazdir(Dugum dugum)
{
if (dugum == null)
return;
Console.Write($"{dugum.Deger} ");
PreOrderYazdir(dugum.SolDugum);
PreOrderYazdir(dugum.SagDugum);
}
public void PostOrderYazdir()
{
PostOrderYazdir(KokDugum);
}
private void PostOrderYazdir(Dugum dugum)
{
if (dugum == null)
return;
PostOrderYazdir(dugum.SolDugum);
PostOrderYazdir(dugum.SagDugum);
Console.Write($"{dugum.Deger} ");
}
public void InOrderYazdir()
{
InOrderYazdir(KokDugum);
}
private void InOrderYazdir(Dugum dugum)
{
if (dugum == null)
return;
InOrderYazdir(dugum.SolDugum);
Console.Write($"{dugum.Deger} ");
InOrderYazdir(dugum.SagDugum);
}
public bool Ara(int Deger)
{
return Ara(KokDugum, Deger);
}
private bool Ara(Dugum dugum, int Deger)
{
if (dugum == null)
return false;
if (dugum.Deger == Deger)
return true;
else if (Deger > dugum.Deger)
return Ara(dugum.SagDugum, Deger);
else
return Ara(dugum.SolDugum, Deger);
}
}
Şimdi ağaca bir kaç eleman ekleyip nasıl eklendiğine bakalım:
Agac agac = new Agac();
agac.DegerEkle(68);
agac.DegerEkle(43);
agac.DegerEkle(90);
agac.DegerEkle(56);
agac.DegerEkle(44);
agac.DegerEkle(78);
agac.DegerEkle(86);
agac.DegerEkle(31);
agac.DegerEkle(97);
agac.DegerEkle(12);
agac.DegerEkle(63);
agac.DegerEkle(77);
agac.DegerEkle(70);
agac.DegerEkle(27);
agac.DegerEkle(8);
agac.DegerEkle(48);Ağaçta hiç eleman olmadığı için 68 bu ağacın Kök Düğümü oldu.
43 değeri 68 değerinden küçük olduğu için ağacın sol tarafındaki düğüme eklendi.
90 değeri 68 değerinden büyük olduğu için ağacın sağ tarafındaki düğüme eklendi.
56 değeri 68 değerinden küçük olduğu için soldaki düğüme geçtik. Soldaki düğüm boş olmadığı için onun içindeki değer ile karşılaştırdık. 56 değeri 43 değerinden büyük olduğu için 43 düğümünün sağ tarafına ekledik.
44 değeri 68 değerinden küçük olduğu için soldaki düğüme geçtik. Soldaki düğümün değeri olan 43 değerinden büyük olduğu için onun sağındaki düğüme geçtik. 56 değerinden de küçük olduğu için onun sol düğümüne ekledik.
78 değeri 68 değerinden büyük olduğu için sağdaki düğüme geçtik. Sağdaki düğümün değeri olan 90 değerinden küçük olduğu için 90 düğümünün sol tarafına ekledik.
86 değeri 68 değerinden büyük olduğu için sağdaki düğüme geçtik. Sağdaki düğümün değeri olan 90 değerinden küçük olduğu için soldaki düğüme geçtik. Soldaki düğümün değeri olan 78 değerinden büyük olduğu için 78 düğümünün sağ tarafına ekledik.
Geri kalan değerler içinde aynı algoritmayı uyguladığımızda da aşağıdaki ağacı elde etmiş olacağız:
BST Üzerinde Değer Aramak
BST üzerinde bir değer aramak için değer eklermiş gibi düğümler arasında dolaşabiliriz. Mesela 63 değerini arayalım:
63 değeri 68 değerinden küçük olduğu için soldaki düğüme geçtik. 63 değeri 43 değerinden büyük olduğu için sağdaki düğüme geçtik. 63 değeri 56 değerinden büyük olduğu için sağdaki düğüme geçtik. Ve 63 düğümünü bulmuş olduk.
Bir de olmayan bir değer için arama yapalım. Mesela 37 değerini arayalım:
37 değeri 68 değerinden küçük olduğu için soldaki düğüme geçtik. 37 değeri 43 değerinden küçük olduğu için soldaki düğüme geçtik. 37 değeri 31 değerinden büyük olduğu için sağdaki düğüme geçtik. Fakat sağında bir düğüm olmadığından dolayı 37 değeri bu ağaçta yoktur diyebiliriz.
BST Üzerinde Gezinmek
Pre Order Dolaşma Mantığı:
Düğümdeki değeri yaz. Sol alt ağacı Pre Order mantığına göre dolaş. Sağ alt ağacı Pre Order Mantığına göre dolaş. Kolay yol olarak elinizi kök düğüme koyup dışarıdan doğru gezerek uğradığınız her düğümü yazmanız. Bu mantığa göre yukarıdaki ağacın Pre Order Çıktısı:
68 43 31 12 8 27 56 44 48 63 90 78 77 70 86 97
Post Order Dolaşma Mantığı:
Sol alt ağacı Post Order mantığına göre dolaş. Sağ alt ağacı Post Order mantığına göre dolaş. Düğümdeki değeri yaz. Bu mantığa göre yukarıdaki ağacın Post Order Çıktısı:
8 27 12 31 48 44 63 56 43 70 77 86 78 97 90 68
In Order Dolaşma Mantığı:
Sol alt ağacı In Order mantığına göre dolaş. Düğümdeki değeri yaz. Sağ alt ağacı In Order mantığına göre dolaş. Bu mantığa göre yukarıdaki ağacın In Order Çıktısı:
8 12 27 31 43 44 48 56 63 68 70 77 78 86 90 97
Yazımı okuduğunuz için teşekkür ederim, umarım yardımcı olabilmişimdir.