İkili Arama Ağacı

İçindekiler

Arama İşlemi
İşlem Ekle
Silme İşlemi
Python, Java ve C / C ++ Örnekleri
İkili Arama Ağacı Karmaşıklıkları
İkili Arama Ağacı Uygulamaları

Bu eğitimde İkili Arama Ağacının nasıl çalıştığını öğreneceksiniz. Ayrıca, C, C ++, Java ve Python'da İkili Arama Ağacının çalışma örneklerini bulacaksınız.

İkili arama ağacı, sıralı bir sayı listesi tutmamızı hızlı bir şekilde sağlayan bir veri yapısıdır.

İkili ağaç olarak adlandırılır çünkü her ağaç düğümünün en fazla iki çocuğu vardır.
Arama ağacı olarak adlandırılır çünkü zaman içinde bir numaranın varlığını aramak için kullanılabilir O(log(n)).

Bir ikili arama ağacını normal bir ikili ağaçtan ayıran özellikler

Sol alt ağacın tüm düğümleri kök düğümden daha küçüktür
Sağ alt ağacın tüm düğümleri kök düğümden daha fazladır
Her bir düğümün her iki alt ağacı da BST'lerdir, yani yukarıdaki iki özelliğe sahiptirler

Kökten bir değeri küçük olan bir sağ alt ağaca sahip bir ağaç, bunun geçerli bir ikili arama ağacı olmadığını göstermek için gösterilir.

Sağdaki ikili ağaç bir ikili arama ağacı değildir çünkü "3" düğümünün sağ alt ağacı ondan daha küçük bir değer içerir.

İkili arama ağacında gerçekleştirebileceğiniz iki temel işlem vardır:

Arama İşlemi

Algoritma, her bir sol alt ağacın kökün altında değerlere sahip olması ve her sağ alt ağacın kökün üzerinde değerlere sahip olması durumunda BST'nin özelliğine bağlıdır.

Değer kökün altındaysa, değerin sağ alt ağaçta olmadığını kesin olarak söyleyebiliriz; yalnızca sol alt ağaçta arama yapmamız gerekir ve değer kökün üzerindeyse, değerin sol alt ağaçta olmadığını kesin olarak söyleyebiliriz; sadece doğru alt ağaçta arama yapmamız gerekiyor.

Algoritma:

 If root == NULL return NULL; If number == root->data return root->data; If number data return search(root->left) If number> root->data return search(root->right)

Bunu bir şema ile görselleştirmeye çalışalım.

4 bulunmadığından, 8'in sol alt ağacından geçiş 8

4 bulunmaz, bu nedenle 3'ün sağ alt ağacından geçiş 3

4 bulunmaz, bu nedenle 6'nın sol alt ağacından geçiş

4 bulunur

Değer bulunursa, aşağıdaki resimde gösterildiği gibi her özyineleme adımında yayılması için değeri döndürürüz.

Fark ettiyseniz, dönüş aramasını (struct node *) dört kez çağırdık. Yeni düğümü veya NULL döndürdüğümüzde, arama (kök) nihai sonucu döndürene kadar değer tekrar tekrar döndürülür.

Değer, alt ağaçların herhangi birinde bulunursa, sonunda döndürülecek şekilde yayılır, aksi takdirde boş döndürülür.

Değer bulunmazsa, sonunda NULL olan bir yaprak düğümün sol veya sağ çocuğuna ulaşırız ve yayılır ve geri döner.

İşlem Ekle

Doğru konuma bir değer eklemek aramaya benzer çünkü sol alt ağacın kökten küçük ve sağ alt ağacın kökten daha büyük olduğu kuralını korumaya çalışıyoruz.

Değere bağlı olarak ya sağ alt ağaca ya da sol alt ağaca gitmeye devam ediyoruz ve sol veya sağ alt ağacın boş olduğu bir noktaya ulaştığımızda yeni düğümü oraya koyuyoruz.

Algoritma:

 If node == NULL return createNode(data) if (data data) node->left = insert(node->left, data); else if (data> node->data) node->right = insert(node->right, data); return node;

Algoritma göründüğü kadar basit değil. Mevcut bir BST'ye nasıl sayı eklediğimizi görselleştirmeye çalışalım.

