بی ایس ٹی کو بائنری ٹری میں تبدیل کریں جتنا کہ ہر کلید میں تمام بڑی کنجیوں کا مجموعہ شامل کیا جاتا ہے


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے فیس بک
ثنائی تلاش درخت ثنائی درخت درخت

بائنری سرچ ٹری دیئے گئے ، بی ایس ٹی کو بائنری میں تبدیل کرنے کے لئے الگورتھم لکھیں درخت اس طرح کہ تمام بڑی چابیاں کا جوہر ہر چابی میں شامل ہوجاتا ہے۔

مثال کے طور پر

ان پٹ

بی ایس ٹی کو بائنری ٹری میں تبدیل کریں جتنا کہ ہر کلید میں تمام بڑی کنجیوں کا مجموعہ شامل کیا جاتا ہے

آؤٹ پٹ

بی ایس ٹی کو بائنری ٹری میں تبدیل کریں جتنا کہ ہر کلید میں تمام بڑی کنجیوں کا مجموعہ شامل کیا جاتا ہے

پیشگی آرڈر: 81 87 88 54 69 34

بولی اپروچ

خیال بہت آسان ہے ، گزرنا تمام نوڈس ایک ایک کرکے ، اور ہر نوڈ کے ل again ایک بار پھر پورے درخت کو عبور کریں اور اس سے زیادہ نوڈس کا مجموعہ تلاش کریں۔ رقم کو ایک صف میں جمع کریں اور کمپیوٹنگ کے بعد ، تمام نوڈس کے لئے رقم ، نوڈس کو ان کی مناسبت سے رقم میں اضافہ کریں۔ یہ نقطہ نظر کسی بھی عام بائنری درخت کے لئے لاگو ہے خاص طور پر بی ایس ٹی کے لئے نہیں۔

  1. دیئے گئے بی ایس ٹی کو آرڈر کی شکل میں منتقل کریں۔
  2. ہر نوڈ کے ل again ، درخت کو ترتیب سے ترتیب میں عبور کریں اور ان تمام نوڈس کا مجموعہ تلاش کریں جو موجودہ نوڈ سے زیادہ ہیں۔
  3. رقم کو کسی صف یا فہرست میں اسٹور کریں۔
  4. تمام نوڈس کو گھومنے کے بعد ، درخت کو پھر ترتیب سے ترتیب دیں اور ہر نوڈ کو اس کے مطابق رقم کے ساتھ سرنی یا فہرست میں اضافہ کریں۔

وقت کی پیچیدگی = O (n)2)
خلائی پیچیدگی = O (h)
جہاں درخت میں نوڈس کی تعداد ہے۔

جاوا کوڈ برائے بی ایس ٹی کو بائنری ٹری میں تبدیل کریں

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class ConvertABSTToABinaryTreeSuchThatSumOfAllGreaterKeysIsAddedToEveryKey {
    // class representing the node of a binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    // function to print the 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);
        }
    }

    private static int findSum(Node root, int value) {
        // if root is null, sum is 0
        if (root == null) {
            return 0;
        }

        // initialize sum as 0
        int sum = 0;

        // traverse the tree and find the sum of all the values greater than value
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            Node curr = queue.poll();
            if (curr.data > value) {
                sum += curr.data;
            }

            if (curr.left != null)
                queue.add(curr.left);
            if (curr.right != null)
                queue.add(curr.right);
        }

        // return sum
        return sum;
    }

    private static void formSumList(Node root, Node curr, ArrayList<Integer> sumList) {
        // traverse the tree in in-order form and for each node
        // calculate the sum of elements greater than it
        if (curr != null) {
            formSumList(root, curr.left, sumList);

            // Check for all the nodes to find the sum
            int sum = findSum(root, curr.data);
            sumList.add(sum);

            formSumList(root, curr.right, sumList);
        }
    }

    private static void  convertToGreaterSumTree(Node root, ArrayList<Integer> sumList) {
        // traverse the tree in in-order form and for each node
        // increment its value by sum
        if (root != null) {
            convertToGreaterSumTree(root.left, sumList);

            // increment this value
            root.data += sumList.get(0);
            sumList.remove(0);

            convertToGreaterSumTree(root.right, sumList);
        }
    }

    public static void main(String[] args) {
        // Example Tree
        Node root = new Node(12);
        root.left = new Node(6);
        root.right = new Node(20);
        root.left.left = new Node(1);
        root.right.left = new Node(15);
        root.right.right =  new Node(34);

        ArrayList<Integer> sumList = new ArrayList<>();
        formSumList(root, root, sumList);

        convertToGreaterSumTree(root, sumList);

        preOrder(root);
        System.out.println();
    }
}
81 87 88 54 69 34

سی ++ کوڈ برائے بی ایس ٹی کو بائنری ٹری میں تبدیل کریں

#include <iostream> 
#include<vector> 
#include<queue> 
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 the preorder traversal of a binary tree 
void preOrder(Node *root) { 
    if (root != NULL) { 
        cout<<root->data<<" "; 
        preOrder(root->left); 
        preOrder(root->right); 
    } 
} 

int findSum(Node *root, int value) { 
    // if root is null, sum is 0 
    if (root == NULL) { 
        return 0; 
    } 
    
    // initialize sum as 0 
    int sum = 0; 
    
    // traverse the tree and find the sum of all the values greater than value 
    queue<Node*> q; 
    q.push(root); 
    while (!q.empty()) { 
        Node *curr = q.front(); 
        q.pop(); 
        if (curr->data > value) { 
            sum += curr->data; 
        } 
        if (curr->left != NULL) { 
            q.push(curr->left); 
        } 
        if (curr->right != NULL) { 
            q.push(curr->right); 
        } 
    } 
    
    // return sum 
    return sum; 
} 

