① なぜ二分探索木が必要なのか？
ソートされた配列で要素を検索する場合、二分探索を使用すると、複雑度は O(log n) になります。
しかし、その中に要素を挿入または削除する場合、複雑度は O(n) になります。
この問題に対する解決策として、二分探索木が存在します。
② 二分探索木とは何か？
まず、二分探索木の目的を明確にします：検索、挿入、削除の操作を O(log n) の複雑度で効率的に管理すること。
二分探索木の特徴：任意のノードについて、左部分木 < 根ノード < 右部分木。
分かりやすく言うと、各ノードに対して、その左部分木の任意のノードはそのノードより小さく、右部分木の任意のノードはそのノードより大きいです。
二分探索木には、以下の3つの性質があることがわかります：
- このような特徴を持つ木に対して中順走査を行うと、得られるシーケンスは必ずソート済みになります。なぜなら、中順走査は左部分木、根、右部分木の順で行われるからです。
- 二分探索木の左右の部分木もまた二分探索木です。
- 二分探索木の最小値はその左チェーンの頂点であり、最大値はその右チェーンの頂点です。
特別なケースとして、空の木も二分探索木です。
以下は典型的な二分探索木の例です：
class Node {
public:
int data;
Node* left;
Node* right;
Node(int val) {
data = val;
left = nullptr;
right = nullptr;
}
};
// 走査操作
void inorderTraversal(Node* node) {
if (node == nullptr) {
return;
}
inorderTraversal(node->left);
std::cout << node->data << " ";
inorderTraversal(node->right);
}
// 最小値検索操作
int findMin(Node* node) {
if (node == nullptr) {
return -1; // または適切なエラー値
}
while (node->left != nullptr) {
node = node->left;
}
return node->data;
}
// 最大値検索操作
int findMax(Node* node) {
if (node == nullptr) {
return -1; // または適切なエラー値
}
while (node->right != nullptr) {
node = node->right;
}
return node->data;
}
③ 二分探索木の検索
二分探索木の性質と特徴に基づいて、以下の操作が得られます：
根ノードから要素 x を検索し、現在のノードと比較します（現在のノードの要素を v とします）。x < v であれば、その左部分木で検索を続けます；x > v であれば、その右部分木で検索を続けます。
この操作を繰り返し、x が見つかるか、葉ノード（つまり x が存在しない）に到達するまで続けます。
探索木がバランスされている場合、検索操作の複雑度は O(log n) です。
bool find(Node* node, int value) {
if (node == nullptr) {
return false;
}
if (node->data == value) {
return true;
} else if (value < node->data) {
return find(node->left, value);
} else {
return find(node->right, value);
}
}
④ 二分探索木の挿入
ノード u を根とする二分探索木に値 x のノードを挿入します。
ケース分け：
- u が空の場合、新しいノードを直接追加します。
- （u の値を v とします）v > x であれば、u の左部分木で挿入操作を続けます。
- （u の値を v とします）v < x であれば、u の右部分木で挿入操作を続けます。
ここでは重複要素がある場合を考慮しません。
探索木がバランスされている場合、挿入操作の複雑度は O(log n) です。
Node* add(Node* node, int value) {
if (node == nullptr) {
return new Node(value);
}
if (value < node->data) {
node->left = add(node->left, value);
} else if (value > node->data) {
node->right = add(node->right, value);
}
return node;
}
⑤ 二分探索木の削除
ノード u を根とする二分探索木から値 x のノードを削除します。
u の値を v とし、ケース分けします：
- u が葉ノードの場合、そのノードを直接削除します。
- u が一つの子しか持たないノード（チェーンノード）の場合、その子を返します。
- u が2つの子を持つノードの場合、その左部分木の最大値（最も右のノード）または右部分木の最小値（最も左のノード）で置き換えます。
第3のケースの補足説明：二分探索木の第1の性質に基づいて、このような特徴を持つ木に対して中順走査を行うと、得られるシーケンスは必ずソート済みになります。このシーケンスを得ることができますが、第3のケースは、このシーケンスにおけるノードの直接の前駆（predecessor）または直接の後継（successor）を見つけることと同じです。
Node* deleteNode(Node* node, int value) {
if (node == nullptr) {
return node;
}
if (value < node->data) {
node->left = deleteNode(node->left, value);
} else if (value > node->data) {
node->right = deleteNode(node->right, value);
} else {
// ノードが一つまたはゼロの子を持つ場合
if (node->left == nullptr) {
Node* temp = node->right;
delete node;
return temp;
} else if (node->right == nullptr) {
Node* temp = node->left;
delete node;
return temp;
}
// ノードが二つの子を持つ場合、中順後継（右部分木の最小値）で置き換える
Node* successor = findMin(node->right);
node->data = successor->data;
node->right = deleteNode(node->right, successor->data);
}
return node;
}