4 <8 yani, 8

4> 3'ün sol çocuğundan enine, 8

4 <6'nın sağ çocuğundan enine, 6'nın sol çocuğundan enine 4'ü 6'nın sol çocuğu olarak

yerleştirin

Düğümü ekledik ama yine de ağacın geri kalanına herhangi bir zarar vermeden fonksiyondan çıkmamız gerekiyor. return node;Sonunda işe yarayan yer burasıdır . Durumda NULL, yeni oluşturulan düğüm döndürülür ve ana düğüme eklenir, aksi takdirde, köke dönene kadar yukarı çıktıkça aynı düğüm herhangi bir değişiklik olmadan döndürülür.

Bu, ağaçta geri giderken diğer düğüm bağlantılarının değişmemesini sağlar.

Öğelerin yukarı doğru yineleme adımında konumlarını kaybetmemeleri için sonunda kök öğenin döndürülmesinin önemini gösteren resim.

Silme İşlemi

İkili arama ağacından bir düğümü silmek için üç durum vardır.

Durum I

İlk durumda, silinecek düğüm yaprak düğümdür. Böyle bir durumda, düğümü ağaçtan silin.

4 silinecek

Düğümü silin

Durum II

İkinci durumda, silinecek düğümün tek bir çocuk düğümü vardır. Böyle bir durumda aşağıdaki adımları izleyin:

Bu düğümü alt düğümüyle değiştirin.
Alt düğümü orijinal konumundan çıkarın.

6 silinecek

, alt değerinin değerini düğüme kopyalayın ve alt

son ağacı silin

Durum III

Üçüncü durumda, silinecek düğümün iki alt öğesi vardır. Böyle bir durumda aşağıdaki adımları izleyin:

Bu düğümün sıralı halefini alın.
Düğümü sıralı halefi ile değiştirin.
Sıralı halefi orijinal konumundan çıkarın.

3 silinecek

Sıralı halefin (4) değerini düğüme kopyala Sıralı halefi

sil

Python, Java ve C / C ++ Örnekleri

