ਬਾਈਨਰੀ ਟਰੀ ਤੋਂ ਬਾਈਨਰੀ ਖੋਜ ਟ੍ਰੀ ਪਰਿਵਰਤਨ ਨੂੰ ਐਸਟੀਐਲ ਸੈੱਟ ਦੀ ਵਰਤੋਂ ਕਰਦਿਆਂ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ Coursera ਗੂਗਲ ਅਸਲ ਵਿੱਚ Microsoft ਦੇ ਓਏ ਕਮਰੇ
ਬਾਈਨਰੀ ਖੋਜ ਲੜੀ ਬਾਈਨਰੀ ਟਰੀ ਟ੍ਰੀ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਸਾਨੂੰ ਇੱਕ ਦਿੱਤਾ ਗਿਆ ਹੈ ਬਾਈਨਰੀ ਟਰੀ ਅਤੇ ਸਾਨੂੰ ਇਸਨੂੰ ਏ ਵਿਚ ਬਦਲਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ ਬਾਈਨਰੀ ਖੋਜ ਟਰੀ. ਸਮੱਸਿਆ “ਬਾਈਨਰੀ ਟ੍ਰੀ ਤੋਂ ਬਾਈਨਰੀ ਸਰਚ ਟ੍ਰੀ ਰੂਪਾਂਤਰਣ ਦੀ ਵਰਤੋਂ ਐਸਟੀਐਲ ਸੈੱਟ ਦੀ ਵਰਤੋਂ ਨਾਲ” ਐਸਟੀਐਲ ਸੈੱਟ ਦੀ ਵਰਤੋਂ ਨਾਲ ਤਬਦੀਲੀ ਕਰਨ ਲਈ ਕਹਿੰਦੀ ਹੈ. ਅਸੀਂ ਪਹਿਲਾਂ ਹੀ ਵਿਚਾਰ ਵਟਾਂਦਰੇ ਕੀਤੇ ਹਨ ਬਾਈਨਰੀ ਟਰੀ ਨੂੰ ਬੀਐਸਟੀ ਵਿੱਚ ਬਦਲਣਾ ਪਰ ਅਸੀਂ ਸੈੱਟ ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਪਰਿਵਰਤਨ ਬਾਰੇ ਨਹੀਂ ਵਿਚਾਰਿਆ ਸੀ. ਤਬਦੀਲੀ ਕਰਨ ਵੇਲੇ ਇਕ ਚੀਜ ਜਿਸ ਦੀ ਜਾਂਚ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੁੰਦੀ ਹੈ ਉਹ ਇਹ ਹੈ ਕਿ ਅਸਲ ਰੁੱਖ structureਾਂਚਾ ਇਕੋ ਜਿਹਾ ਰਹਿਣਾ ਚਾਹੀਦਾ ਹੈ.

ਉਦਾਹਰਨ

ਇੰਪੁੱਟ

ਆਉਟਪੁੱਟ

ਬਾਈਨਰੀ ਟਰੀ ਤੋਂ ਬਾਈਨਰੀ ਖੋਜ ਟ੍ਰੀ ਪਰਿਵਰਤਨ ਨੂੰ ਐਸਟੀਐਲ ਸੈੱਟ ਦੀ ਵਰਤੋਂ ਕਰਦਿਆਂ

 

ਸੈੱਟ ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਬਾਈਨਰੀ ਟਰੀ ਨੂੰ ਬੀਐਸਟੀ ਵਿੱਚ ਬਦਲਣ ਦੀ ਪਹੁੰਚ

ਅਸੀਂ ਪਹਿਲਾਂ ਹੀ ਬਾਈਨਰੀ ਟਰੀ ਨੂੰ ਬਾਈਨਰੀ ਸਰਚ ਟ੍ਰੀ ਵਿੱਚ ਤਬਦੀਲ ਕਰਨ ਬਾਰੇ ਵਿਚਾਰ ਵਟਾਂਦਰੇ ਕੀਤੇ ਹਨ, ਪਰ ਇੱਥੇ ਅਸੀਂ ਇਨਬਿਲਟ ਐਸਟੀਐਲ ਸੈਟ ਦੀ ਵਰਤੋਂ ਕਰਾਂਗੇ. ਇਸ ਲਈ ਇਕ firstੰਗ ਇਹ ਹੋ ਸਕਦਾ ਹੈ ਕਿ ਪਹਿਲਾਂ ਸੰਤੁਲਿਤ ਬਾਈਨਰੀ ਖੋਜ ਲੜੀ ਦਾ ਨਿਰਮਾਣ ਕੀਤਾ ਜਾਵੇ ਜੋ ਕਿ ਏਵੀਐਲ ਦਾ ਰੁੱਖ ਜਾਂ ਲਾਲ-ਕਾਲਾ ਰੁੱਖ. ਅਤੇ ਫਿਰ ਅਸੀਂ ਨਵੇਂ ਬਣੇ ਰੁੱਖ ਦੀ ਇਕ ਅੰਦਰੂਨੀ ਟ੍ਰਾਵਰਸਾਲ ਕਰਦੇ ਹਾਂ ਅਤੇ ਸਮਾਨ ਨੂੰ ਉਸੇ ਹੀ ਅੰਦਰੂਨੀ ਅੰਦਾਜ਼ ਵਿਚ ਵਾਪਸ ਅਸਲ ਰੁੱਖ ਤੇ ਕਾਪੀ ਕਰਦੇ ਹਾਂ.

