STLセットを使用した二分木から二分探索木への変換


難易度 ミディアム
よく聞かれる Amazon (アマゾン) Coursera Googleポリシー 確かに マイクロソフト OYOルーム
二分探索木 二分木

問題文

私たちは与えられます 二分木 そしてそれをに変換する必要があります 二分探索木。 問題「STLセットを使用したバイナリツリーからバイナリ検索ツリーへの変換」では、STLセットを使用して変換を行うように求められます。 すでに議論しました 二分木をBSTに変換する ただし、Setを使用した変換については説明していません。 変換中にチェックする必要があることのXNUMXつは、元のツリー構造が同じままでなければならないということです。

入力

出力

STLセットを使用した二分木から二分探索木への変換

 

Setを使用してバイナリツリーをBSTに変換するアプローチ

二分探索木から二分探索木への変換についてはすでに説明しましたが、ここでは組み込みのSTLセットを使用します。 したがって、方法のXNUMXつは、最初に平衡二分探索木を構築することです。 AVLツリーまたは赤黒 木。 次に、新しく作成されたツリーを順番にトラバースし、同様の順序でコンテンツを元のツリーにコピーして戻します。

上で説明したアプローチでは、不要な自己平衡二分木を作成する必要があります。 したがって、これを回避するために、アレイベースのアプローチについて説明しました。 そのアプローチでは、最初に トラバーサル XNUMXつのうち、配列を並べ替えました。 再び順序どおりのトラバーサルを使用して、最初のツリーの要素を置き換えました。

このアプローチでは、配列を作成してから並べ替えることはしません。 要素をソートされた方法で保持するセットを使用します。 したがって、ツリーをトラバースし、要素をに挿入し続けます セッションに。 その後、指定されたツリーの要素を置き換えます。

コード

Setを使用してバイナリツリーをBSTに変換するC ++コード

#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

Setを使用してバイナリツリーをBSTに変換するJavaコード

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 log N)、  ここで、Nはツリー内の要素の数です。 ここでは、対数係数がセットのために来ました。 データ構造の設定には、要素の挿入、検索、削除にlogN時間が必要です。

スペースの複雑さ

オン)、ここでは、セット内のノードを格納するために余分なスペースを使用しました。 したがって、変換のアルゴリズム自体には線形空間の複雑さがあり、プログラム全体にも線形空間の複雑さがあります。