Menü

İkili Arama Ağacı C ++: Örneklerle BST Uygulaması ve İşlemleri

  • Ana
  • Diğer
  • İkili Arama Ağacı C ++: Örneklerle BST Uygulaması ve İşlemleri

binary search tree c

Sorunları Ortadan Kaldırmak Için Enstrümanımızı Deneyin

İşlemler, C ++ Uygulama, Avantajlar ve Örnek Programlar Dahil C ++ 'da İkili Arama Ağacı (BST) Hakkında Ayrıntılı Eğitim:

Bir İkili Arama Ağacı veya popüler adıyla BST, aşağıdaki koşulları sağlayan bir ikili ağaçtır:

  1. BST'nin sol çocukları olarak yerleştirilen kök düğümden daha küçük olan düğümler.
  2. BST'nin sağ alt öğeleri olarak yerleştirilen kök düğümden daha büyük olan düğümler.
  3. Sol ve sağ alt ağaçlar sırayla ikili arama ağaçlarıdır.

Anahtarların belirli bir sırayla sıralanmasına ilişkin bu düzenleme, programcının arama, ekleme, silme, vb. Gibi işlemleri daha verimli bir şekilde gerçekleştirmesini kolaylaştırır. Düğümler sıralanmamışsa, işlem sonucunu almadan önce her bir düğümü karşılaştırmamız gerekebilir.

=> Tam C ++ Eğitim Serisini Buradan Kontrol Edin.

C ++

Ne öğreneceksin:

İkili Arama Ağacı C ++

Aşağıda örnek bir BST gösterilmektedir.

Örnek BST

İkili Arama Ağaçları, bu özel düğüm sıralaması nedeniyle 'Sıralı İkili Ağaçlar' olarak da adlandırılır.

Yukarıdaki BST'den, sol alt ağacın kökten daha küçük düğümlere sahip olduğunu, yani 45'in sağ alt ağacın 45'ten büyük düğümlere sahip olduğunu görebiliriz.

Şimdi BST'nin bazı temel işlemlerini tartışalım.

Temel işlemler

# 1) Ekle

Ekleme işlemi, ikili arama ağacına yeni bir düğüm ekler.

İkili arama ağacı ekleme işlemi için algoritma aşağıda verilmiştir.

deneyimli için oracle sql mülakat soruları
Insert(data) Begin If node == null Return createNode(data) If(data >root->data) Node->right = insert(node->left,data) Else If(data data) Node->right = insert(node>right,data) Return node; end

Yukarıdaki algoritmada gösterildiği gibi, BST sırasını ihlal etmememiz için düğümün uygun konuma yerleştirilmesini sağlamalıyız.

BST

Yukarıdaki diyagram dizisinde gördüğümüz gibi, bir dizi ekleme işlemi yapıyoruz. Eklenecek anahtarın kök düğüm ile karşılaştırılmasından sonra, anahtarın uygun konumda yaprak düğüm olarak yerleştirilmesi için sol veya sağ alt ağaç seçilir.

# 2) Sil

Silme işlemi, BST'den verilen anahtarla eşleşen bir düğümü siler. Bu işlemde de, silme işleminden sonra kalan düğümleri yeniden konumlandırmalıyız, böylece BST sıralaması ihlal edilmez.

Bu nedenle, hangi düğümü silmemiz gerektiğine bağlı olarak, BST'de silme için aşağıdaki durumlara sahibiz:

# 1) Düğüm bir Yaprak Düğümü olduğunda

Silinecek düğüm bir yaprak düğüm olduğunda, o zaman düğümü doğrudan siliyoruz.

Düğüm bir yaprak düğümdür

# 2) Düğümün yalnızca Bir Çocuğu olduğunda

Silinecek düğümün yalnızca bir çocuğu olduğunda, çocuğu düğüme kopyalar ve çocuğu sileriz.

Düğümün yalnızca bir çocuğu var

# 3) Düğümün İki Çocuğu Olduğunda

Silinecek düğümün iki çocuğu varsa, düğümün sıralı halefini bulur ve sonra sıralı halefi düğüme kopyalarız. Daha sonra sıralı halefi siliyoruz.

Düğümün iki çocuğu var