ਉਪਰੋਕਤ ਵਿਚਾਰ ਵਟਾਂਦਰੇ ਲਈ ਇੱਕ ਬੇਲੋੜੀ ਸਵੈ-ਸੰਤੁਲਨ ਬਾਈਨਰੀ ਟਰੀ ਦੀ ਸਿਰਜਣਾ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਇਸ ਤੋਂ ਬਚਣ ਲਈ ਅਸੀਂ ਐਰੇ-ਅਧਾਰਤ ਪਹੁੰਚ ਬਾਰੇ ਵਿਚਾਰ-ਵਟਾਂਦਰਾ ਕੀਤਾ. ਉਸ ਪਹੁੰਚ ਵਿਚ, ਅਸੀਂ ਪਹਿਲਾਂ ਏ ਟ੍ਰੈਵਲ ਤਿੰਨਾਂ ਵਿਚੋਂ ਅਤੇ ਫਿਰ ਐਰੇ ਨੂੰ ਕ੍ਰਮਬੱਧ ਕੀਤਾ. ਦੁਬਾਰਾ ਇਕ ਅੰਦਰੂਨੀ ਟ੍ਰਾਵਰਸਲ ਨਾਲ, ਅਸੀਂ ਸ਼ੁਰੂਆਤੀ ਰੁੱਖ ਵਿਚਲੇ ਤੱਤ ਬਦਲ ਦਿੱਤੇ.

ਇਸ ਪਹੁੰਚ ਵਿੱਚ, ਅਸੀਂ ਇੱਕ ਐਰੇ ਨਹੀਂ ਬਣਾਵਾਂਗੇ ਅਤੇ ਫਿਰ ਇਸ ਨੂੰ ਸੌਰਟ ਕਰਾਂਗੇ. ਅਸੀਂ ਇੱਕ ਸੈੱਟ ਦੀ ਵਰਤੋਂ ਕਰਾਂਗੇ ਜੋ ਤੱਤ ਨੂੰ ਕ੍ਰਮਬੱਧ ਰੂਪ ਵਿੱਚ ਰੱਖਦਾ ਹੈ. ਇਸ ਤਰ੍ਹਾਂ ਅਸੀਂ ਰੁੱਖ ਨੂੰ ਪਾਰ ਕਰਾਂਗੇ ਅਤੇ ਤੱਤ ਨੂੰ. ਵਿੱਚ ਪਾਉਂਦੇ ਰਹਾਂਗੇ ਸੈੱਟ. ਬਾਅਦ ਵਿਚ, ਅਸੀਂ ਦਿੱਤੇ ਗਏ ਰੁੱਖ ਵਿਚਲੇ ਤੱਤ ਬਦਲ ਦੇਵਾਂਗੇ.

ਕੋਡ

ਸੈੱਟ ਦੀ ਵਰਤੋਂ ਕਰਦਿਆਂ ਬਾਈਨਰੀ ਟਰੀ ਨੂੰ ਬੀਐਸਟੀ ਵਿੱਚ ਬਦਲਣ ਲਈ ਸੀ ++ ਕੋਡ

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

// defines the structure of a tree node
struct node{
    int data;
    node* left;
    node* right;
};

// inserts the given tree elements into the set
void insertIntoSet(node* root, set<int> &treeSet){
    if(root){
        insertIntoSet(root->left, treeSet);
        treeSet.insert(root->data);
        insertIntoSet(root->right, treeSet);
    }
}

// replace the elements of the initial tree
// with elements in treeSet in in-order fashion
void modifyBinaryTreeIntoBST(node* root, set<int> &treeSet)
{
    if(root){
        modifyBinaryTreeIntoBST(root->left, treeSet);
        root->data = *(treeSet.begin());
        treeSet.erase(treeSet.begin());
        modifyBinaryTreeIntoBST(root->right, treeSet);
    }
}

// Converts Binary tree to BST
void binaryTreeToBST(node* root)
{
    set<int> treeSet;
    // first fill the set
    insertIntoSet(root, treeSet);
    // then replace the elements in initial tree
    modifyBinaryTreeIntoBST(root, treeSet);
}

