二分探索樹の基本原理
二分探索樹（Binary Search Tree）は、効率的なデータ検索を可能にする階層型のデータ構造です。この構造は以下の規則に従ってノードが配置されます。
- 左部分木: 親ノードよりも小さい値を持つ全てのノードが含まれます。
- 右部分木: 親ノードよりも大きい値を持つ全てのノードが含まれます。
- 再帰的性質: 各部分木自体もまた有効な二分探索樹でなければなりません。
以下に示す配列データを用いて構造を理解します。
int data[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};基本操作の実装
1. データの探索
検索処理は根元から開始し、比較結果に基づいて枝分かれを進みます。目標のキーに一致するノードが見つかれば真を返し、null（空）に至る場合は存在しないことを意味して偽を返します。
template<typename T>
class BSTreeNode {
public:
T value;
BSTreeNode* left;
BSTreeNode* right;
BSTreeNode(T val) : value(val), left(nullptr), right(nullptr) {}
};
template<typename T>
bool findElement(BSTreeNode<T>* root, const T& targetKey) {
BSTreeNode<T>* currentNode = root;
while (currentNode != nullptr) {
if (currentNode->value > targetKey) {
currentNode = currentNode->left;
}
else if (currentNode->value < targetKey) {
currentNode = currentNode->right;
}
else {
return true; // 発見
}
}
return false; // 未発見
}2. データの挿入
新規要素の追加においては、まずルートポインタの状態を確認します。空の場合は即座に新しいノードを設定します。すでにツリーが存在する場合、既存のルールに基づいて適切な位置を特定し、ノードを接続します。ただし、二分探索樹には重複した値を含めることはできません。
template<typename T>
bool insertNode(BSTreeNode*<T>& root, T newValue) {
if (root == nullptr) {
root = new BSTreeNode<T>(newValue);
return true;
}
BSTreeNode<T>* parentNode = nullptr;
BSTreeNode<T>* currentNode = root;
while (currentNode != nullptr) {
parentNode = currentNode;
if (newValue < currentNode->value) {
currentNode = currentNode->left;
}
else if (newValue > currentNode->value) {
currentNode = currentNode->right;
}
else {
return false; // 重複値のため失敗
}
}
// 新しいノードを作成し結合
BSTreeNode<T>* newNode = new BSTreeNode<T>(newValue);
if (newValue < parentNode->value) {
parentNode->left = newNode;
} else {
parentNode->right = newNode;
}
return true;
}3. データの削除
削除処理は最も複雑です。対象となるノードが見つかった後、その子の状況によって処理方針が変わります。
- 子がいない場合: そのまま親ノードへの参照を切ります。
- 片方のみの子の場合: 残っている子を直接親につなぎ替えます。
- 両方の子がいる場合: 通常、右部分木の中から最小の値（ successor ）または左部分木からの最大の値を該当する場所へコピーし、その後オリジナルの継承者ノードを削除する方法を採用します。
template<typename T>
bool removeNode(BSTreeNode*& root, T targetKey) {
BSTreeNode<T>* parentNode = nullptr;
BSTreeNode<T>* currentNode = root;
// 対象ノードの探索
while (currentNode != nullptr) {
if (currentNode->value > targetKey) {
parentNode = currentNode;
currentNode = currentNode->left;
}
else if (currentNode->value < targetKey) {
parentNode = currentNode;
currentNode = currentNode->right;
}
else {
// 削除対象が見つかった
// 左サブツリーがないケース
if (currentNode->left == nullptr) {
if (currentNode == root) {
root = currentNode->right;
} else {
if (parentNode->value > targetKey) {
parentNode->left = currentNode->right;
} else {
parentNode->right = currentNode->right;
}
}
delete currentNode;
return true;
}
// 右サブツリーがないケース
else if (currentNode->right == nullptr) {
if (currentNode == root) {
root = currentNode->left;
} else {
if (parentNode->value > targetKey) {
parentNode->left = currentNode->left;
} else {
parentNode->right = currentNode->left;
}
}
delete currentNode;
return true;
}
// 両方のサブツリーがあるケース（入れ替え法）
else {
BSTreeNode<T>* minParent = currentNode;
BSTreeNode<T>* minValueNode = currentNode->right;
// 右側の最小ノードを検出
while (minValueNode->left != nullptr) {
minParent = minValueNode;
minValueNode = minValueNode->left;
}
// 値のコピー
currentNode->value = minValueNode->value;
// 最小ノードの削除（論理的には右側のみの削除として扱う）
if (minParent->left == minValueNode) {
minParent->left = minValueNode->right;
} else {
minParent->right = minValueNode->right;
}
delete minValueNode;
return true;
}
}
}
return false; // 存在しなかった場合
}計算量とパフォーマンス評価
二分探索樹の効率性は、主に検索操作に依存します。ノード数 n の場合、平均的な検索コストは木の高さに比例します。
理想的なバランスが取れた平衡探索樹では、高さが log₂(n) に近いため、検索・挿入・削除のいずれもO(log N) の時間計算量を達成可能です。
しかし、データが特定の順序（例：昇順ソートされた状態）で挿入されると、木が偏った構造（リスト状）になり、最悪ケースにおいて比較回数が O(N²) あるいは平均的に O(N) に劣化し、パフォーマンスが著しく低下します。そのため、実運用では AVL 木や赤黒木などのバランス補正機構が必要になる場合があります。