二分木を二分探索木に変換
二分木は非線形データ構造です。各ノードには最大 2つの子があるので、二分木と呼ばれます。これらの子は左の子と右の子と呼ばれています。また、最上位のノードをルートと呼ぶ無向グラフとして解釈することもできます。二分探索木（BST）は、データをソートされた方法で整理しておくのに役立つ特別な特性を持つ二分木です。
このチュートリアルでは、二分木の元の構造を維持しながら二分木を BST に変換する方法について説明します。
二分木を二分探索木に変換するアルゴリズム
-
二分木ノードの順不同の探索を格納するために
arrという配列を作成します。 -
任意のソートアルゴリズム(MergeSort O(nlogn)、QuickSort O(n^2)、Insertion Sort O(n^2)など)を用いて
arrをソートする。 -
もう一度、ツリーの順序を入れ替えて探索し、二分木の要素をソートされた配列
arrから格納して、BST を生成します。
二分木を BST に変換する図
-
ルートのノード
4を順番にトラバーサルすることを呼び出します。再帰的に左にトラバースして最左端のノードであるノード1に到達し、それを出力に含めます; ルートであり左ノードを持たないノードであるため、ノード2にトレースバックし、それをトラバーサルに含めます。このようにして、木全体を探索し、順序を変えて探索した結果を配列arrに[1, 2, 3, 5, 4, 6]として格納します。 -
任意のソートアルゴリズムを用いて配列
arrをソートすると、[1, 2, 3, 4, 5, 6]が得られます。 -
再び順不同探索を呼び出して、並べ替えられた配列
arrを二分木に格納し、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 に格納し、その配列を二分木に格納する順序順探索の時間的複雑さは O(n) です。しかし、配列をソートする複雑さは O(nlogn) であるため、全体の複雑さは O(nlogn) + 2*O(n) となります。時間的な複雑さは O(nlogn) のオーダーです。
- 最良の場合
最良の時間的複雑さは O(n) のオーダーです。与えられた二分木が既に BST である場合、それを実現するために順序を変えて探索を行い、ソート操作は不要です。
- 最悪の場合
最悪の場合の時間的複雑さは O(nlogn) のオーダーです。
空間計算量
アルゴリズムの空間の複雑さは、再帰呼び出しに必要な余分な空間のために O(n) となります。
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn