İkili ağaçlar nedir, ikili arama ağaçları nedir, bu ağaçlarda dolaşma algoritmaları hangileridir, hangisi sıralı çıkış verir?

Bilgisayar bilimlerinde yer alan önemli veri yapılarından bir tanesi de ağaçlardır. Ağaç yapılarını önemli yapan özellikler:

·         Esneklik: Tek bir amaç için en iyi çözüm ağaç yapısı olmasa da, çoklu çözümler için ağaç yapısının esnekliği bu yapının avantajı olarak sayılabilir.

·         Etkili Arama: Arama sırasında ağacın bazı dalları budanarak arama yapılması performans artışı sağlar ve bu da verimliliği arttırır. Ağaç yapısı genellikle bilginin istenilen bölümüne konumlanmak için genellikle filtreleme aracı olarak kullanılır.

·         Doğal Temsil: Bilgiyi temsil etmenin doğal bir yoludur.

·         Ağaç yapısı bir uygulamayı bazen daha kolay uygulanabilir bir hale dönüştürür.

Bağlı listeler, yığıtlar ve kuyruklar doğrusal (linear) veri yapılarıdır. Ağaçlar ise doğrusal olmayan belirli niteliklere sahip iki boyutlu veri yapılarıdır (Şekil 1). Ağaçlardaki düğümlerden iki veya daha fazla bağ çıkabilir. İkili ağaçlar (binary trees), düğümlerinde en fazla iki bağ içeren (0,1 veya 2) ağaçlardır. Ağacın en üstteki düğümüne kök (root) adı verilir.

 

Şekil 1 : Bir ikili ağacın grafiksel gösterimleri

Şekil 1'de görülen ağacın düğümlerindeki bilgiler sayılardan oluşmuştur. Her düğümdeki sol ve sağ bağlar yardımı ile diğer düğümlere ulaşılır. Sol (leftptr) ve sağ (rightptr) bağlar boş ("NULL" = "/" = "\") da olabilir. Düğüm yapıları değişik türlerde bilgiler içeren veya birden fazla bilgi içeren ağaçlar da olabilir. Doğadaki ağaçlar köklerinden gelişip göğe doğru yükselirken veri yapılarındaki ağaçlar kökü yukarıda yaprakları aşağıda olacak şekilde çizilirler.

Şekil 2'deki ağaç, A düğümü kök olmak üzere 9 düğümden oluşmaktadır. Sol alt ağaç B kökü ile başlamakta ve sağ alt ağaç da C kökü ile başlamaktadır. A'dan solda B'ye giden ve sağda C'ye giden iki dal (branch) çıkmaktadır.

 

Şekil 2 : Ağaçlarda düzeyler

 Tanımlar (Örnekler Şekil 2'ye göre verilmiştir) :

1)      İkili Ağaç (Binary Tree) : Sonlu düğümler kümesidir. Bu küme boş bir küme olabilir (empty tree). Boş değilse şu kurallara uyar.

i) Kök olarak adlandırılan özel bir düğüm vardır.

ii)                 Her düğüm en fazla iki düğüme bağlıdır.

iii)               Kök hariç her düğüm bir daldan gelmektedir.

iv)               Tüm düğümlerden yukarı doğru çıkıldıkça sonuçta köke ulaşılır.

2)      Düğüm (node) : Ağacın her bir elemanına düğüm adı verilir. Örnekler : A, B, C.

3)      Kök (root) : Düzey 0'daki (şemanın en üstündeki) tek düğüm. Örnek : Şekil 2'de A bilgisini içeren düğüm.

4)      Çocuk (child) : Bir düğümün sol ve sağ bağı aracılığı ile bağlandığı düğümler o düğümün çocuklarıdır. Örnek : B ve C, A'nın çocuklarıdır.

5)      Parent : Bir düğüm, sağ ve sol bağları ile bağlandığı düğümlerin parent'ıdır. A düğümü, B ve C düğümlerinin parent'ıdır.    

6)      Bir düğümün düzey (level) veya derinliği (depth) : Bir düğümün kök düğümden olan uzaklığıdır. Örnek : D düğümünün düzeyi veya derinliği 2'dir.

