Претворба бинарног стабла у бинарно стабло претраживања помоћу СТЛ скупа  


Ниво тешкоће Средњи
Често питани у амазонка Цоурсера гоогле Заиста мицрософт ОИО собе
Бинарно стабло претраживања Бинарно дрво Дрво

Изјава о проблему  

Добили смо а бинарно стабло и морамо га претворити у бинарно стабло претраге. Проблем „Конверзија бинарног стабла у бинарно стабло претраживања помоћу СТЛ скупа“ тражи конверзију помоћу СТЛ скупа. Већ смо разговарали претварање бинарног стабла у БСТ али нисмо разговарали о конверзији помоћу Сет-а. Док је конверзија једна ствар коју треба проверити је да оригинална структура стабла мора остати иста.

Пример  

Улазни

Пин

Излаз

Претворба бинарног стабла у бинарно стабло претраживања помоћу СТЛ скупаПин

 

Приступ претварању бинарног стабла у БСТ помоћу Сет-а  

Већ смо разговарали о конверзији бинарног стабла у бинарно стабло претраживања, али овде ћемо користити уграђени СТЛ сет. Дакле, један од начина може бити да се прво направи уравнотежено бинарно стабло претраживања које је АВЛ дрво или црвено-црно дрво. А затим извршимо интерверзални прелазак новоствореног стабла и копирамо садржај натраг на оригинално стабло на сличан начин.

Горе разматрани приступ захтева стварање непотребног само-балансирајућег бинарног стабла. Да бисмо то избегли, разговарали смо о приступу заснован на низу. У том приступу прво смо урадили а преокрет од три, а затим сортирао низ. Опет са интерверзним преласком, заменили смо елементе у почетном стаблу.

Види такође
Роот до Леаф патх са циљним збиром Леетцоде Солутионс

У овом приступу нећемо створити низ, а затим га сортирати. Користићемо сет који елемент држи сортирано. Тако ћемо прећи дрво и наставити са уметањем елемента у сет. После тога, заменићемо елементе у датом стаблу.

код  

Ц ++ код за претварање бинарног стабла у БСТ помоћу Сет-а

#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

Анализа сложености  

Сложеност времена

О (Н лог Н),  где је Н број елемената у стаблу. Овде је логаритамски фактор дошао због скупа. Постављање структуре података захтева време дневника Н за уметање, претраживање и брисање елемента.

Види такође
Максимални низ из два дата низа који редослед одржавају исти

Сложеност простора

НА), овде смо користили додатни простор за чување чворова у скупу. Стога сам алгоритам за конверзију има линеарну сложеност простора, а програм у целини такође линеарну сложеност простора.