Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ प्रोग्राम रैंडमाइज़्ड बाइनरी सर्च ट्री लागू करने के लिए


एक बाइनरी सर्च ट्री एक सॉर्टेड बाइनरी ट्री है जिसमें सभी नोड्स में निम्नलिखित गुण होते हैं:

  • किसी नोड का राइट सब-ट्री उसके पैरेंट नोड की की से अधिक की रखता है।
  • किसी नोड का लेफ्ट सब-ट्री उसके पैरेंट नोड की की से कम या बराबर की रखता है।
  • प्रत्येक नोड में दो से अधिक चाइल्ड नहीं होने चाहिए।

यहाँ 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
  1. C++ में बाइनरी खोज प्रोग्राम C++ में बाइनरी खोज प्रोग्राम

    बाइनरी खोज क्या है? बाइनरी खोज (आधा-अंतराल खोज) एक खोज एल्गोरिदम है जो क्रमबद्ध सरणी में लक्ष्य मान की स्थिति ढूंढता है। यह लक्ष्य मान की तुलना मध्य तत्व से करता है और खोज स्थान को आधा कर देता है। मुख्य बिंदु केवल क्रमबद्ध सरणी पर काम करता है समय जटिलता: O(log n) दुनिया के सभी नाम क्रमबद्ध हों तो

  1. C++ में AVL ट्री को लागू करना C++ में AVL ट्री को लागू करना

    AVL ट्री एक सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री है जहां सभी नोड्स के लिए बाएं और दाएं सबट्री की ऊंचाई का अंतर एक से अधिक नहीं हो सकता।ट्री रोटेशन एक ऑपरेशन है जो AVL ट्री पर एलिमेंट्स के क्रम में हस्तक्षेप किए बिना स्ट्रक्चर को बदलता है। यह ट्री में एक नोड को ऊपर ले जाता है और एक नोड को नीचे। इसका उपयो

  1. C++ प्रोग्राम: बाइनरी सर्च ट्री पर लेफ्ट रोटेशन करना C++ प्रोग्राम: बाइनरी सर्च ट्री पर लेफ्ट रोटेशन करना

    एक बाइनरी सर्च ट्री एक सॉर्टेड बाइनरी ट्री है जिसमें सभी नोड्स में निम्नलिखित दो गुण होते हैं - एक नोड का राइट सब-ट्री उसके पैरेंट नोड की कुंजी से अधिक सभी कुंजियों को रखता है। एक नोड का लेफ्ट सब-ट्री उसके पैरेंट नोड की कुंजी से कम सभी कुंजियों को रखता है। प्रत्येक नोड में दो से अधिक चाइल्ड नहीं हो