二分探索木チェック
Harshit Jindal
2023年10月12日
Data Structure
Binary Tree
Binary Search Tree
バイナリーツリーは非線形データ構造体です。各ノードには最大 2つの子があるので、バイナリツリーと呼ばれています。これらの子は左の子と右の子と呼ばれています。バイナリツリーが BST になるためには、以下の特性を満たさなければなりません。
- 左サブツリーのすべてのノードは、ルートノードよりも小さい。
- 右サブツリーのすべてのノードは、ルートノードよりも大きい。
- 左と右のサブツリーも二分探索木でなければなりません。
二分探索木であるかどうかをチェックするアルゴリズム
アルゴリズム 1
このアプローチでは、すべてのノードをサブツリーのルートとみなして、左サブツリーにルートより大きい要素が含まれているかどうか、右サブツリーにルートより小さい要素が含まれているかどうかを調べます。max と min の要素を見つけるには、getMin() と getMax() という 2つの別の関数を使わなければならません。
getMin()
-
tempをrootとして初期化する。 -
tempがleftのとき、以下のようにする。- つまり、左に向かって移動して最小の要素を見つける。
-
temp->valをそのサブツリー内の最小値として返します。
getMax()
-
tempをrootとして初期化する。 -
tempがrightを持っている間に、以下のようにします。- つまり、右に向かって移動して最大の要素を探す。
-
temp->valをそのサブツリー内の最大値として返します。
isBST(root) とする
-
rootがNULLの場合はtrueを返します。 -
左サブツリーの最大要素
maxmを見つけるにはgetMax(root->left)を呼び出します。 -
getMin(root->right)を呼び出して、右サブツリーの最小要素minmを探します。 -
ルート要素が
maxmより小さいかminmより大きい場合は false を返します。 -
isBST(root->left)とisBST(root->right)を呼び出して、すべてのノードを再帰的にチェックします。両方の再帰的呼び出しが真を返した場合、その木は BST であり、そうでなければ真を返し、そうでなければ偽を返します。
上記のアルゴリズムは木が BST であるかどうかを教えてくれますが、非常に遅いです。関数 getMin() と getMax() は最悪の場合の時間的複雑度が O(n) であり、これらは n ノードに対して呼び出されるので、合計時間的複雑度は O(n2) となります。
アルゴリズム 2
このアルゴリズムは前のアルゴリズムを改良したもので、繰り返し計算を行わないようにしています。以前のアプローチでは、ノードごとに getMin() と getMax() を呼び出していました。このアプローチでは、ノードを通過する際に許容される最小値と最大値を追跡することで、上記のアプローチを改良しています。
isBST(root)
-
2つの変数
minをINT_MIN、maxをINT_MAXとして初期化します。 -
isBST(root,min,max)を呼び出す。
isBST(root, min, max)
-
rootがNULLの場合はtrueを返します。 -
min>root->dataの場合、BST プロパティが違反しているので false を返します。 -
max<root->dataの場合、BST プロパティが違反しているので false を返します。 -
左サブツリーを再帰的にチェックするには、
isBST(root->left, min, root->data-1)(minとroot->data - 1を引数に渡すと、左サブツリーの BST の有効範囲が変わります) を、右サブツリーを再帰的にチェックするには、isBST(root->right, root->data+1, max)(root->data + 1とmaxを引数に渡すと、右サブツリーの BST の有効範囲が変わります) を呼び出します。 -
再帰的な呼び出しが両方とも
trueを返す場合は、木が BST であることを示し、trueを返します。
このアルゴリズムの時間的複雑さは O(n) であり、以前の方法よりも大幅に改善されています。
アルゴリズム 3
このアルゴリズムでは、INT_MIN と INT_MAX を l と r の 2つのポインタに置き換えることで、上のアルゴリズムで使用していた INT_MIN と INT_MAX の使用を回避します。
isBST(root)
-
2つのノード
lとrをNULLとして初期化します。 -
isBST(root, l, r)を呼び出す。(オーバーロードされた関数呼び出し)
isBST(root, l, r)
-
rootがNULLの場合はtrueを返します。 -
lがNULLでなくl->data>=root->dataの場合、BST プロパティが違反しているので false を返します。 -
rがNULLでなくr->data<=root->dataの場合、BST プロパティが違反しているので false を返します。 -
左サブツリーを再帰的にチェックするには、
isBST(root->left, left, root)(第 3 引数に root を渡すとサブツリーの最小値の上限が変更されます)を、右サブツリーを再帰的にチェックするには、isBST(root->right, root, right)(第 2 引数に root を渡すとサブツリーの最大値の上限が変更されます)を呼び出します。 -
再帰的な呼び出しが両方とも
trueを返す場合、ツリーは BST であり、trueを返します。
アルゴリズム 4
二分探索木の順不同探索は、ソートされた順に要素を返します。このプロパティを使用して、バイナリツリーが BST であるかどうかをチェックすることができます。順不同探索のすべての要素が昇順でない場合、与えられた木は二分探索木ではありません。
isBST(root)
-
変数
prevをINT_MINとして初期化します。prevは、現在のノードがprevよりも大きいかどうか、つまりソートされた順序に従っているかどうかを調べるために使われます。 -
isBST(root, prev)を呼び出す。(オーバーロードされた関数 Call)。
(オーバーロードされた関数 Call)
-
rootがNULLの場合はtrueを返す。 -
isBST(root->left, prev)で左サブツリーを再帰的にチェックする。falseを返した場合は false を返します。 -
root->data<=prev. の昇順に違反している場合は false を返します。 -
prev->dataをroot->dataとして更新します。 -
isBST(root->right, prev)で右サブツリーを再帰的に調べる。falseを返した場合は false を返す。 -
そうでなければ true を返します。
二分探索木であることを確認するアルゴリズムの実装
アルゴリズム 1
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
Node(int x) {
this->data = x;
this->left = this->right = NULL;
}
};
int getMin(Node* root) {
while (root->left) {
root = root->left;
}
return root->data;
}
int getMax(Node* root) {
while (root->right) {
root = root->right;
}
return root->data;
}
bool isBST(Node* root) {
if (root == NULL) return true;
if (root->left != NULL && getMax(root->left) > root->data) return false;
if (root->right != NULL && getMin(root->right) < root->data) return false;
if (!isBST(root->left) || !isBST(root->right)) return false;
return true;
}
int main() {
Node* root = new Node(6);
root->left = new Node(3);
root->right = new Node(9);
root->left->left = new Node(1);
root->left->right = new Node(5);
root->right->left = new Node(7);
root->right->right = new Node(11);
if (isBST(root)) {
cout << "This binary tree is a BST." << endl;
} else {
cout << "This binary tree is not a BST." << endl;
}
return 0;
}
アルゴリズム 2
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
Node(int x) {
this->data = x;
this->left = this->right = NULL;
}
};
bool isBST(Node* root, int min, int max) {
if (root == NULL) return 1;
if (root->data < min || root->data > max) return 0;
return isBST(root->left, min, root->data - 1) &&
isBST(root->right, root->data + 1, max);
}
bool isBST(Node* root) { return isBST(root, INT_MIN, INT_MAX); }
int main() {
Node* root = new Node(6);
root->left = new Node(3);
root->right = new Node(9);
root->left->left = new Node(1);
root->left->right = new Node(5);
root->right->left = new Node(7);
root->right->right = new Node(11);
if (isBST(root)) {
cout << "This binary tree is a BST." << endl;
} else {
cout << "This binary tree is not a BST." << endl;
}
return 0;
}
アルゴリズム 3
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
Node(int x) {
this->data = x;
this->left = this->right = NULL;
}
};
bool isBST(Node* root, Node* l, Node* r) {
if (root == NULL) return true;
if (l != NULL and root->data <= l->data) return false;
if (r != NULL and root->data >= r->data) return false;
return isBST(root->left, l, root) && isBST(root->right, root, r);
}
bool isBST(Node* root) {
Node* l = NULL;
Node* r = NULL;
return isBST(root, l, r);
}
int main() {
Node* root = new Node(6);
root->left = new Node(3);
root->right = new Node(9);
root->left->left = new Node(1);
root->left->right = new Node(5);
root->right->left = new Node(7);
root->right->right = new Node(11);
if (isBST(root)) {
cout << "This binary tree is a BST." << endl;
} else {
cout << "This binary tree is not a BST." << endl;
}
return 0;
}
アルゴリズム 4
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
Node(int x) {
this->data = x;
this->left = this->right = NULL;
}
};
bool isBST(Node* root, int& prev) {
if (!root) return true;
if (!isBST(root->left, prev)) return false;
if (root->data <= prev) return false;
prev = root->data;
return isBST(root->right, prev);
}
bool isBST(Node* root) {
int prev = INT_MIN;
return isBST(root, prev);
}
int main() {
Node* root = new Node(6);
root->left = new Node(3);
root->right = new Node(9);
root->left->left = new Node(1);
root->left->right = new Node(5);
root->right->left = new Node(7);
root->right->right = new Node(11);
if (isBST(root)) {
cout << "This binary tree is a BST." << endl;
} else {
cout << "This binary tree is not a BST." << endl;
}
return 0;
}
複雑性分析
時間計算量
- 平均ケース
与えられたバイナリツリーが BST であるかどうかを調べるには、すべての n ノードを探索しなければなりません。したがって、時間の複雑さは [Big Theta]: O(n) のオーダーになります。
- 最良の場合
最良の時間複雑度は O(n) のオーダーです。これは平均ケースの時間的複雑さと同じです。
- 最悪の場合
最悪の時間複雑度は O(n) のオーダーです。これはベストケース時間複雑度と同じである.
空間計算量
アルゴリズムの空間の複雑さは、再帰呼び出しに必要な余分な空間のために O(n) となります。
チュートリアルを楽しんでいますか？ <a href="https://www.youtube.com/@delftstack/?sub_confirmation=1" style="color: #a94442; font-weight: bold; text-decoration: underline;">DelftStackをチャンネル登録</a> して、高品質な動画ガイドをさらに制作するためのサポートをお願いします。 Subscribe
著者： Harshit Jindal
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