İkili Ağaçlar (Binary Trees)

Veri yapılarında , algoritmalarda kullanılan ikili ağaçların özelliği kendisine bağlanacak elamanların sayısının en fazla iki olmasıdır. Her eleman düğüm(node) olarak ifade edilir.Başlangıç düğümüne(root,kök) eklenen elemanlar daha anlaşılır olması bakımından sol çoçuk ve sağ çoçuk olarak ifade edilir.İkili ağaç yapısı elemanlara erişmekte dizilerde kullanılan indis kavramı yerine bağlı listeleri kullanır.Her öğe kendisinden sonra gelenlerin adreslerini tutarak diğer elemanlara ulaşmayı mümkün kılar.

Bilinmesi gereken kavramlar:
Yol(Path):Kökten ,ulaşılması istenen düğüme giderken geçilen düğüm listesi.
Derinlik(Depth): İstenilen düğümün köke olan uzaklığı. Kökün derinliği sıfırdır.
Yükseklik(Height):Bulunulan düğümden itibaren kendisi altında kalan en son düğümle arasında kalan uzaklık.

İkili ağaç örnekleri:

Örnek-1

Örnek-2

Örnek-3

İkili ağaçlarda tüm elemanları ziyaret etmek için kullanılacak yöntemler:

Preorder : ilk kök ziyaret edilir ,sonra sol çoçuk en sonunda da sağ çoçuk ziyaret edilir.

Inorder :İlk sol çoçuk ,sonra kök en son ise sağ çoçuk ziyaret edilir. 

Postorder : İlk sol çoçuk sonra sağ çoçuk en sonunda ise kök ziyaret edilir.

Daha anlaşılır olması açısından bir örnek üzerinde yukarıdaki ifadelerin uygulanışını gösterelim.

Düğüm(Node)       Derinlik(Depth)      Yükseklik(Height)

    A                                  0                                 3

    B                                  1                                 2

    C                                  1                                 2 

    D                                  2                                 1

    E                                   2                                 0

    F                                   2                                 0

    G                                  2                                 1

    H                                  3                                 0

    K                                  3                                 0

Preorder   : A,B,D,H,E,C,F,G,K

Inorder     : H,D,B,E,A,F,C,G,K

Postorder  : H,D,E,B,F,K,G,C,A

İkili ağaçlar herhangi bir elemanı arama,max ve min elemanı bulma, sıralama vb. işlemlerinde oldukça kullanışlıdır. Yakın zamanda paylaşılacak olan örnek C++ kodu üzerinde bunu inceleyeceğiz.


İkili ağaçlarda ,yukarıda gösterilen örnek ağaç yapılarında olduğu gibi , ekleme ve silme işlemleri esnasında farklı türlerde ikili ağaç yapıları oluşabilir. Bizim için en önemli olan, daha iyi bir performans sağlaması açısından, her zaman ikili ağaçları dengeli olarak tutabilmektir.
Dengeli ikili ağaçlar(Balanced binary trees) :Kökün sağ en alt tarafında kalan düğümün derinliği ile sol en alt tarafında kalan düğümün derinliği arasındaki farkın 1 ve 1 den küçük olması ile gerçekleşir.

Bu durumu Örnek 1 üzerinde açıklayalım.
a)Kökün sağ tarafında kalan düğümler : C,F,G,K
b)Kökün sol tarafında kalan düğümler : B,D,E,H

Buna göre sol en altta kalan H düğümü ile sağ en altta kalan K düğümü arasındaki fark sıfır olduğundan bu dengeli bir ağaçtır.

Örnek 3 de ise
c)Kökün sağ tarafında kalan düğümler : kökün sağ tarafında kalan düğüm olmadığından A'yı alıyoruz.
d)Kökün sol tarafında kalan düğümler : B,C,D,E

A'nın derinliği 0 ,sol en altta kalan E düğümünün derinliği 4 olduğundan bu ağaç dengeli değildir.

Dengeli ağaçlar :

1) Complete Binary Tree
2) AVL Trees
3) Red-Black Trees
4) B-Trees