void formSumList(Node *root, Node *curr, vector<int> &sumList) { 
    // traverse the tree in in-order form and for each node 
    // calculate the sum of elements greater than it 
    if (curr != NULL) { 
        formSumList(root, curr->left, sumList); 
        
        // Check for all the nodes to find the sum 
        int sum = findSum(root, curr->data); 
        sumList.push_back(sum); 
        formSumList(root, curr->right, sumList); 
    } 
} 

void convertToGreaterSumTree(Node *root, vector<int> &sumList) { 
    // traverse the tree in in-order form and for each node 
    // replace its value with the corresponding sum 
    if (root != NULL) { 
        convertToGreaterSumTree(root->left, sumList); 
        // change this value 
        root->data += sumList[0]; 
        sumList.erase(sumList.begin()); 
        convertToGreaterSumTree(root->right, sumList); 
    } 
} 

int main() { 
    // Example Tree 
    Node *root = new Node(12); 
    root->left = new Node(6); 
    root->right = new Node(20); 
    root->left->left = new Node(1); 
    root->right->left = new Node(15); 
    root->right->right = new Node(34); 
    
    vector<int> sumList; 
    formSumList(root, root, sumList); 
    
    convertToGreaterSumTree(root, sumList); 
    preOrder(root); 
    cout<<endl; 
    
    return 0; 
}
81 87 88 54 69 34

زیادہ سے زیادہ نقطہ نظر

مندرجہ بالا نقطہ نظر کو بی ایس ٹی کے لئے بہتر بنایا جاسکتا ہے ، کیونکہ ایک بی ایس ٹی ڈیٹا کو بہت ہی مخصوص انداز میں اسٹور کرتا ہے۔
بی ایس ٹی کو ریورس ترتیب میں ، یعنی دائیں-> روٹ-> بائیں شکل سے عبور کریں۔ اس طرح ہم نوڈس کو کم ہوتی ہوئی ترتیب میں عبور کریں گے اور کسی بھی نوڈ کا دورہ کرنے سے پہلے ہم اس سے زیادہ نوڈس کا دورہ کریں گے ، لہذا ہم صرف ایک ٹریورسال میں نوڈس سے زیادہ تمام نوڈس کا مجموعہ تلاش کرسکتے ہیں لہذا اس ٹراورسال انکریمنٹ کے دوران ہر نوڈ میں اس سے زیادہ نوڈس کے جوڑے کے حساب سے۔

  1. متغیر رقم کو 0 کے طور پر شروع کریں ، یہ حوالہ کے ذریعے منظور ہوتا ہے یا عالمی سطح پر تعریف کیا جاتا ہے۔
  2. بی ایس ٹی کو الٹ ان آرڈر فارم میں منتقل کریں ، اس طرح سے ہم ڈیٹا کو کم ہوتے ہوئے حاصل کریں گے۔
  3. ہر ایک نوڈ کے لئے ، جس سے ہم گزرتے ہیں ، اس کی قیمت کے حساب سے اضافہ کرتے ہیں ، اور نوڈ کی اصل ویلیو (اپ ڈیٹ کرنے سے پہلے) کے حساب سے انکریمینٹ جوڑ دیتے ہیں۔

وقت کی پیچیدگی = اے (ن)
خلائی پیچیدگی = O (h)
جہاں n دیئے گئے BST میں نوڈس کی کل تعداد ہے۔

جاوا کوڈ برائے بی ایس ٹی کو بائنری ٹری میں تبدیل کریں

public class ConvertABSTToABinaryTreeSuchThatSumOfAllGreaterKeysIsAddedToEveryKey {
    // 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 the 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);
        }
    }

    // sum defined globally and initialized as 0
    private static int sum = 0;

    private static void convertToGreaterSumTree(Node root) {
        // traverse the tree in reverse in-order form
        if (root != null) {
            convertToGreaterSumTree(root.right);

            // update the sum and increment the node's value
            int prevValue = root.data;
            root.data += sum;
            sum += prevValue;

            convertToGreaterSumTree(root.left);
        }
    }

    public static void main(String[] args) {
        // Example Tree
        Node root = new Node(12);
        root.left = new Node(6);
        root.right = new Node(20);
        root.left.left = new Node(1);
        root.right.left = new Node(15);
        root.right.right =  new Node(34);

        convertToGreaterSumTree(root);

        preOrder(root);
        System.out.println();
    }
}
81 87 88 54 69 34

سی ++ کوڈ برائے بی ایس ٹی کو بائنری ٹری میں تبدیل کریں

#include <iostream>
#include<vector>
#include<queue>
using namespace std;

// sum defined globally and initialized as 0
int sum = 0;

// 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 the preorder traversal of a binary tree
void preOrder(Node *root) {
    if (root != NULL) {
        cout<<root->data<<" ";
        preOrder(root->left);
        preOrder(root->right);
    }
}

void convertToGreaterSumTree(Node *root) {
    // traverse the tree in reverse in-order form
    if (root != NULL) {
        convertToGreaterSumTree(root->right);
        
        // update the sum and the node's value
        int prevValue = root->data;
        root->data += sum;
        sum += prevValue;
        
        convertToGreaterSumTree(root->left);
    }
}

int main() {
    // Example Tree
    Node *root = new Node(12);
    root->left = new Node(6);
    root->right = new Node(20);
    root->left->left = new Node(1);
    root->right->left = new Node(15);
    root->right->right =  new Node(34);

    convertToGreaterSumTree(root);

    preOrder(root);
    cout<<endl;
    
    return 0;
}
81 87 88 54 69 34

حوالہ 1     حوالہ 2