// creates and returns a new node with supplied node value
node* create(int data){
    node *tmp = new node();
    tmp->data = data;
    tmp->left = tmp->right = NULL;
    return tmp;
}

// simple in-order traversal
void inorder(node *root){
    if(root){
        inorder(root->left);
        cout<<root->data;
        inorder(root->right);
    }
}

int main()
{
    // constructing a binary tree
    // same as shown above
    node *root = create(1);
    root->right = create(2);
    root->right->left = create(4);
    root->right->left->left = create(5);
    root->right->left->right = create(3);

    cout<<"Inorder Traversal of given binary tree"<<endl;
    inorder(root);cout<<endl;
    binaryTreeToBST(root);
    cout<<"Inorder Traversal of modified tree\n";
    inorder(root);
}
Inorder Traversal of given binary tree
15432
Inorder Traversal of modified tree
12345

ਜਾਵਾ ਕੋਡ ਸੈੱਟ ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਬਾਈਨਰੀ ਟਰੀ ਨੂੰ ਬੀਐਸਟੀ ਵਿੱਚ ਬਦਲਣ ਲਈ

import java.util.*;
import java.lang.*;
import java.io.*;
 
class node{
  int data;
  node left;
  node right;
}
 
class Tree{
  // creates and returns a new node with supplied node value
  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = null;
    tmp.right = null;
    return tmp;
  }

  // inserts the given tree elements into the set
  static void insertIntoSet(node root, TreeSet<Integer> treeSet){
    if(root != null){
      insertIntoSet(root.left, treeSet);
      treeSet.add(root.data);
      insertIntoSet(root.right, treeSet);
    }
  }

  // replace the elements of the initial tree
  // with elements in treeSet in in-order fashion
  static void modifyBinaryTreeIntoBST(node root, TreeSet<Integer> treeSet)
  {
    if(root != null){
      modifyBinaryTreeIntoBST(root.left, treeSet);
      root.data = treeSet.pollFirst();
      modifyBinaryTreeIntoBST(root.right, treeSet);
    }
  }

  // Converts Binary tree to BST
  static void binaryTreeToBST(node root)
  {
    TreeSet<Integer> treeSet = new TreeSet<>();
    // first fill the set
    insertIntoSet(root, treeSet);
    // then replace the elements in initial tree
    modifyBinaryTreeIntoBST(root, treeSet);
  }

  // simple in-order traversal
  static void inorder(node root){
    if(root != null){
      inorder(root.left);
      System.out.print(root.data);
      inorder(root.right);
    }
  }

  public static void main(String[] args)
  {
    // constructing a binary tree
    // same as shown above
    node root = create(1);
    root.right = create(2);
    root.right.left = create(4);
    root.right.left.left = create(5);
    root.right.left.right = create(3);

    System.out.println("Inorder Traversal of given binary tree");
    inorder(root);
    System.out.println();
    binaryTreeToBST(root);
    System.out.println("Inorder Traversal of modified tree");
    inorder(root);
  }
}
Inorder Traversal of given binary tree
15432
Inorder Traversal of modified tree
12345

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ ਲਗ ਐਨ),  ਜਿੱਥੇ N ਰੁੱਖ ਵਿਚਲੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਹੈ. ਇੱਥੇ ਲਾਗਰਿਥਮਿਕ ਕਾਰਕ ਸੈੱਟ ਦੇ ਕਾਰਨ ਆਇਆ. ਸੈਟ ਡੈਟਾ structureਾਂਚੇ ਨੂੰ ਐਲੀਮੈਂਟ ਨੂੰ ਪਾਉਣ, ਖੋਜ ਕਰਨ ਅਤੇ ਮਿਟਾਉਣ ਲਈ ਲੌਗ ਐਨ ਦੀ ਲੋੜ ਹੁੰਦੀ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਇਥੇ ਅਸੀਂ ਸੈੱਟ ਵਿਚ ਨੋਡਾਂ ਨੂੰ ਸਟੋਰ ਕਰਨ ਲਈ ਵਾਧੂ ਜਗ੍ਹਾ ਦੀ ਵਰਤੋਂ ਕੀਤੀ ਹੈ. ਇਸ ਤਰ੍ਹਾਂ ਪਰਿਵਰਤਨ ਲਈ ਐਲਗੋਰਿਦਮ ਵਿਚ ਆਪਣੇ ਆਪ ਵਿਚ ਲੀਨੀਅਰ ਸਪੇਸ ਗੁੰਝਲਤਾ ਹੁੰਦੀ ਹੈ ਅਤੇ ਸਮੁੱਚੇ ਪ੍ਰੋਗ੍ਰਾਮ ਵਿਚ ਵੀ ਲੀਨੀਅਰ ਸਪੇਸ ਗੁੰਝਲਤਾ ਹੁੰਦੀ ਹੈ.