Veri Yapısında İkili Ağaç (ÖRNEK)
Sarah Chen
İkili Ağaç nedir?
İkili kelimesi iki anlamına gelir. Ağaç veri yapısında “İkili Ağaç”, her düğümün en fazla iki alt düğüme (sol ve sağ düğümler) sahip olabildiği bir ağaç anlamına gelir. Basit bir ikili ağaçtır.
Ancak, en sık kullanılan ve çeşitli kullanım durumları olan başka bir ikili ağaç daha vardır. Buna İkili Arama Ağacı (BST) denir. Bu ağaç, arama algoritmasını çok daha hızlı hale getirebilir, tam olarak log(n) zaman karmaşıklığı. Veri yapısında, n ikili ağaçtaki düğüm sayısını ifade eder.
İkili Ağaç ile İkili Arama Ağacı Arasındaki Farklar Nelerdir?
BST ile normal İkili ağaç arasındaki fark, BST sol düğümünün kök düğümden daha küçük bir değere sahip olması ve sağ düğümün kök düğümden daha büyük bir değere sahip olmasıdır. Yani sol alt ağaç her zaman kökten daha küçük bir değer içerecek, sağ alt ağaç ise her zaman kökten daha büyük bir değer içerecektir.
İkili Arama Ağaçları Örneği
İkili Arama Ağacı kavramlarını göstermek için aşağıdaki örneği inceleyelim.
Burada tüm düğümlerin verilen disiplini takip etmesini sağlayabilirsiniz. İkili Arama Ağacındaki maksimum düğüm sayısı için bir formül vardır. Yukarıdaki ağacı incelersek, tüm yaprak düğümler dışında her düğümün iki çocuğu olduğunu görebiliriz. Ve verilen İkili Ağacın yüksekliği(h) 4'tür. Formül şu şekildedir: 2h - 1. Yani 15 verir.
Yukarıda verilen görüntü tam bir İkili Ağaç veya Dengeli İkili Ağaç değildir, Tam İkili Ağaç veya Dengeli İkili Ağaç olarak adlandırılır. İkili Ağacın yüksekliğini optimize eden ve Şekil 3'teki gibi BST için aramayı daha hızlı gerçekleştiren, AVL (başka bir İkili Ağaç türü) adı verilen başka bir Veri Yapısı vardır.
Yukarıda verilen İkili Ağacın sıralı geçişini hesaplamaya çalışın. Azalan olmayan sıralanmış bir dizi vereceğini ve Geçiş algoritmalarının İkili Ağaç ile aynı olacağını göreceksiniz.
İkili Ağaç Türleri
İşte bazı önemli İkili Ağaç türleri:
- Tam İkili Ağaç: Bu ikili ağaçta her düğümün 0 veya 2 alt düğümü olabilir. Bu tür ikili ağaçta yalnızca bir alt düğüme izin verilmez. Yani yaprak düğüm hariç tüm düğümlerin 2 çocuğu olacaktır.
- Tam İkili Ağaç: Her düğüm 0 veya 2 düğüme sahip olabilir. Tam İkili Ağaç gibi görünür, ancak tüm yaprak elemanları sol alt ağaca yaslanır, oysa tam ikili ağaçta düğüm sağ veya sol alt ağaçta olabilir.
- Mükemmel İkili Ağaç: Tüm düğümlerin 0 veya 2 düğümü olması ve tüm yaprak düğümlerin aynı seviyede veya yükseklikte olması gerekir. Yukarıdaki tam ikili ağaç yapısı örneği Mükemmel İkili Ağaç değildir çünkü düğüm 6 ve düğüm 1,2,3 aynı yükseklikte değildir. Ancak Tam İkili Ağaç örneği mükemmel bir ikili ağaçtır.
- Dejenere İkili Ağaç: Her düğümün yalnızca tek bir çocuğu olabilir. Arama, ekleme ve silme gibi tüm işlemler O(N) zaman alır.
- Dengeli İkili Ağaç: Burada bu ikili ağaçta sol ve sağ alt ağacın yükseklik farkı en fazla 1 olur. Yani düğüm eklerken veya silerken ağacın yüksekliğini tekrar dengelememiz gerekiyor. Bu tür Kendi Kendini Dengeleyen İkili Ağaç denir. AVL ağacı.
BST'nin üç temel işlemi vardır. Bunlar aşağıda ayrıntılı olarak tartışılmaktadır.
İkili Ağacın C'de Uygulanması ve C++
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int value;
struct Node *left, *right;
}
struct Node *getEmptynode(int val)
{
struct Node *tempNode = (struct Node *)malloc(sizeof(struct Node));
tempNode->value = val;
tempNode->left = NULL;
tempNode->right = NULL;
return tempNode;
}
struct Node *successor(struct Node *node)
{
struct Node *present = node;
// going to the left most node
while (present != NULL && present->left != NULL)
{
present = present->left;
}
return present;
}
struct Node *insert(struct Node *node, int value)
{
if (node == NULL)
{
return getEmptynode(value);
}
if (value < node->value)
{
node->left = insert(node->left, value);
}
else
{
node->right = insert(node->right, value);
}
return node;
}
int searchInBST(struct Node *node, int value)
{
struct Node *current = node;
while (current->value != value)
{
if (current->value > value)
{
current = current->left;
}
else
{
current = current->right;
}
if (current == NULL)
{
return 0;
}
}
return 1;
}
void inorder(struct Node *root)
{
if (root != NULL)
{
inorder(root->left);
cout << root->value << " ";
inorder(root->right);
}
}
struct Node *deleteNode(struct Node *node, int value)
{
if (node == NULL)
{
return node;
}
if (value < node->value)
{
node->left = deleteNode(node->left, value);
}
else if (value > node->value)
{
node->right = deleteNode(node->right, value);
}
else
{
if (node->left == NULL)
{
struct Node *temp = node->right;
free(node);
return temp;
}
else if (node->right == NULL)
{
struct Node *temp = node->left;
free(node);
return temp;
}
struct Node *temp = successor(node->right);
node->value = temp->value;
node->right = deleteNode(node->right, temp->value);
}
return node;
}
int main()
{
struct Node *root = NULL;
root = insert(root, 8);
root = insert(root, 4);
root = insert(root, 12);
root = insert(root, 2);
root = insert(root, 6);
root = insert(root, 10);
root = insert(root, 14);
root = insert(root, 1);
root = insert(root, 3);
root = insert(root, 5);
root = insert(root, 7);
root = insert(root, 9);
root = insert(root, 11);
root = insert(root, 13);
root = insert(root, 15);
cout << "InOrder Traversal after inserting all nodes: " << endl;
inorder(root);
root = insert(root, -10);
cout << "\nInOrder Traversal after inserting -10 : " << endl;
inorder(root);
cout << "\nSearching -5 in the BST: " << searchInBST(root, -5) << endl;
cout << "Searching -10 in the BST: " << searchInBST(root, -10) << endl;
root = deleteNode(root,8);
cout<<"After deleting node 8, inorder traversal: "<<endl;
inorder(root);
root = deleteNode(root,-10);
cout<<"\nAfter deleting node -10, inorder traversal: "<<endl;
inorder(root);
}
Çıktı:
InOrder Traversal after inserting all nodes: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 InOrder Traversal after inserting -10 : 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Searching -5 in the BST: 0 Searching -10 in the BST: 1 After deleting node 8, inorder traversal: -10 1 2 3 4 5 6 7 9 10 11 12 13 14 15 After deleting node -10, inorder traversal: 1 2 3 4 5 6 7 9 10 11 12 13 14 15
İkili Ağacın Uygulanması Python
class Node:
def __init__(self,value):
self.left = None
self.right = None
self.value = value
def insert(root,value):
if root == None:
return Node(value)
if value< root.value:
root.left = insert(root.left,value)
else:
root.right = insert(root.right,value)
return root
def searchInBST(root,value):
current = root
while current.value != value:
if current.value > value:
current = current.left
else:
current = current.right
if current == None:
return "Not found"
return "Found"
def inorder(root):
if root != None:
inorder(root.left)
print(root.value,end=" ")
inorder(root.right)
def successor(root):
present = root
while present != None and present.left != None:
present = present.left
return present
def deleteNode(root,value):
if root == None:
return root
if value < root.value:
root.left = deleteNode(root.left, value)
elif value>root.value:
root.right = deleteNode(root.right, value)
else:
if root.left == None:
temp = root.right
root = None
return temp
elif root.right == None:
temp = root.left
root = None
return temp
temp = successor(root.right)
root.value = temp.value
root.right = deleteNode(root.right, temp.value)
return root
root = Node(8)
root = insert(root, 4)
root = insert(root, 12)
root = insert(root, 2)
root = insert(root, 6)
root = insert(root, 10)
root = insert(root, 14)
root = insert(root, 1)
root = insert(root, 3)
root = insert(root, 5)
root = insert(root, 7)
root = insert(root, 9)
root = insert(root, 11)
root = insert(root, 13)
root = insert(root, 15)
print("InOrder Traversal after inserting all nodes: ")
inorder(root)
root = insert(root, -10)
print("\nInOrder Traversal after inserting -10 : ")
inorder(root)
print("\nSearching -5 in the BST: ",searchInBST(root, -5))
print("Searching -5 in the BST: ",searchInBST(root, -10))
root = deleteNode(root,8)
print("After deleting node 8, inorder traversal:")
inorder(root)
root = deleteNode(root,-10)
print("\nAfter deleting node -10, inorder traversal:")
inorder(root)
Çıktı:
InOrder Traversal after inserting all nodes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 InOrder Traversal after inserting -10 : -10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Searching -5 in the BST: Not found Searching -5 in the BST: Found After deleting node 8, inorder traversal: -10 1 2 3 4 5 6 7 9 10 11 12 13 14 15 After deleting node -10, inorder traversal: 1 2 3 4 5 6 7 9 10 11 12 13 14 15
İkili Ağaç Uygulaması
İkili Ağacın bazı yaygın uygulamaları şunlardır:
- Düğüm verilerini sıralı düzende düzenleme
- Haritada kullanılır ve programlama dili kitaplıklarındaki düğüm nesnelerini ayarlar.
- Veri yapılarında öğeleri arama
» Bir sonraki eğitimimizi öğrenin Kombinasyon Algoritması
