متوازن BST کي معمولي BST ۾ تبديل ڪريو


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ آمريڪي ايڪسپريس ByteDance گاديء جو هڪ گرافس اڳوڻن ڌار ڌار زو
ثنائي ڳولا وارو وڻ بائنري وڻ وڻن

مسئلي جو بيان

Binary Search Tree (BST) ڏنو ويو ، بي ٽي ايس کي متوازن بائنري سرچ وڻ ۾ بدلائڻ لاءِ الگورٿم لکو. هڪ متوازن بائنري سرچ وڻ جوڙي کان سواءِ ٻيو ڪجهه ناهي ، هڪ بائنري سرچ وڻ جنهن جي کاٻي شاخ جي چوٽي ۽ سا subي وڻ جي اونچائي ۾ فرق 1 کان گهٽ يا برابر آهي.

مثال

پٽ

متوازن BST کي معمولي BST ۾ تبديل ڪريو

پيداوار

متوازن BST کي معمولي BST ۾ تبديل ڪريو

اڳ آرڊر: 31 17 3 23 48 45 50 62

پٽ

متوازن BST کي معمولي BST ۾ تبديل ڪريو

پيداوار

متوازن BST کي معمولي BST ۾ تبديل ڪريو

يادگار: 8 7 9

 

عام بي ٽي ايس کي متوازن BST ۾ تبديل ڪرڻ لاءِ الورگيتم

هڪ طريقو ٿي سگهي ٿو ته ترتيب ڏيڻ واري بائنري سرچ وڻ جي ترتيب سان ترتيب ڏيڻ فيشن ۾ ۽ عناصر کي خود بيلنس ڪرڻ واري وڻ ۾ ذخيرو ڪري سگهجي ٿو ، جهڙوڪ اي وي ايل وڻ يا هڪ ڳاڙهي ڪارو وڻ. اهو نقشو وڌيڪ ڪارائتو نه آهي ، اهو O (N log N) وقت وٺندو آهي ۽ O (N) اضافي جڳهه استعمال ڪندو آهي

ڏنل مسئلو هڪ ترتيب واري صف مان متوازن بائنري سرچ وڻ ٺاهڻ جي برابر آهي ۽ اسان knowاڻون ٿا ته ڪئين ترتيب ڏنل بائنري يا فهرست هڪ متوازن بائنري سرچ وڻ ۾ ڪئين بدلجي وڃي. جيڪڏهن اسان ڏنل مسئلي تي هڪ نظر وجهون ، اسان هڪ ترتيب واري ترتيب مان متوازن بائنري سرچ وڻ تعمير ڪرڻ واري مسئلي کي بدلائي سگهون ٿا.

خيال ڏنل بينڊ کي ترتيب ڏيڻ ۾ ترتيب ڏيڻ جي جال ۾ آهي ۽ نوڊس کي صف ۾ محفوظ ڪيو وڃي. صف ڊيٽا ۾ ترتيب وار ترتيب تي مشتمل هوندي. پوءِ اسان ترتيب ڏنل ترتيب کي متوازن ۾ تبديل ڪري ڇڏيو بائنري ڳولا وارو وڻ.

1. Traverse the given binary search tree in in-order traversal and store the nodes in an array, let the array be inOrderNodes.
2. The middle element of the array forms the root of the balanced BST and all the elements to the left of middle element forms the left sub-tree and all the elements to the right of middle element forms the right sub-tree.
3. Make root's left as the result of a recursive call for step 2. For left sub-tree the start index is start in step 2 and end index is mid - 1.
4. Make root's right as the result of a recursive call for step 2. For right sub-tree the start index is mid + 1 and end index is end in step 2.
5. Return root.

پيچيدگي تجزيي

وقت جي پيچيدگي = اي (ن) ، جئين اسان وٽ س treeو وڻ موجود آهي جوڙيون اسان وٽ هن الگوريٿم لاءِ لڪير وقت جي پيچيدگي آهي.
خلائي پيچيدگي = اي (ن) ، ڇاڪاڻ ته اسان سائيز جا هڪ صف استعمال ڪري رهيا آهيون n بائنري سرچ وڻ جي انڊرورس ٽراسل کي رکڻ لاءِ
جتي ڏنل ڏنل بائنري سرچ وڻ ۾ نمبر نون جو تعداد آهي.

جاوا ڪوڊ هڪ عام بي ايس ٽي کي متوازن BST ۾ تبديل ڪرڻ لاءِ

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