Python Java C C ++

 # Binary Search Tree operations in Python # Create a node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Inorder traversal def inorder(root): if root is not None: # Traverse left inorder(root.left) # Traverse root print(str(root.key) + "->", end=' ') # Traverse right inorder(root.right) # Insert a node def insert(node, key): # Return a new node if the tree is empty if node is None: return Node(key) # Traverse to the right place and insert the node if key < node.key: node.left = insert(node.left, key) else: node.right = insert(node.right, key) return node # Find the inorder successor def minValueNode(node): current = node # Find the leftmost leaf while(current.left is not None): current = current.left return current # Deleting a node def deleteNode(root, key): # Return if the tree is empty if root is None: return root # Find the node to be deleted if key root.key): root.right = deleteNode(root.right, key) else: # If the node is with only one child or no child if root.left is None: temp = root.right root = None return temp elif root.right is None: temp = root.left root = None return temp # If the node has two children, # place the inorder successor in position of the node to be deleted temp = minValueNode(root.right) root.key = temp.key # Delete the inorder successor root.right = deleteNode(root.right, temp.key) return root root = None root = insert(root, 8) root = insert(root, 3) root = insert(root, 1) root = insert(root, 6) root = insert(root, 7) root = insert(root, 10) root = insert(root, 14) root = insert(root, 4) print("Inorder traversal: ", end=' ') inorder(root) print("Delete 10") root = deleteNode(root, 10) print("Inorder traversal: ", end=' ') inorder(root)

 // Binary Search Tree operations in Java class BinarySearchTree ( class Node ( int key; Node left, right; public Node(int item) ( key = item; left = right = null; ) ) Node root; BinarySearchTree() ( root = null; ) void insert(int key) ( root = insertKey(root, key); ) // Insert key in the tree Node insertKey(Node root, int key) ( // Return a new node if the tree is empty if (root == null) ( root = new Node(key); return root; ) // Traverse to the right place and insert the node if (key root.key) root.right = insertKey(root.right, key); return root; ) void inorder() ( inorderRec(root); ) // Inorder Traversal void inorderRec(Node root) ( if (root != null) ( inorderRec(root.left); System.out.print(root.key + " -> "); inorderRec(root.right); ) ) void deleteKey(int key) ( root = deleteRec(root, key); ) Node deleteRec(Node root, int key) ( // Return if the tree is empty if (root == null) return root; // Find the node to be deleted if (key root.key) root.right = deleteRec(root.right, key); else ( // If the node is with only one child or no child if (root.left == null) return root.right; else if (root.right == null) return root.left; // If the node has two children // Place the inorder successor in position of the node to be deleted root.key = minValue(root.right); // Delete the inorder successor root.right = deleteRec(root.right, root.key); ) return root; ) // Find the inorder successor int minValue(Node root) ( int minv = root.key; while (root.left != null) ( minv = root.left.key; root = root.left; ) return minv; ) // Driver Program to test above functions public static void main(String() args) ( BinarySearchTree tree = new BinarySearchTree(); tree.insert(8); tree.insert(3); tree.insert(1); tree.insert(6); tree.insert(7); tree.insert(10); tree.insert(14); tree.insert(4); System.out.print("Inorder traversal: "); tree.inorder(); System.out.println("After deleting 10"); tree.deleteKey(10); System.out.print("Inorder traversal: "); tree.inorder(); ) )

 // Binary Search Tree operations in C #include #include struct node ( int key; struct node *left, *right; ); // Create a node struct node *newNode(int item) ( struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; ) // Inorder Traversal void inorder(struct node *root) ( if (root != NULL) ( // Traverse left inorder(root->left); // Traverse root printf("%d -> ", root->key); // Traverse right inorder(root->right); ) ) // Insert a node struct node *insert(struct node *node, int key) ( // Return a new node if the tree is empty if (node == NULL) return newNode(key); // Traverse to the right place and insert the node if (key key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; ) // Find the inorder successor struct node *minValueNode(struct node *node) ( struct node *current = node; // Find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; ) // Deleting a node struct node *deleteNode(struct node *root, int key) ( // Return if the tree is empty if (root == NULL) return root; // Find the node to be deleted if (key key) root->left = deleteNode(root->left, key); else if (key> root->key) root->right = deleteNode(root->right, key); else ( // If the node is with only one child or no child if (root->left == NULL) ( struct node *temp = root->right; free(root); return temp; ) else if (root->right == NULL) ( struct node *temp = root->left; free(root); return temp; ) // If the node has two children struct node *temp = minValueNode(root->right); // Place the inorder successor in position of the node to be deleted root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); ) return root; ) // Driver code int main() ( struct node *root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 1); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 14); root = insert(root, 4); printf("Inorder traversal: "); inorder(root); printf("After deleting 10"); root = deleteNode(root, 10); printf("Inorder traversal: "); inorder(root); )

 // Binary Search Tree operations in C++ #include using namespace std; struct node ( int key; struct node *left, *right; ); // Create a node struct node *newNode(int item) ( struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; ) // Inorder Traversal void inorder(struct node *root) ( if (root != NULL) ( // Traverse left inorder(root->left); // Traverse root cout  right); ) ) // Insert a node struct node *insert(struct node *node, int key) ( // Return a new node if the tree is empty if (node == NULL) return newNode(key); // Traverse to the right place and insert the node if (key key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; ) // Find the inorder successor struct node *minValueNode(struct node *node) ( struct node *current = node; // Find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; ) // Deleting a node struct node *deleteNode(struct node *root, int key) ( // Return if the tree is empty if (root == NULL) return root; // Find the node to be deleted if (key key) root->left = deleteNode(root->left, key); else if (key> root->key) root->right = deleteNode(root->right, key); else ( // If the node is with only one child or no child if (root->left == NULL) ( struct node *temp = root->right; free(root); return temp; ) else if (root->right == NULL) ( struct node *temp = root->left; free(root); return temp; ) // If the node has two children struct node *temp = minValueNode(root->right); // Place the inorder successor in position of the node to be deleted root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); ) return root; ) // Driver code int main() ( struct node *root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 1); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 14); root = insert(root, 4); cout << "Inorder traversal: "; inorder(root); cout << "After deleting 10"; root = deleteNode(root, 10); cout << "Inorder traversal: "; inorder(root); )