Yukarıdaki ağaçta, iki çocuklu 6 nolu düğümü silmek için, önce silinecek olan bu düğümün sıralı halefini buluruz. Sağ alt ağaçta minimum değeri bularak sıralı halefi buluruz. Yukarıdaki durumda, sağ alt ağaçta minimum değer 7'dir. Silinecek düğüme kopyalıyoruz ve ardından inorder halefini siliyoruz.

# 3) Ara

BST'nin arama işlemi, BST'de 'anahtar' olarak tanımlanan belirli bir öğeyi arar. BST'de bir öğeyi aramanın avantajı, tüm ağacı aramamıza gerek olmamasıdır. Bunun yerine, BST'deki sıralama nedeniyle, anahtarı kökle karşılaştırıyoruz.

Anahtar kök ile aynıysa, o zaman kök döndürürüz. Anahtar kök değilse, sol veya sağ alt ağacı aramamız gerekip gerekmediğini belirlemek için onu kök ile karşılaştırırız. Alt ağacı bulduğumuzda, anahtarı aramalıyız ve alt ağaçlardan birinde yinelemeli olarak ararız.

Aşağıda, BST'deki bir arama işlemi için algoritma verilmiştir.

Search(key) Begin If(root == null || root->data == key) Return root; If(root->key left,key) Else if (root->key >key ) Search(root->right,key); end

BST

Yukarıdaki ağaçta değeri 6 olan bir anahtarı aramak istersek, o zaman önce anahtarı kök düğümle karşılaştırırız, yani if ​​(6 == 7) => Hayır if (6<7) =Yes; this means that we will omit the right subtree and search for the key in the left subtree.

Ardından soldaki alt ağaca iniyoruz. Eğer (6 == 5) => Hayır.

