Пераўтварэнне двайковага дрэва ў двайковае дрэва пошуку з выкарыстаннем набору STL


Узровень складанасці серада
Часта пытаюцца ў амазонка Coursera Google Сапраўды Microsoft Нумары OYO
Двайковае дрэва пошуку Двайковае дрэва дрэва

Пастаноўка праблемы

Нам дадзена бінарнае дрэва і нам трэба пераўтварыць яго ў двайковае дрэва пошуку. Праблема «Пераўтварэнне двайковага дрэва ў двайковае дрэва пошуку з выкарыстаннем набору STL» просіць зрабіць пераўтварэнне з выкарыстаннем набору STL. Мы ўжо абмяркоўвалі пераўтварэнне бінарнага дрэва ў BST але мы не абмяркоўвалі пераўтварэнне з дапамогай Set. Пры пераўтварэнні трэба праверыць, што зыходная структура дрэва павінна застацца ранейшай.

Прыклад

уваход

выхад

Пераўтварэнне двайковага дрэва ў двайковае дрэва пошуку з выкарыстаннем набору STL

 

Падыход для пераўтварэння двайковага дрэва ў BST з дапамогай Set

Мы ўжо абмяркоўвалі пераўтварэнне двайковага дрэва ў двайковае дрэва пошуку, але тут мы будзем выкарыстоўваць убудаваны набор STL. Такім чынам, адным са спосабаў можа быць спачатку пабудаваць збалансаванае двайковае дрэва пошуку, якое з'яўляецца Дрэва AVL альбо чырвона-чорнае дрэва. А потым мы робім абход новага створанага дрэва і капіруем змесціва назад у зыходнае дрэва аналагічным чынам.

Абмеркаваны вышэй падыход патрабуе стварэння непатрэбнага самабалансавальнага бінарнага дрэва. Такім чынам, каб пазбегнуць гэтага, мы абмеркавалі падыход, заснаваны на масівах. Пры такім падыходзе мы спачатку зрабілі абход з трох, а потым адсартаваў масіў. Зноў жа, у выніку парадку абходу мы замянілі элементы ў пачатковым дрэве.

Пры такім падыходзе мы не будзем ствараць масіў, а потым сартаваць яго. Мы будзем выкарыстоўваць набор, які захоўвае элемент у адсартаваным выглядзе. Такім чынам, мы пройдзем дрэва і працягнем ўстаўляць элемент у камплект. Пасля мы заменім элементы ў дадзеным дрэве.

код

Код C ++ для пераўтварэння бінарнага дрэва ў BST з дапамогай Set

#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

Код Java для пераўтварэння двайковага дрэва ў BST з дапамогай Set

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

Аналіз складанасці

Складанасць часу

O (N часопіс N),  дзе N - колькасць элементаў у дрэве. Тут лагарыфмічны каэфіцыент прыйшоў з-за мноства. Усталёўка структуры дадзеных патрабуе часопіса N часу на ўстаўку, пошук і выдаленне элемента.

Касмічная складанасць

O (N), тут мы выкарысталі дадатковае месца для захоўвання вузлоў у наборы. Такім чынам, сам алгарытм пераўтварэння мае лінейную касмічную складанасць, а праграма ў цэлым таксама лінейную касмічную складанасць.