Veri Yapısında İkili Ağaç (ÖRNEK)

By: Sarah Chen Sarah Chen
Hours Güncellenmiş

⚡ Akıllı Özet

Veri yapılarında ikili ağaç, her düğümün en fazla iki çocuğu (sol ve sağ olarak adlandırılır) olan hiyerarşik bir yapıdır. Bu kaynak, ikili ağaçları, ikili arama ağacını, türlerini, uygulamalarını ve eksiksiz C açıklamasını içermektedir. C++, ve Python uygulamalar.

  • ???? Tanım: İkili ağaç, her düğümün en fazla iki çocuk düğümüne (sol ve sağ) sahip olduğu bir yapıdır.
  • 🔍 İkili Arama Ağacı: İkili arama ağacında, soldaki çocuklar daha küçük değerler, sağdaki çocuklar ise daha büyük değerler tutar; bu da O(log n) arama karmaşıklığına olanak tanır.
  • 🧩 Türleri: Tam, eksiksiz, mükemmel, dejenere ve dengeli ikili ağaçların her biri farklı şekil kuralları uygular.
  • ⚙️ BST Operadurumlar: Ekleme, arama ve silme işlemleri, aramaları hızlandırmak için sıralama özelliğine göre yapılır.
  • ???? Code Sağlanan: Çalışma C, C++, ve Python Programlar ekleme, arama, silme ve sıralı gezinme işlemlerini göstermektedir.
Devamını Oku

İ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 Ağaç ile İkili Arama Ağacı Arasındaki Farklar

İkili Arama Ağaçları Örneği

İkili Arama Ağacı kavramlarını göstermek için aşağıdaki örneği inceleyelim.

İkili Arama Ağaçları Örneği

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.

İkili Arama Ağaçları Örneği

İkili Arama Ağaçları Örneği

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.

İkili Ağaç Türleri

  • 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.

İkili Ağaç Türleri

  • 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.

İkili Ağaç Türleri

  • 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ı.

İkili Ağaç Türleri

BST'nin üç temel işlemi vardır. Bunlar aşağıda ayrıntılı olarak tartışılmaktadır.

İLGİLİ MAKALELER

İ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ı

SSS

Bir düğümün derinliği, kökten o düğüme kadar olan kenarların sayısıdır. Bir düğümün yüksekliği, o düğümden bir yaprağa kadar olan en uzun yoldaki kenarların sayısıdır. Ağacın yüksekliği, kökün yüksekliğine eşittir.

İkili ağaçlar her düğümü yalnızca iki çocukla sınırlandırdığı için dengesiz ve yavaş hale gelebilir. AVL ağacı, alt ağaçların yükseklik farkını bir içinde tutan ve O(log n) işlem garantisi veren, kendi kendini dengeleyen bir ikili arama ağacıdır.

İkili bir ağaç, kök düğümü 0 indeksine yerleştirerek bir dizide saklanabilir. i indeksindeki bir düğüm için, sol çocuğu 2i+1 indeksinde, sağ çocuğu ise 2i+2 indeksinde bulunur. Bu, tam ikili ağaçlar için en uygundur.

Yapay zeka araçları, değerler veya kod listesini etkileşimli bir ikili ağaç diyagramına dönüştürebilir ve düğümler eklendikçe, arandıkça veya silindikçe bunları vurgulayabilir. Bu, yeni başlayanların her işlem sırasında yapının nasıl değiştiğini görmelerine yardımcı olur.

Evet. Yapay zekâ kodlama asistanları, ikili ağaç ve BST kodları (ekleme, arama, silme ve gezinme) üretebilir; bu kodlar aşağıdaki gibi dillerde kullanılabilir: C++, Python, ve Java. RevYapay zekâ, tekrarlanan kayıtlar gibi uç durumları gözden kaçırabileceğinden, çıktıyı inceleyin ve test edin.

Bu yazıyı şu şekilde özetleyin: