C++ प्रोग्राम सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री (AVL ट्री) लागू करने के लिए

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

यह C++ में सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री (AVL ट्री) लागू करने का प्रोग्राम है।

एल्गोरिदम

• balance(): बैलेंस फैक्टर प्राप्त करके ट्री को बैलेंस करें। अंतर को bal_factor में रखें। यदि bal_factor > 1 तो बाएं सबट्री को बैलेंस करें। यदि bal_factor < -1 तो दाएं सबट्री को बैलेंस करें।
• insert(): ट्री में एलिमेंट्स डालें:
  • यदि ट्री खाली है तो डेटा को रूट के रूप में डालें।
  • यदि ट्री खाली नहीं है और डेटा < रूट, तो बाएं चाइल्ड के रूप में डालें।
  • अन्यथा दाएं चाइल्ड के रूप में डालें।
• रोटेशन्स: LL, RR, LR, RL रोटेशन्स का उपयोग करके बैलेंस बहाल करें।

C++ कार्यान्वयन

#include <iostream>
#include <cstdio>
#include <sstream>
#include <algorithm>
#define pow2(n) (1 << (n))
using namespace std;

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

class AVLTree {
public:
    Node* root;
    AVLTree() { root = NULL; }
    
    int height(Node* node) {
        if (!node) return 0;
        return 1 + max(height(node->left), height(node->right));
    }
    
    int getBalance(Node* node) {
        if (!node) return 0;
        return height(node->left) - height(node->right);
    }
    
    Node* rightRotate(Node* y) {
        Node* x = y->left;
        Node* T2 = x->right;
        x->right = y;
        y->left = T2;
        return x;
    }
    
    Node* leftRotate(Node* x) {
        Node* y = x->right;
        Node* T2 = y->left;
        y->left = x;
        x->right = T2;
        return y;
    }
    
    Node* insert(Node* node, int key) {
        if (!node) {
            node = new Node{key, NULL, NULL};
            return node;
        }
        if (key < node->data)
            node->left = insert(node->left, key);
        else if (key > node->data)
            node->right = insert(node->right, key);
        else return node; // डुप्लीकेट नहीं
        
        int balance = getBalance(node);
        
        // LL केस
        if (balance > 1 && key < node->left->data)
            return rightRotate(node);
        // RR केस
        if (balance < -1 && key > node->right->data)
            return leftRotate(node);
        // LR केस
        if (balance > 1 && key > node->left->data) {
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }
        // RL केस
        if (balance < -1 && key < node->right->data) {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }
        return node;
    }
    
    void inorder(Node* root) {
        if (!root) return;
        inorder(root->left);
        cout << root->data << " ";
        inorder(root->right);
    }
    
    void preorder(Node* root) {
        if (!root) return;
        cout << root->data << " ";
        preorder(root->left);
        preorder(root->right);
    }
    
    void postorder(Node* root) {
        if (!root) return;
        postorder(root->left);
        postorder(root->right);
        cout << root->data << " ";
    }
};

int main() {
    AVLTree tree;
    int keys[] = {13, 10, 15, 5, 11, 4, 8, 16, 14, 3, 7, 9, 52};
    int n = sizeof(keys)/sizeof(keys[0]);
    
    for (int i = 0; i < n; i++)
        tree.root = tree.insert(tree.root, keys[i]);
    
    cout << "Inorder: "; tree.inorder(tree.root); cout << endl;
    cout << "Preorder: "; tree.preorder(tree.root); cout << endl;
    cout << "Postorder: "; tree.postorder(tree.root); cout << endl;
    return 0;
}

आउटपुट

Inorder: 3 4 5 7 8 9 10 11 13 14 15 16 52
Preorder: 10 5 4 3 8 7 9 13 11 15 14 16 52
Postorder: 3 4 9 8 7 5 14 16 15 11 13 10 52