C++ में बाइनरी सर्च ट्री को बैलेंस करना

मान लीजिए हमारे पास एक बाइनरी सर्च ट्री है, हमें उसी नोड वैल्यूज़ के साथ एक बैलेंस्ड बाइनरी सर्च ट्री ढूंढनी है। एक बाइनरी सर्च ट्री को बैलेंस्ड कहा जाता है अगर और केवल अगर हर नोड के दो सबट्रीज़ की गहराई 1 से अधिक नहीं होती। अगर एक से अधिक रिजल्ट हैं, तो उनमें से कोई भी लौटाएं। उदाहरण के लिए, अगर ट्री है:

इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:

• inorder() मेथड डिफाइन करें, यह इनऑर्डर ट्रैवर्सल सीक्वेंस को एक ऐरे में स्टोर करेगा

• construct मेथड डिफाइन करें, जो low और high लेगा:

  • अगर low > high तो नल लौटाएं

  • mid := low + (high - low) / 2

  • root := arr[mid] वैल्यू के साथ नया नोड

  • root का लेफ्ट := construct(low, mid - 1) और root का राइट := construct(mid + 1, high)

  • root लौटाएं

• मेन मेथड से, inorder मेथड कॉल करें और construct(0, arr का साइज - 1) लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्न इम्प्लीमेंटेशन देखें:

#include <bits/stdc++.h>
using namespace std;

class TreeNode{
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data){
        val = data;
        left = right = NULL;
    }
};

void insert(TreeNode **root, int val){
    queue<TreeNode*> q;
    q.push(*root);
    while(q.size()){
        TreeNode *temp = q.front();
        q.pop();
        if(!temp->left){
            if(val != NULL)
                temp->left = new TreeNode(val);
            else
                temp->left = new TreeNode(0);
            return;
        }else{
            q.push(temp->left);
        }
        if(!temp->right){
            if(val != NULL)
                temp->right = new TreeNode(val);
            else
                temp->right = new TreeNode(0);
            return;
        }else{
            q.push(temp->right);
        }
    }
}

TreeNode *make_tree(vector<int> v){
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i<v.size(); i++){
        insert(&root, v[i]);
    }
    return root;
}

void tree_level_trav(TreeNode* root){
    if (root == NULL) return;
    cout << "[";
    queue<TreeNode *> q;
    TreeNode *curr;
    q.push(root);
    q.push(NULL);
    while (q.size() > 1) {
        curr = q.front();
        q.pop();
        if (curr == NULL){
            q.push(NULL);
        } else {
            if(curr->left)
                q.push(curr->left);
            if(curr->right)
                q.push(curr->right);
            if(curr->val == 0 || curr == NULL){
                cout << "null" << ", ";
            }else{
                cout << curr->val << ", ";
            }
        }
    }
    cout << "]"<<endl;
}

class Solution {
public:
    vector <int> arr;
    void inorder(TreeNode* node){
        if(!node || node->val == 0) return;
        inorder(node->left);
        arr.push_back(node->val);
        inorder(node->right);
    }
    TreeNode* construct(int low, int high){
        if(low > high) return NULL;
        int mid = low + (high - low) / 2;
        TreeNode* root = new TreeNode(arr[mid]);
        root->left = construct(low, mid - 1);
        root->right = construct(mid + 1, high);
        return root;
    }
    TreeNode* balanceBST(TreeNode* root) {
        inorder(root);
        return construct(0, (int)arr.size() - 1);
    }
};

int main(){
    vector<int> v = {1,NULL,2,NULL,NULL,NULL,3,NULL,NULL,NULL,NULL,NULL,NULL,NULL,4};
    TreeNode *root = make_tree(v);
    Solution ob;
    tree_level_trav(ob.balanceBST(root));
}

इनपुट

[1,NULL,2,NULL,NULL,NULL,3,NULL,NULL,NULL,NULL,NULL,NULL,NULL,4]

आउटपुट

[2, 1, 3, 4, ]