STL 세트를 사용하여 이진 트리에서 이진 검색 트리로 변환


난이도 중급
자주 묻는 질문 아마존 Coursera 구글 과연 Microsoft 오요 룸
이진 검색 트리 이진 트리 나무

문제 정책

우리는 주어진 이진 트리 그리고 우리는 그것을 이진 검색 트리. “STL 세트를 이용한 이진 트리에서 이진 검색 트리로 변환”문제는 STL 세트를 사용하여 변환을 요청합니다. 우리는 이미 논의했습니다 이진 트리를 BST로 변환 그러나 우리는 Set를 사용한 변환에 대해 논의하지 않았습니다. 변환하는 동안 확인해야 할 한 가지는 원래 트리 구조가 동일하게 유지되어야한다는 것입니다.

입력

산출

STL 세트를 사용하여 이진 트리에서 이진 검색 트리로 변환

 

Set을 사용하여 이진 트리를 BST로 변환하는 방법

우리는 이미 이진 트리를 이진 검색 트리로 변환하는 것에 대해 논의했지만 여기서는 내장 STL 세트를 사용할 것입니다. 따라서 방법 중 하나는 먼저 균형 잡힌 이진 검색 트리를 구성하는 것입니다. AVL 트리 또는 레드-블랙 나무. 그런 다음 새로 생성 된 트리를 순서대로 순회하고 내용을 비슷한 순서대로 원래 트리에 다시 복사합니다.

위에서 논의한 접근 방식은 불필요한 자체 균형 이진 트리를 생성해야합니다. 따라서이를 피하기 위해 어레이 기반 접근 방식을 논의했습니다. 그 접근 방식에서 우리는 먼저 순회 세 가지 중 하나를 선택한 다음 배열을 정렬했습니다. 다시 inorder traversal로 초기 트리의 요소를 대체했습니다.

이 접근 방식에서는 배열을 만든 다음 정렬하지 않습니다. 요소를 정렬 된 방식으로 유지하는 세트를 사용합니다. 따라서 우리는 트리를 가로 질러 계속해서 요소를 세트. 나중에 주어진 트리의 요소를 교체합니다.

암호

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은 트리의 요소 수입니다. 여기에서 대수 인자는 세트로 인해 왔습니다. 데이터 구조를 설정하려면 요소를 삽입, 검색 및 삭제하려면 log N 시간이 필요합니다.

공간 복잡성

의 위에), 여기서는 세트에 노드를 저장하기 위해 추가 공간을 사용했습니다. 따라서 변환 알고리즘 자체에는 선형 공간 복잡성이 있고 프로그램 전체에는 선형 공간 복잡성도 있습니다.