TUTORIAL · Data Structure
이진 트리를 이진 검색 트리로 변환
이 자습서에서는 이진 트리를 이진 검색 트리로 변환하는 방법을 설명합니다.
이 페이지의 내용
이진 트리는 비선형 데이터 구조입니다. 각 노드에는 최대 두 개의 자식이 있기 때문에 이진 트리라고합니다. 이 아이들을 왼쪽 아이들과 오른쪽 아이들이라고 부릅니다. 또한 최상위 노드를 루트라고하는 무 방향 그래프로 해석 될 수도 있습니다. 이진 검색 트리 (BST)는 데이터를 정렬 된 방식으로 구성하는 데 도움이되는 특수 속성이있는 이진 트리입니다.
이 튜토리얼에서는 바이너리 트리의 원래 구조를 유지하면서 바이너리 트리를 BST로 변환하는 방법에 대해 설명합니다.
이진 트리를 BST로 변환하는 알고리즘
-
이진 트리 노드의 순회 순회를 저장하기 위해
arr라는 배열을 만듭니다. -
정렬 알고리즘 (MergeSort O(nlogn), QuickSort O(n^2), Insertion Sort O(n^2) 등)을 사용하여
arr를 정렬합니다. -
다시, 트리의 inorder traversal을 수행하고 정렬 된 배열
arr의 이진 트리에 요소를 저장하여 BST를 산출합니다.
이진 트리를 BST 일러스트레이션으로 변환
-
루트 노드
4에서 inorder traversal을 호출합니다. 재귀 적으로 왼쪽으로 이동하여 가장 왼쪽 노드 인1노드에 도달하고이를 출력에 포함합니다. 루트이고 남은 노드가 없기 때문에 노드2로 추적하여 순회에 포함합니다. 이런 식으로 전체 트리를 순회하고 배열arr에[1, 2, 3, 5, 4, 6]으로 inorder traversal을 저장합니다. -
정렬 알고리즘을 사용하여 배열
arr를 정렬하여[1, 2, 3, 4, 5, 6]를 얻습니다. -
BST를 얻기 위해 정렬 된 배열
arr를 이진 트리에 다시 저장하기 위해 inorder traversal을 다시 호출합니다.
이진 트리를 BST 구현으로 변환
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
Node(int x) {
this->data = x;
this->left = this->right = NULL;
}
};
vector<int> v;
void inorder(Node* root) {
if (root != NULL) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
}
void storetree(Node* root, int i = 0) {
if (!root) {
return;
}
storetree(root->left);
v.push_back(root->data);
storetree(root->right);
}
void restoretree(Node* root, int& i) {
if (!root) {
return;
}
restoretree(root->left, i);
root->data = v[i];
i++;
restoretree(root->right, i);
}
void converttoBST(Node* root) {
if (!root) {
return;
}
storetree(root);
sort(v.begin(), v.end());
int i = 0;
restoretree(root, i);
}
int main() {
Node* root = new Node(3);
root->left = new Node(1);
root->right = new Node(7);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->left->left->right = new Node(2);
root->right->left = new Node(6);
root->right->right = new Node(9);
root->right->right->left = new Node(8);
cout << "The inorder traversal of the tree is : ";
inorder(root);
cout << endl;
converttoBST(root);
cout << "The inorder traversal of the tree is : ";
inorder(root);
cout << endl;
}
이진 트리를 BST 알고리즘 복잡성으로 변환
시간 복잡성
- 평균 사례
배열을sorted에 저장하고sorted배열을 이진 트리에 다시 저장하는 inorder traversal을 수행하는 시간 복잡도는O(n)입니다. 그러나 배열 정렬의 복잡성은O(nlogn)이므로 전체 복잡성은O(nlogn) + 2 * O(n)로 제공됩니다. 시간 복잡도는O(nlogn)순서입니다.
- 베스트 케이스
최상의 경우 시간 복잡도는O(n)순서입니다. 주어진 이진 트리가 이미 BST 인 경우,이를 실현하기 위해 inorder traversal을 수행하고 정렬 작업이 필요하지 않습니다.
- 최악의 경우
최악의 시간 복잡도는O(nlogn)의 순서입니다.
공간 복잡성
알고리즘의 공간 복잡성은 재귀 호출에 필요한 추가 공간으로 인해O(n)입니다.
