बाइनरी सर्च ट्री (BST) एक विशेष प्रकार का वृक्ष है जो निम्नलिखित नियमों का पालन करता है -
-
लेफ्ट चाइल्ड नोड का मान हमेशा पैरेंट नोट से कम होता है
-
राइट चाइल्ड नोड का मान पैरेंट नोड से अधिक होता है।
-
सभी नोड्स व्यक्तिगत रूप से एक बाइनरी सर्च ट्री बनाते हैं।
बाइनरी सर्च ट्री (BST) का उदाहरण -
खोज, न्यूनतम और अधिकतम खोजें जैसे कार्यों की जटिलता को कम करने के लिए बाइनरी सर्च ट्री बनाया जाता है।
ऑपरेशन बाइनरी सर्च ट्री (BST) हटाएं
डिलीट ऑपरेशन पेड़ से निर्दिष्ट नोड को गिरा रहा है। नोड्स को हटाने के मामले में, तीन संभावनाएं हैं -
-
ट्री से लीफ नोड को हटाना:सबसे सरल विलोपन बाइनरी सर्च ट्री से लीफ नोड को हटाना है। लीफ नोड को हटाने के लिए केवल पत्ती प्रभावित होती है। उदाहरण,
लीफ नोड को हटाने से 7 देता है,
-
एक चाइल्ड नोड के साथ नोड को हटाना:इस विलोपन के लिए, आपको चाइल्ड नोड को हटाए जाने वाले नोड से बदलना होगा और फिर इसे हटाना होगा। उदाहरण,
BST से 2 हटाना
-
दो चाइल्ड नोड्स के साथ नोड को हटाना:यहां हटाए जाने वाले नोड में दो चाइल्ड नोड होते हैं। तो, हम पेड़ के क्रम रूप में उपयोग करेंगे, यहां हम तत्व को हटा देंगे और इसके स्थान के लिए इसके पड़ोसी पड़ोसी का चयन करेंगे और बाकी को फिर से बनाएंगे। उदाहरण,
5 को BST से हटाने पर निम्न ट्री वापस आ जाएगा।
उदाहरण
#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