import java.util.ArrayList;
class ConvertANormalBSTToBalancedBST {
    // class representing node of a binary tree
    static class Node {
        int data;
        Node left, right;
        public Node(int data) {
            this.data = data;
        }
    }
    // function to print pre-order traversal of a binary tree
    private static void preOrder(Node root) {
        if (root != null) {
            System.out.print(root.data + " ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }
    // function to store the in-order traversal of a binary tree to an array
    private static void storeInOrderTraversal(Node root, ArrayList<Integer> inOrderNodes) {
        if (root != null) {
            storeInOrderTraversal(root.left, inOrderNodes);
            inOrderNodes.add(root.data);
            storeInOrderTraversal(root.right, inOrderNodes);
        }
    }
    private static Node convertSortedArrayToBalancedBST(ArrayList<Integer> inOrderNodes, int start, int end) {
        // Base Case
        if (start > end) {
            return null;
        }
        // middle element of the array forms the node
        int mid = (start + end) / 2;
        Node root = new Node(inOrderNodes.get(mid));
        // elements to the left of middle element forms left subtree
        root.left = convertSortedArrayToBalancedBST(inOrderNodes, start, mid - 1);
        // elements to the right of middle element forms right subtree
        root.right = convertSortedArrayToBalancedBST(inOrderNodes, mid + 1, end);
        // return root
        return root;
    }
    private static Node convertToBalancedBST(Node root) {
        // create an array
        ArrayList<Integer> inOrderNodes = new ArrayList<>();
        // store the in-order traversal in the array
        storeInOrderTraversal(root, inOrderNodes);
        // make balanced BST from sorted array
        return convertSortedArrayToBalancedBST(inOrderNodes, 0, inOrderNodes.size() - 1);
    }
    public static void main(String[] args) {
        // Example 1
        Node root1 = new Node(50);
        root1.left = new Node(23);
        root1.right = new Node(62);
        root1.left.left = new Node(17);
        root1.left.right = new Node(45);
        root1.left.left.left = new Node(3);
        root1.left.right.left = new Node(31);
        root1.left.right.right = new Node(48);
        root1 = convertToBalancedBST(root1);
        preOrder(root1);
        System.out.println();
        // Example 2
        Node root2 = new Node(7);
        root2.right = new Node(8);
        root2.right.right = new Node(9);
        root2 = convertToBalancedBST(root2);
        preOrder(root2);
        System.out.println();
    }
}
31 17 3 23 48 45 50 62 
8 7 9

عام بي ايس ٽي کي متوازن BST ۾ تبديل ڪرڻ لاءِ C ++ ڪوڊ

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

// class representing node of a binary tree 
class Node { 
    public: 
    int data; 
    Node *left; 
    Node *right; 
    
    Node(int d) { 
        data = d; 
        left = right = NULL; 
    } 
};

// function to print pre-order traversal of a binary tree
void preOrder(Node *root) {
    if (root != NULL) {
        cout<<root->data<<" ";
        preOrder(root->left);
        preOrder(root->right);
    }
}

// function to store the in-order traversal of a binary tree to an array
void storeInOrderTraversal(Node *root, vector<int> &inOrderNodes) {
    if (root != NULL) {
        storeInOrderTraversal(root->left, inOrderNodes);
        inOrderNodes.push_back(root->data);
        storeInOrderTraversal(root->right, inOrderNodes);
    }
}

Node* convertSortedArrayToBalancedBST(vector<int> &inOrderNodes, int start, int end) {
    // Base Case
    if (start > end) {
        return NULL;
    }
    
    // middle element of the array forms the node
    int mid = (start + end) / 2;
    Node *root = new Node(inOrderNodes[mid]);
    
    // elements to the left of middle element forms left subtree
    root->left = convertSortedArrayToBalancedBST(inOrderNodes, start, mid - 1);
    // elements to the right of middle element forms right subtree
    root->right = convertSortedArrayToBalancedBST(inOrderNodes, mid + 1, end);
    
    // return root
    return root;
}

Node* convertToBalancedBST(Node *root) {
    // create an array
    vector<int> inOrderNodes;
    // store the in-order traversal in the array
    storeInOrderTraversal(root, inOrderNodes);
    
    // make balanced BST from sorted array
    return convertSortedArrayToBalancedBST(inOrderNodes, 0, inOrderNodes.size() - 1);
}

int main() {
    // Example 1
    Node *root1 = new Node(50);
    root1->left = new Node(23);
    root1->right = new Node(62);
    root1->left->left = new Node(17);
    root1->left->right = new Node(45);
    root1->left->left->left = new Node(3);
    root1->left->right->left = new Node(31);
    root1->left->right->right = new Node(48);
    root1 = convertToBalancedBST(root1);
    preOrder(root1);
    cout<<endl;

    // Example 2
    Node *root2 = new Node(7);
    root2->right = new Node(8);
    root2->right->right = new Node(9);
    root2 = convertToBalancedBST(root2);
    preOrder(root2);
    cout<<endl;
    
    return 0;
}
31 17 3 23 48 45 50 62 
8 7 9