C++ प्रोग्राम: बाइनरी सर्च ट्री द्वारा संख्या की घटनाओं की गिनती

यह C++ प्रोग्राम बाइनरी सर्च ट्री (BST) का उपयोग करके एक सॉर्टेड ऐरे में दिए गए नंबर की घटनाओं (occurrences) की संख्या गिनता है। प्रत्येक नोड में डेटा और उसकी काउंट होती है।

एल्गोरिदम

शुरुआत
  1. फंक्शन Insert() - ट्री में नोड इन्सर्ट करें:
     - आर्गुमेंट्स: रूट, डेटा
     - डेटा से नया नोड बनाएं
     - यदि ट्री खाली है, तो नया नोड रूट बनाएं
     - यदि डेटा = tmp->data, तो उस नोड की काउंट बढ़ाएं
     - यदि डेटा < tmp->data, तो बाएं चाइल्ड पर जाएं
     - यदि डेटा > tmp->data, तो दाएं चाइल्ड पर जाएं
  
  2. फंक्शन SearchNode() - ट्री में आइटम सर्च करें:
     - आर्गुमेंट्स: रूट, डेटा
     - लूप चलाएं जब तक टेम्प NULL न हो या डेटा मिल जाए
     - यदि डेटा < tmp->data, तो बाएं जाएं
     - यदि डेटा > tmp->data, तो दाएं जाएं
     - यदि डेटा = tmp->data, तो आइटम मिला और उसकी काउंट प्रिंट करें
     - अन्यथा "Data not found" प्रिंट करें
समाप्ति

उदाहरण कोड

#include <iostream>
using namespace std;

struct Node {
    int data;
    int count;
    Node *left, *right;
};

Node* CreateNode(int d) {
    Node *newNode = new Node;
    newNode->data = d;
    newNode->count = 1;
    newNode->left = newNode->right = nullptr;
    return newNode;
}

Node* Insert(Node* root, int d) {
    Node *tmp = CreateNode(d);
    Node *t = root;
    
    if (root == nullptr)
        root = tmp;
    else {
        while (t != nullptr) {
            if (t->data == d) {
                t->count++;
                break;
            } else if (t->data < d) {
                if (t->right == nullptr) {
                    t->right = tmp;
                    break;
                }
                t = t->right;
            } else {
                if (t->left == nullptr) {
                    t->left = tmp;
                    break;
                }
                t = t->left;
            }
        }
    }
    return root;
}

void SearchNode(Node *root, int d) {
    Node *tmp = root;
    while (tmp != nullptr) {
        if (tmp->data == d) {
            cout << "\nData item " << d << " is present " 
                 << tmp->count << " number of times.";
            return;
        } else if (tmp->data > d)
            tmp = tmp->left;
        else
            tmp = tmp->right;
    }
    cout << "\nData not found";
}

int main() {
    char choice;
    int n, i;
    int arr[20] = {8, 1, 3, 6, 4, 7, 10, 14, 13, 7, 6, 1, 26, 4, 26, 20, 21, 12, 10, 1};
    
    Node *root = nullptr;
    for (i = 0; i < 20; i++)
        root = Insert(root, arr[i]);
    
    do {
        cout << "\nEnter the element to be searched: ";
        cin >> n;
        SearchNode(root, n);
        cout << "\n\nWant to search more? (y/n): ";
        cin >> choice;
    } while (choice == 'y' || choice == 'Y');
    
    return 0;
}

आउटपुट

Enter the element to be searched: 7
Data item 7 is present 2 number of times.

Want to search more? (y/n): y
Enter the element to be searched: 6
Data item 6 is present 2 number of times.

Want to search more? (y/n): y
Enter the element to be searched: 4
Data item 4 is present 2 number of times.

Want to search more? (y/n): y
Enter the element to be searched: 15
Data not found

Want to search more? (y/n): n

समय जटिलता: औसत केस O(log n), सबसे खराब केस O(n) असंतुलित ट्री के लिए।

स्पेस जटिलता: O(n) ट्री स्टोरेज के लिए।

सुधार: बैलेंस्ड BST (AVL, Red-Black Tree) का उपयोग करके सबसे खराब केस को O(log n) बनाया जा सकता है।