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

<시간/>

주어진 Binary Tree의 경우 Binary Tree의 원래 구조를 그대로 유지하는 방식으로 Binary Search Tree로 변환합니다.

이 솔루션은 어레이 기반 솔루션 대신 C++ STL 세트를 사용합니다.

예시

예시 1

입력

출력

예시 2

입력

      11
     /   \
    31    16
   /        \
 21         6

출력

     16
    /   \
  11     21
 /         \
 6          31

해결책

inorder traversal을 수행하는 동안 집합의 이진 트리 항목을 복사해야 합니다. 이것은 O(n log n) 시간을 소비합니다. C++ STL(Standard Template Library)에서 설정한 설정은 Red Black Tree, AVL Tree 등과 같은 Self Balancing Binary Search Tree를 사용하여 구현됩니다.
C++의 집합은 삽입, 검색, 삭제 등의 각 작업이 O(log n) 시간을 소비하기 때문에 자체 균형 이진 검색 트리를 구현하는 데 사용되므로 집합을 정렬할 필요가 없습니다.
이제 우리는 트리의 inorder traversal을 수행하면서 처음부터 트리까지 집합의 요소를 하나씩 쉽게 복사할 수 있습니다. 세트의 각 항목을 처음부터 복사할 때 주의해야 합니다. 먼저 중위 순회를 수행하는 동안 트리에 복사한 다음 세트에서도 삭제합니다.
현재 위에서 언급한 솔루션은 여기에 설명된 이진 트리에서 이진 검색 트리로의 배열 기반 변환보다 간단하고 구현하기 쉽습니다.

다음은 set을 이용하여 이진 트리를 이진 탐색 트리(BST)로 변환하는 프로그램에 대해 설명합니다.

예시

/* CPP program for converting a Binary tree to BST implementing sets as containers. */
#include <bits/stdc++.h>
using namespace std;
struct Node1 {
   int data;
   struct Node1 *left, *right;
};
// function for storing the nodes in set while performing inorder traversal.
void storeinorderInSet(Node1* root1, set<int>& s){
   if (!root1)
   return;
   // Left subtree is visited first
   storeinorderInSet(root1->left, s);
   Order of O(logn) for sets is taken by insertion
   s.insert(root1->data);
   // We visit the right subtree
   storeinorderInSet(root1->right, s);
} // Time complexity = O(nlogn)
// function for copying elements of set one by one to the tree while performing inorder traversal
void setToBST(set<int>& s, Node1* root1){
   // base condition
   if (!root1) return;
   // We first move to the left subtree and update elements
   setToBST(s, root1->left);
   // iterator initially pointing to the starting of set
   auto it = s.begin();
   // We copy the element at sarting of set(sorted) to the tree.
   root1->data = *it;
   // now we erase the starting element from set.
   s.erase(it);
   // now we move to right subtree and update elements
   setToBST(s, root1->right);
}
// T(n) = O(nlogn) time
// We convert Binary tree to BST.
void binaryTreeToBST(Node1* root1){
   set<int> s;
   // We populate the set with the tree's inorder traversal data
   storeinorderInSet(root1, s);
   // At present sets are by default sorted as they are used
   implementing self-balancing BST
   // We copy elements from set to the tree while inorder traversal
   which makes a BST
   setToBST(s, root1);
}
// Time complexity = O(nlogn),
// Auxiliary Space = O(n) for set.
// helper function for creating a node
Node1* newNode(int data){
   // dynamically allocating memory
   Node1* temp = new Node1();
   temp->data = data;
   temp->left = temp->right = NULL;
   return temp;
}
// function for doing inorder traversal
void inorder(Node1* root1){
   if (!root1)
   return;
   inorder(root1->left);
   cout<< root1->data << " ";
   inorder(root1->right);
}
int main(){
   Node1* root1 = newNode(6);
   root1->left = newNode(8);
   root1->right = newNode(10);
   root1->right->left = newNode(11);
   root1->left->left = newNode(2);
   root1->left->right = newNode(7);
   root1->right->right = newNode(12);
   /* Building tree given in the following figure
      6
      / \
      8 10
      /\ / \
      2 7 11 12 */
   // We convert the above Binary tree to BST
   binaryTreeToBST(root1);
   cout<< "Inorder traversal of BST is: " << endl;
   inorder(root1);
   return 0;
}

출력

Inorder traversal of BST is:
1 5 6 7 9 10 11

시간 복잡도는 다음과 같이 표시됩니다. O(n Log n)

보조 공간은 다음과 같이 표시됩니다. (n)