बाइनरी सर्च ट्री (BST) एक विशेष प्रकार का ट्री है जो निम्नलिखित नियमों का पालन करता है -
बाएं चाइल्ड नोड का मान हमेशा पैरेंट नोट से कम होता है
राइट चाइल्ड नोड का मान पैरेंट नोड से अधिक होता है।
सभी नोड्स व्यक्तिगत रूप से एक बाइनरी सर्च ट्री बनाते हैं।
बाइनरी सर्च ट्री (BST) का उदाहरण -
बाइनरी सर्च ट्री खोज, न्यूनतम और अधिकतम ढूंढने जैसे ऑपरेशंस की जटिलता को कम करने के लिए बनाया जाता है।
बाइनरी सर्च ट्री (BST) में डिलीट ऑपरेशन
डिलीट ऑपरेशन ट्री से निर्दिष्ट नोड को हटाना है। नोड्स हटाने के मामले में, तीन संभावनाएं हैं -
ट्री से लीफ नोड हटाना: बाइनरी सर्च ट्री से लीफ नोड हटाना सबसे सरल डिलीशन है। लीफ नोड हटाने के लिए केवल लीफ प्रभावित होता है। उदाहरण,
लीफ नोड 7 को हटाने पर,
एक चाइल्ड नोड वाले नोड को हटाना: इस डिलीशन के लिए, आपको चाइल्ड नोड को हटाए जाने वाले नोड से बदलना होगा और फिर इसे हटाना होगा। उदाहरण,
BST से 2 को हटाना
दो चाइल्ड नोड्स वाले नोड को हटाना: यहां हटाए जाने वाले नोड में दो चाइल्ड नोड्स हैं। तो, हम ट्री के इनऑर्डर रूप का उपयोग करेंगे, यहां हम तत्व को हटाएंगे और इसके इनऑर्डर पड़ोसी को इसकी जगह चुनेंगे और बाकी को फिर से बनाएंगे। उदाहरण,
BST से 5 को हटाने पर निम्नलिखित ट्री लौटाएगा।
उदाहरण
#include<stdio.h> #include<stdlib.h> struct node{ int key; struct node *left, *right; }; struct node *newNode(int item){ struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; } void inordertraversal(struct node *root){ if (root != NULL){ inordertraversal(root->left); printf("%d ", root->key); inordertraversal(root->right); } } struct node* insert(struct node* node, int key){ if (node == NULL) return newNode(key); if (key < node->key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; } struct node * minValueNode(struct node* node){ struct node* current = node; while (current && current->left != NULL) current = current->left; return current; } struct node* deleteNode(struct node* root, int key){ if (root == NULL) return root; if (key < root->key) root->left = deleteNode(root->left, key); else if (key > root->key) root->right = deleteNode(root->right, key); else{ 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; } struct node* temp = minValueNode(root->right); root->key = temp->key; root->right = deleteNode(root->right, temp->key); } return root; } int main(){ struct node *root = NULL; root = insert(root, 50); root = insert(root, 30); root = insert(root, 20); root = insert(root, 40); root = insert(root, 70); root = insert(root, 60); root = insert(root, 80); printf("Inorder traversal of the given tree \n"); inordertraversal(root); printf("\nDelete 20\n"); root = deleteNode(root, 20); printf("Inorder traversal of the modified tree \n"); inordertraversal(root); printf("\nDelete 30\n"); root = deleteNode(root, 30); printf("Inorder traversal of the modified tree \n"); inordertraversal(root); printf("\nDelete 50\n"); root = deleteNode(root, 50); printf("Inorder traversal of the modified tree \n"); inordertraversal(root); return 0; } आउटपुट
Inorder traversal of the given tree 20 30 40 50 60 70 80 Delete 20 Inorder traversal of the modified tree 30 40 50 60 70 80 Delete 30 Inorder traversal of the modified tree 40 50 60 70 80 Delete 50 Inorder traversal of the modified tree 40 60 70 80
