एक बाइनरी सर्च ट्री एक सॉर्टेड बाइनरी ट्री है जिसमें सभी नोड्स में निम्नलिखित गुण होते हैं:
- किसी नोड का राइट सब-ट्री उसके पैरेंट नोड की की से अधिक की रखता है।
- किसी नोड का लेफ्ट सब-ट्री उसके पैरेंट नोड की की से कम या बराबर की रखता है।
- प्रत्येक नोड में दो से अधिक चाइल्ड नहीं होने चाहिए।
यहाँ C++ में रैंडमाइज़्ड बाइनरी सर्च ट्री लागू करने का प्रोग्राम है।
एल्गोरिदम
- search(): BST में आइटम खोजें।
- insert(): ट्री में आइटम्स डालें।
- del(): ट्री से आइटम हटाएं (केस a, b, c हैंडल करता है)।
- inorder/preorder/postorder: ट्रैवर्सल मेथड्स।
C++ कार्यान्वयन
#include <iostream>
#include <cstdlib>
using namespace std;
struct Node {
int info;
Node *left, *right;
};
class BST {
Node* root;
public:
BST() : root(NULL) {}
void insert(int key) { root = insertRec(root, key); }
Node* insertRec(Node* node, int key) {
if (!node) return new Node{key, NULL, NULL};
if (key < node->info) node->left = insertRec(node->left, key);
else if (key > node->info) node->right = insertRec(node->right, key);
return node;
}
void search(int key) { searchRec(root, key); }
void searchRec(Node* node, int key) {
int depth = 0;
while (node) {
depth++;
if (node->info == key) { cout << "Found at depth: " << depth << endl; return; }
node = (key < node->info) ? node->left : node->right;
}
cout << "Not found" << endl;
}
void deleteKey(int key) { root = deleteRec(root, key); }
Node* deleteRec(Node* root, int key) {
if (!root) return root;
if (key < root->info) root->left = deleteRec(root->left, key);
else if (key > root->info) root->right = deleteRec(root->right, key);
else {
if (!root->left) return root->right;
if (!root->right) return root->left;
Node* temp = minValueNode(root->right);
root->info = temp->info;
root->right = deleteRec(root->right, temp->info);
}
return root;
}
Node* minValueNode(Node* node) {
while (node->left) node = node->left;
return node;
}
void inorder() { inorderRec(root); cout << endl; }
void inorderRec(Node* node) {
if (!node) return;
inorderRec(node->left);
cout << node->info << " ";
inorderRec(node->right);
}
void preorder() { preorderRec(root); cout << endl; }
void preorderRec(Node* node) {
if (!node) return;
cout << node->info << " ";
preorderRec(node->left);
preorderRec(node->right);
}
void postorder() { postorderRec(root); cout << endl; }
void postorderRec(Node* node) {
if (!node) return;
postorderRec(node->left);
postorderRec(node->right);
cout << node->info << " ";
}
void display() { displayRec(root, 1); }
void displayRec(Node* node, int level) {
if (!node) return;
displayRec(node->right, level+1);
cout << endl;
if (node == root) cout << "Root->: ";
else for (int i=0; iinfo;
displayRec(node->left, level+1);
}
};
int main() {
BST bst;
bst.insert(6); bst.insert(7); bst.insert(5); bst.insert(4);
bst.search(7); bst.search(1);
bst.inorder(); bst.preorder(); bst.postorder();
bst.display();
bst.deleteKey(5);
bst.display();
return 0;
}
आउटपुट
Found at depth: 2 Not found Inorder: 4 5 6 7 Preorder: 6 5 4 7 Postorder: 4 5 7 6 Display: 7 Root->: 6 5 4 After deleting 5: 7 Root->: 6 4