Eğer (6 Hayır; bu 6> 5 anlamına gelir ve sağa doğru hareket etmeliyiz.

(6 == 6) => Evet ise; anahtar bulunur.

# 4) Geçişler

İkili ağacın geçişlerini zaten tartışmıştık. BST durumunda da, sipariş, ön sipariş veya sipariş sonrası sıraya ulaşmak için ağaçtan geçebiliriz. Aslında, Inorder01 dizisinde BST'yi geçtiğimizde, sıralı diziyi elde ederiz.

Bunu aşağıdaki Resimde gösterdik.

geçişler

Yukarıdaki ağaç için geçişler aşağıdaki gibidir:

Sıralı geçiş (lnr): 3 5 6 7 8 9 10
Ön sipariş geçişi (nlr): 7 5 3 6 9 8 10
Sipariş sonrası geçiş (lrn): 3 6 5 8 10 9 7

İllüstrasyon

Aşağıda verilen verilerden bir İkili Arama Ağacı oluşturalım.

45 30 60 65 70

İlk elemanı kök düğüm olarak alalım.

# 1) 45

kök düğüm

Sonraki adımlarda, verileri İkili Arama ağacının tanımına göre yerleştireceğiz, yani veri ana düğümden daha küçükse, sol çocuğa yerleştirilecek ve veri ana düğümden büyükse, o zaman doğru çocuk olacak.

Bu adımlar aşağıda gösterilmiştir.

# 2) 30

İkili Arama ağacı 1. Adım 30

# 3) 60

İkili Arama ağacı Adım 2 60

# 4) 65

11 İkili arama ağacı step3

# 5) 70

İkili arama ağacı 4. adım

Az önce oluşturduğumuz yukarıdaki BST üzerinde sıralı geçişi gerçekleştirdiğimizde, sıra aşağıdaki gibidir.

Sıralı geçiş sırası

Geçiş sırasının artan sırada düzenlenmiş elemanlara sahip olduğunu görebiliriz.

İkili Arama Ağacı Uygulaması C ++

BST'yi ve C ++ uygulamasını kullanarak işlemlerini gösterelim.

#include using namespace std; //declaration for new bst node struct bstnode { int data; struct bstnode *left, *right; }; // create a new BST node struct bstnode *newNode(int key) { struct bstnode *temp = new struct bstnode(); temp->data = key; temp->left = temp->right = NULL; return temp; } // perform inorder traversal of BST void inorder(struct bstnode *root) { if (root != NULL) { inorder(root->left); cout<data<<' '; inorder(root->right); } } /* insert a new node in BST with given key */ struct bstnode* insert(struct bstnode* node, int key) { //tree is empty;return a new node if (node == NULL) return newNode(key); //if tree is not empty find the proper place to insert new node if (key data) node->left = insert(node->left, key); else node->right = insert(node->right, key); //return the node pointer return node; } //returns the node with minimum value struct bstnode * minValueNode(struct bstnode* node) { struct bstnode* current = node; //search the leftmost tree while (current && current->left != NULL) current = current->left; return current; } //function to delete the node with given key and rearrange the root struct bstnode* deleteNode(struct bstnode* root, int key) { // empty tree if (root == NULL) return root; // search the tree and if key data) root->left = deleteNode(root->left, key); // if key > root, go for rightmost tree else if (key > root->data) root->right = deleteNode(root->right, key); // key is same as root else { // node with only one child or no child if (root->left == NULL) { struct bstnode *temp = root->right; free(root); return temp; } else if (root->right == NULL) { struct bstnode *temp = root->left; free(root); return temp; } // node with both children; get successor and then delete the node struct bstnode* temp = minValueNode(root->right); // Copy the inorder successor's content to this node root->data = temp->data; // Delete the inorder successor root->right = deleteNode(root->right, temp->data); } return root; } // main program int main() { /* Let us create following BST 40 / 30 60 65 70*/ struct bstnode *root = NULL; root = insert(root, 40); root = insert(root, 30); root = insert(root, 60); root = insert(root, 65); root = insert(root, 70); cout<<'Binary Search Tree created (Inorder traversal):'<

Çıktı:

İkili Arama Ağacı oluşturuldu (Sıralı geçiş):

30 40 60 65 70

40 düğümünü sil

ağdaki paket kaybı nasıl kontrol edilir

Değiştirilmiş İkili Arama Ağacı için sıralı geçiş:

30 60 65 70

Yukarıdaki programda, sıralı geçiş sırası için BST'yi çıkarıyoruz.

BST'nin Avantajları

# 1) Arama Çok Etkili

BST'nin tüm düğümlerine belirli bir sırayla sahibiz, bu nedenle belirli bir öğeyi aramak çok verimli ve daha hızlıdır. Bunun nedeni, tüm ağacı aramamız ve tüm düğümleri karşılaştırmamız gerekmemesidir.

Sadece kök düğümü aradığımız öğe ile karşılaştırmalıyız ve sonra sol veya sağ alt ağaçta arama yapmamız gerekip gerekmediğine karar vermeliyiz.

# 2) Diziler ve Bağlantılı Listelerle Karşılaştırıldığında Verimli Çalışma

BST durumunda bir öğeyi aradığımızda, her adımda sol veya sağ alt ağacın yarısından kurtulur ve böylece arama işleminin performansını iyileştiririz. Bu, belirli bir öğeyi aramak için tüm öğeleri sırayla karşılaştırmamız gereken diziler veya bağlantılı listelerin tersidir.

# 3) Ekleme ve Silme Daha Hızlıdır

Ekleme ve silme işlemleri, bağlantılı listeler ve diziler gibi diğer veri yapılarına kıyasla daha hızlıdır.

BST Uygulamaları

BST'nin başlıca uygulamalarından bazıları aşağıdaki gibidir:

  • BST, veritabanı uygulamalarında çok düzeyli indekslemeyi uygulamak için kullanılır.
  • BST, sözlük gibi yapıları uygulamak için de kullanılır.
  • BST, çeşitli verimli arama algoritmalarını uygulamak için kullanılabilir.
  • BST, çevrimiçi mağazalar gibi giriş olarak sıralı bir liste gerektiren uygulamalarda da kullanılır.
  • BST'ler ayrıca ifade ağaçlarını kullanarak ifadeyi değerlendirmek için kullanılır.

Sonuç

İkili arama ağaçları (BST), ikili ağacın bir varyasyonudur ve yazılım alanında yaygın olarak kullanılmaktadır. BST'deki her düğüm belirli bir sıraya göre yerleştirildiği için sıralı ikili ağaçlar olarak da adlandırılırlar.

BST'nin sıralı geçişi bize artan sırayla sıralanmış öğeler sırasını verir. BST'ler arama için kullanıldığında, çok verimlidir ve hiç vakit kaybetmeden yapılır. BST'ler ayrıca Huffman’ın kodlaması, veritabanlarında çok düzeyli indeksleme vb. Gibi çeşitli uygulamalar için kullanılır.

=> Popüler C ++ Eğitim Serisini Buradan Okuyun.

Önerilen Kaynaklar

^