ایک عام BST کو متوازن BST میں تبدیل کریں


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے امریکن ایکسپریس ByteDance کیپٹل ایک Grofers انٹیل تقسیم Zoho
ثنائی تلاش درخت ثنائی درخت درخت

مسئلہ یہ بیان

بائنری سرچ ٹری (BST) دیئے گئے ، بی ایس ٹی کو متوازن بائنری سرچ ٹری میں تبدیل کرنے کے لئے الگورتھم لکھیں۔ ایک متوازن ثنائی تلاش کا درخت بائنری سرچ ٹری کے سوا کچھ نہیں ہے جس کے بائیں سب سبری اور دائیں سب ٹری کی اونچائی کے درمیان فرق 1 سے کم یا اس کے برابر ہے۔

مثال کے طور پر

ان پٹ

ایک عام BST کو متوازن BST میں تبدیل کریں

آؤٹ پٹ

ایک عام BST کو متوازن BST میں تبدیل کریں

پیشگی آرڈر: 31 17 3 23 48 45 50 62

ان پٹ

ایک عام BST کو متوازن BST میں تبدیل کریں

آؤٹ پٹ

ایک عام BST کو متوازن BST میں تبدیل کریں

پیشگی ترتیب: 8 7 9

 

عام BST کو متوازن BST میں تبدیل کرنے کیلئے الگورتھم

ایک نقطہ نظر یہ ہوسکتا ہے کہ دیئے گئے بائنری سرچ ٹری کو ترتیب سے فیشن میں عبور کیا جائے اور عناصر کو خود توازن والے درخت میں محفوظ کیا جاسکے ، جیسے AVL درخت یا سرخ رنگ کا درخت۔ یہ نقطہ نظر زیادہ موثر نہیں ہے ، یہ O (N لاگ N) وقت لیتا ہے اور O (N) اضافی جگہ استعمال کرتا ہے۔

دیا ہوا مسئلہ حل شدہ صف سے متوازن بائنری سرچ ٹری کی تعمیر کے مترادف ہے اور ہم جانتے ہیں کہ ترتیب شدہ سرنی یا فہرست کو متوازن بائنری سرچ ٹری میں کیسے تبدیل کیا جائے۔ اگر ہم دیئے گئے مسئلے کے قریب قریب سے جائزہ لیں تو ہم اس مسئلے کو حل شدہ صف سے متوازن بائنری سرچ ٹری کی تعمیر میں تبدیل کر سکتے ہیں۔

خیال یہ ہے کہ دیئے گئے بی ایس ٹی کو آرڈر ٹروراسل میں عبور کریں اور نوڈس کو ایک صف میں محفوظ کریں۔ سرنی ترتیب میں ڈیٹا پر مشتمل ہوگی۔ پھر ہم ترتیب شدہ سرنی کو متوازن میں تبدیل کرتے ہیں بائنری تلاش درخت.

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.

پیچیدگی کا تجزیہ

وقت کی پیچیدگی = O (n) ، چونکہ ہم پورے درخت کو عبور کرتے ہیں نوڈس ہمارے پاس اس الگورتھم کے ل line لین ٹائم پیچیدگی ہے۔
خلائی پیچیدگی = O (n) ، کیونکہ ہم سائز کا ایک صف استعمال کررہے ہیں n بائنری تلاش درخت کی inord traversal کے ذخیرہ کرنے کے لئے.
جہاں دیئے گئے بائنری سرچ ٹری میں نوڈس کی تعداد ہے۔

عام BST کو متوازن 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 کو متوازن 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