7)      Ağacın derinliği (depth of tree) : En derindeki yaprağın derinliği veya yüksekliği (height). Örnek : Şekil 2'deki ağacın derinliği 3'tür.

8)      Yaprak (leaf) : Sol ve sağ bağı boş olan düğümlere yaprak adı verilir. Örnekler : D,G,H,I.

9)      Kardeş (sibling, brother) : Aynı parent'a sahip iki düğüme kardeş düğümler adı verilir. Örnekler : B ile C kardeştir. D ile E kardeştir. H ile I kardeştir.

10)  Ancestor (üst düğüm) : Bir düğümün parent'ı birinci ancestor'ıdır. Parent'ın parent'ı (recursion) ikinci ancestor'ıdır. Kök, kendi hariç tüm düğümlerin ancestor'ıdır.

11)  Descendant (alt düğüm) : Bir düğümün iki çocuğu birinci descendant'larıdır. Onların çocukları da ikinci descendant'larıdır.   

12)  Full binary tree : i) Her yaprağı aynı derinlikte olan ii) Yaprak olmayan düğümlerin tümünün iki çocuğu olan ağaç Full (Strictly) Binary Tree'dir (İkinci şart yeterli). Bir full binary tree'de n tane yaprak varsa bu ağaçta toplam 2n-1 düğüm vardır.

13)  Complete binary tree : Full binary tree'de yeni bir derinliğe soldan sağa doğru düğümler eklendiğinde oluşan ağaçlara Complete Binary Tree denilir. Böyle bir ağaçta bazı yapraklar diğerlerinden daha derindir. Bu nedenle full binary tree olmayabilirler. En derin düzeyde düğümler olabildiğince soldadır. 

14)  General Tree (Ağaç) : Her düğümün en fazla iki çocuğu olabilme sınırı olmayan ağaçlardır.

15)  İkili Arama Ağacı (Binary Search Tree) : Boş olan veya her düğümü aşağıdaki şartlara uyan anahtara sahip bir ikili ağaçtır :

i)                    Kökün solundaki alt ağaçlardaki (eğer varsa) tüm anahtarlar kökteki anahtardan küçüktür.

ii)                  Kökün sağındaki alt ağaçlardaki (eğer varsa) tüm anahtarlar kökteki anahtardan büyüktür.

iii)                Sol ve sağ alt ağaçlar da ikili arama ağaçlarıdır.

İkili Ağaçlar ve İkili Ağaçlar Üzerindeki Dolaşma İşlemleri

Dolaşma (traverse), ağaç üzerindeki tüm düğümlere uğrayarak gerçekleştirilir. Ağaçlar üzerindeki dolaşma işlemleri, ağaçtaki tüm bilgilerin listelenmesi veya başka amaçlarla yapılır. Doğrusal veri yapılarında baştan sona doğru dolaşmak kolaydır. Ağaçlar ise düğümleri doğrusal olmayan veri yapılarıdır. Bu nedenle farklı algoritmalar uygulanır. Çok bilinen yöntemler üç tane olup özyinelemeden yararlanırlar :

1)      Preorder (depth-first order) Dolaşma (Traversal)

i)                    Köke uğra (visit)

ii)                  Sol alt ağacı preorder olarak dolaş.

iii)                Sağ alt ağacı preorder olarak dolaş.

2)      Inorder (Symmetric order) Dolaşma

i)                    Sol alt ağacı inorder'a göre dolaş

ii)                  Köke uğra (visit)

iii)                Sağ alt ağacı inorder'a göre dolaş.

3)      Postorder Dolaşma

i)                    Sol alt ağacı postorder'a göre dolaş

ii)                  Sağ alt ağacı postorder'a göre dolaş.

iii)                Köke uğra (visit)

Şekil 3 : İkili Ağaç ve değişik şekillerde dolaşılması

İkili Arama Ağaçları

İkili arama ağaçları, her bir düğümün solundaki (sol alt ağacındaki) tüm düğümler kendisinden küçük, sağındakiler (sağ alt ağacındakiler) de kendisinden büyük olacak şekilde oluşturulurlar (Şekil 4). İkili arama ağaçlarındaki en önemli işlemlerden birisi aramadır.

