Her node’un en fazla 2 çocuğu olan bilgisayar bilimlerinde sıklıkla tercih edilen ağaçlardır. Node’ların dereceleri 0, 1 veya 2 dir.
“D” derinliğine sahip bir binary tree’de, maksimum node sayısı 2D+1 − 1 ’dir.
“H” yüksekliğine sahip bir binary ağaçta maksimum node sayısı 2H+1 − 1 ’dir.
Binary Tree Oluşturmak
Binary tree’ler C programlama dilinde, linked list’e benzer şekilde oluşturulurlar. İçerisinde veriyi tutan data, sol noda’ işaret eden left ve sağ node’a işaret eden rigt olan bir node struct’ı oluşturulur. Ağaçtaki tüm node’lar bu struct yapısından türetilir. Başlangıç node’u olan kök root’ta tutulur. Eğer node’un sağ veya sol çocuğu yoksa o değerlere NULL girilir.
struct node {
int data;
struct node *left;
struct node *right;
};3 node’dan oluşan sırasıyla 2, 4, 6 değerlerini içeren basit bir binary tree oluşturalım.
root ismindeki başlangıç node’unu tanımlıyoruz ve malloc fonkiyonuyla bellekte yer kaplamasını sağlıyoruz. root’un data değerine 2, left ve right değerlerine ise şimdilik NULL ataması yapıyoruz. Böylelikle kök node’umuz oluştu.
struct node *root = (struct node *)malloc(sizeof(struct node));
root->data = 2;
root->left = NULL;
root->right = NULL;
Şimdi Kök node’un soluna 4 node’unu oluşturup atayalım.
temp isminde bir node oluşturup, bellekte yer ayırdıktan sonra, node’un data değerine 4‘ü, left ve right değerlerine ise NULL’u atıyoruz. Sonrasında root’un left’ine temp’i atıyoruz.
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = 4;
temp->left = NULL;
temp->right = NULL;
root->left = temp;
Son olarak ağaçta 4 node’unun sağına 6 node’unu oluşturup ekleyelim.
temp2 isminde bir node oluşturup belleke yer ayırdıktan sonra, data değerine 6, left ve right değerleine NULL ataması yapıyoruz. Daha sonra root’un left’inin right’ına oluşturduğumuz temp node’unu atıyoruz.
struct node *temp2 = (struct node *)malloc(sizeof(struct node));
temp2->data = 6;
temp2->left = NULL;
temp2->right = NULL;
root->left->right = temp2;
Ve basit bir binary tree oluşturduk. Fakat, genelde ağaçlarda NULL ifadelerinin gösterilmesi tercih edilmez. Dilersek onları kaldırabiliriz.
Binary Tree Traversal
Bir ağaçtaki her bir node’u tek tek gezmeye traversal (gezinme) denilmektedir. Bir ağaçtaki node’lar üç farklı şekilde gezilebilmektedir. Bu gezinme teknikleri:
- Preorder
- Inorder
- Postorder
dır.
Preorder: Kökün başta olduğu gezinme yöntemidir. Önce kök, sonra sol alt ağaç ve en son sağ alt ağaç gezilir.
Inorder: Kökün ortada olduğu gezinme yöntemidir. Önce sol alt ağaç, sonra kök ve en son sağ alt ağaç gezilir.
Postorder: Kökün sonda olduğu gezinme yöntemidir. Önce sol alt ağaç, sonra sağ alt ağaç ve en son kök gezilir.
Aşağıdaki ikili ağacın preorder, inorder ve postorder gezinme şekillerini gösterelim.
Preorder: 14, 37, 3, 40, 7, 88, 6, 25, 13, 78, 3
Inorder: 40, 3, 7, 37, 88, 14, 25, 78, 13, 3, 6
Postorder: 40, 7, 3, 88, 37, 78, 3, 13, 25, 6, 14
Binary Search Tree
Binary search tree diğer adıyla ikili arama ağacı, binary tree’nin bir alt kümesidir. Binary tree’nin tüm özelliklerine sahiptir. Binary search tree’yi özelleştiren şey ise tüm node’lar için:
sol node’un değeri < kendisinin değeri < sağ node’un değeri
şeklinde olmasıdır. Ayrıca bu ağaçta aynı değere sahip birden fazla node olamaz.
Yukarıdaki ikili ağaçta her bir node’un sol node’u kendisinden küçük, sağı kendisinden büyüktür. Bu yüzden bu ağaç ikili arama ağacı (binary search tree) dir.
Binary Search Tree Insertion
Binary search tree’ye eleman eklerken öncelikle köke elemanın değeri kökün değerinden büyük mü? diye sorulur. Eğer büyükse sağa değilse sola geçilir. Sonra burası boş mu diye bakılır. Boş değilse oradaki node’a aynı soru sorulur. Eğer küçükse aynı şekilde sola büyükse sağa geçilir. Bu işlem node’un eklenebileceği boş bir alan olana kadar devam eder ve boşluk bulduğunda oraya yerleştirilir.
[10, 4, 5, 23, 19, 20, 2] sayı dizisindeki elemanlarla sırasıyla ekleme işlemi yaparak bir binary search tree oluşturalım.
1. Adım: 10 node’unu ekleyelim.
2. Adım: 4, 10’dan büyük mü? Hayır. 4’ü 10’un soluna ekleyelim.
3.Adım: 5, 10 dan büyük mü? Hayır. 5, 4′ den büyük mü? Evet. 5’i 4’ün sağına ekleyelim.
4. Adım: 23, 10’dan büyük mü? Evet. 23’ü 10’un sağına ekleyelim.
5. Adım: 19, 10’den büyük mü? Evet. 19, 23’den büyük mü? Hayır. 19’u 23’ün soluna ekleyelim.
6. Adım: 20, 10’dan büyük mü? Evet. 20, 23′ den büyük mü? Hayır. 20, 19’dan büyük mü? Evet. 20’yi 19’un sağına ekleyelim.
7. Adım: 2, 10’dan büyük mü? Hayır. 2, 4’den büyük mü? Hayır. 2’yi 4’ün soluna ekleyelim.
Binary Search Tree Deletion
Bir ikili arama ağacında silme işlemi yapmak istediğimizde bizi 3 farklı durum karşılar. Bunlar:
- Silinecek node’un çocuğu yoksa
- Silinecek node’un tek bir çocuğu varsa
- Silinecek node’un iki çocuğu varsa
durumlarıdır.
Sİlinecek Node’un Bir Çocuğu Varsa
Sİlinecek node’un çocuğu yoksa, o node bir leaf node’udur. Leaf node’u silinmek istendiğinde direkt olarak ağaçtan kaldırılarak silme işlemi gerçekleştirilir.
Sİlinecek Node’un Bir Çocuğu Varsa
Silinecek node’un bir çocuğu varsa, o node’un çocuğu ile ebeveyni arasında bağ kurulup node kaldırılır. Böylece silme işlemi gerçekleşmiş olur.
Sİlinecek Node’un İki Çocuğu Varsa
Eğer silinecek node’un iki çocuğu varsa, sol alt ağaçtaki en büyük elemanla veya sağ alt ağaçtaki en küçük elemanla yer değiştir. Böylece o node tek çocuklu veya çocuksuz bir node haline gelir ve silme işlemi yapılır.
