二分探索木とは

二分探索木（Binary Search Tree: BST）は、以下の条件を満たす二分木構造です：

• 左部分木に含まれるノードの値は、常に親ノードの値より小さい
• 右部分木に含まれるノードの値は、常に親ノードの値より大きい
• 左右の部分木もまた二分探索木を満たす

基本操作

探索（Search）

探索操作は以下のように行われます：

1. ルートノードから比較を開始します
2. 探索値が現在のノードより大きい場合は右部分木に進みます
3. 探索値が現在のノードより小さい場合は左部分木に進みます
4. 一致する値が見つかるか、または空のノードに到達するまで繰り返します

挿入（Insert）

挿入操作は以下のように行われます：

1. ルートがnullptr（空木）の場合、新しいノードをルートに設定します
2. そうでない場合、探索操作と同様に木をたどり、適切な位置を探します
3. 重複する値がすでに存在する場合は挿入をキャンセルします

中順走査（In-order Traversal）

中順走査によって、ノードの値を昇順に取得することが可能です。

削除（Delete）

削除操作は以下の4つのケースを考慮する必要があります：

1. 削除対象のノードが子を持たない場合
2. 削除対象のノードが左の子のみを持つ場合
3. 削除対象のノードが右の子のみを持つ場合
4. 削除対象のノードが左右の子を持つ場合

4番目のケースでは、削除対象ノードの右部分木における最小値を持つノード（または左部分木における最大値を持つノード）を探し、値を交換した後、そのノードを削除する方法を用います。

実装例

ノード構造

template<typename T>
struct Node {
    T value;
    Node* left;
    Node* right;

    Node(const T& val) : value(val), left(nullptr), right(nullptr) {}
};

BSTクラスの実装

template<typename T>
class BinarySearchTree {
private:
    Node<T>* root;

    void inOrderTraversal(Node<T>* node) {
        if (node == nullptr) return;
        inOrderTraversal(node->left);
        std::cout << node->value << " ";
        inOrderTraversal(node->right);
    }

    Node<T>* findMin(Node<T>* node) {
        while (node->left != nullptr)
            node = node->left;
        return node;
    }

public:
    BinarySearchTree() : root(nullptr) {}

    bool insert(const T& value) {
        Node<T>* newNode = new Node<T>(value);
        if (root == nullptr) {
            root = newNode;
            return true;
        }

        Node<T>* current = root;
        Node<T>* parent = nullptr;

        while (true) {
            parent = current;
            if (value < current->value) {
                current = current->left;
                if (current == nullptr) {
                    parent->left = newNode;
                    return true;
                }
            } else if (value > current->value) {
                current = current->right;
                if (current == nullptr) {
                    parent->right = newNode;
                    return true;
                }
            } else {
                delete newNode;
                return false;
            }
        }
    }

    bool remove(const T& value) {
        Node<T>* current = root;
        Node<T>* parent = nullptr;

        while (current != nullptr && current->value != value) {
            parent = current;
            if (value < current->value)
                current = current->left;
            else
                current = current->right;
        }

        if (current == nullptr) return false;

        // Case 1: 子を持たないノード
        if (current->left == nullptr && current->right == nullptr) {
            if (current == root) {
                root = nullptr;
            } else if (parent->left == current) {
                parent->left = nullptr;
            } else {
                parent->right = nullptr;
            }
            delete current;

        // Case 2: 右の子のみを持つノード
        } else if (current->left == nullptr) {
            Node<T>* temp = current;
            if (current == root) {
                root = root->right;
            } else if (parent->left == current) {
                parent->left = current->right;
            } else {
                parent->right = current->right;
            }
            delete temp;

        // Case 3: 左の子のみを持つノード
        } else if (current->right == nullptr) {
            Node<T>* temp = current;
            if (current == root) {
                root = root->left;
            } else if (parent->left == current) {
                parent->left = current->left;
            } else {
                parent->right = current->left;
            }
            delete temp;

        // Case 4: 左右の子を持つノード
        } else {
            Node<T>* successorParent = current;
            Node<T>* successor = current->right;
            while (successor->left != nullptr) {
                successorParent = successor;
                successor = successor->left;
            }

            T tempValue = current->value;
            current->value = successor->value;
            successor->value = tempValue;

            if (successorParent->left == successor)
                successorParent->left = successor->right;
            else
                successorParent->right = successor->right;

            delete successor;
        }

        return true;
    }

    void inOrder() {
        inOrderTraversal(root);
        std::cout << std::endl;
    }
};

応用例

二分探索木は、以下のような用途に使われます：

• 検索木としての利用（データの探索、挿入、削除）
• 辞書型データ構造の実装（キーと値のペアを管理）
• 動的集合の管理

性能分析

二分探索木の操作の時間計算量は、木の形状によって異なります：

• 最良の場合（木が平衡している場合）：O(log n)
• 最悪の場合（木が線形構造に近い場合）：O(n)