Örnek olarak aşağıdaki ağaçta, 44 sayısını aratmak için şu işlem sırası izlenir :

Karşılaştırma 1            : 44, 47 ile karşılaştırılır. 44<47 olduğundan sol bağdan ilerlenir.

Karşılaştırma 2            : 44, 25 ile karşılaştırılır. 44>25 olduğundan sağ bağdan ilerlenir.

Karşılaştırma 3            : 44, 43 ile karşılaştırılır. 44>43 olduğundan sağ bağdan ilerlenir.

Karşılaştırma 4            : 44 == 44. Aranan anahtar değeri ağaçta bulundu!

Örnek olarak aşağıdaki ağaçta, 90 sayısını aratmak için şu işlem sırası izlenir :

Karşılaştırma 1            : 90, 47 ile karşılaştırılır. 90>47 olduğundan sağ bağdan ilerlenir.

Karşılaştırma 2            : 90, 77 ile karşılaştırılır. 90>77 olduğundan sağ bağdan ilerlenir.

Karşılaştırma 3            : 90, 93 ile karşılaştırılır. 90<93 olduğundan sol bağdan ilerlenir.

            : NULL. Aranan anahtar değeri ağaçta bulunamadı.

Şekil 4 : İkili Arama Ağacı

Görüldüğü gibi arama işleminin etkinliği ağacın yüksekliğine bağlıdır. İkili arama ağaçları dengeli tutulabilirse, bir anahtar değerini aramada oldukça hızlıdırlar. Böyle olduğunda n elemanlı bir ağaç en fazla log₂n düzeyden oluşur. Bir değerin bulunması veya ağaçta olmadığının belirlenmesi için en fazla log₂n karşılaştırma yapılır. Örnek olarak 1000 elemanlı bir ikili arama ağacında bir elemanın bulunabilmesi için en fazla 10 karşılaştırma yapmak gerekecektir (2¹⁰=1024 > 1000). Bağlı listelerde ise bulunacak elemanın değerine göre (eleman sonda ise) 1000 karşılaştırma yapmak gerekebilir. 

Düğüm sayısı n olan Complete Binary Tree'de derinliği hesaplayabiliriz.

n = 2⁰ + 2¹ + 2² +... + 2^d = 2^d+1-1 => n+1 = 2^d+1 => d = log₂(n+1) - 1'dir.

15 düğümlü bir ağaçta d = log₂(15+1) - 1 = 4-1 = 3'tür.

İkili ağaçlardaki dolaşma işlemlerinin tümü ikili arama ağaçlarında da kullanılır. İkili arama ağaçları üzerinde inorder dolaşıldığında tüm elemanlar küçükten büyüğe sıralı bir şekilde karşımıza gelecektir.

İkili arama ağaçları, tekrarları önlemek açısından da oldukça yararlıdırlar. Ağaç oluşturulurken tekrar eden bir eleman eklenmek istendiğinde, kökten itibaren sola git, sağa git kararları ile o değerin olduğu yere hızlıca ulaşılacak ve ağaçta (veriler içinde) o değerin zaten olduğu anlaşılacaktır. Bu şekilde tekrar eden verilerin olması engellenir.  

Bunlar dışında ikili arama ağacından düğüm silme, ikili arama ağacını iki boyutlu ağaç biçiminde ekrana çizdirme, ağacı düzey sırasında dolaşma (düzey düzey soldan sağa) gibi algoritmalar da yazılabilir. Ayrıca ağaç düzeyini bulma, ağaca string de dahil birçok bilgi ekleme gibi işlemler de yapılabilir.

Bağlı liste veri yapısında ekleme, silme ve arama  işlemleri listedeki eleman sayısı n olmak üzere O(n)  kadar zaman almaktadır. İkili ağaç veri yapısı ise h  ağacın derinliğini göstermek üzere bu işlemlerin O(h)  kadar zamanda yapılmasını sağlar.  Dengeli bir ikili ağaçta sağ ve sol alt ağaçların derinlikleri farkı en fazla birdir. Eğer elimizdeki n tane elemanı dengeli bir ikili ağaca yerleştirirsek, bu ağaçtaki elemanlara ulaşma, ekleme ve silme işlemleri O(log n) kadar zaman alır.