二分探索木は以下の条件を満たすデータ構造です：

• 左の子ノードは親ノードより小さい。
• 右の子ノードは親ノードより大きい。

重要な点として、左側サブツリーの任意の値は、右側サブツリーのすべての値よりも小さいです。

探索効率

各ステップで半分の枝を削除できるため、非常に効率的です。パフォーマンスは木の深さとバランスに依存します。

ノードの定義

struct TreeNode {
    TreeNode* parent;
    TreeNode* left;
    TreeNode* right;
    int key;
};

挿入操作

bool addNode(TreeNode*& root, TreeNode* newNode) {
    if (root == nullptr) {
        root = newNode;
        return true;
    }

    TreeNode* current = root;
    while (true) {
        if (newNode->key < current->key) {
            if (current->left == nullptr) {
                current->left = newNode;
                newNode->parent = current;
                return true;
            }
            current = current->left;
        } else if (newNode->key > current->key) {
            if (current->right == nullptr) {
                current->right = newNode;
                newNode->parent = current;
                return true;
            }
            current = current->right;
        } else {
            return false; // 既に存在する場合
        }
    }
}

探索操作

TreeNode* findNode(TreeNode* root, int target) {
    TreeNode* current = root;
    while (current != nullptr) {
        if (target < current->key) {
            current = current->left;
        } else if (target > current->key) {
            current = current->right;
        } else {
            return current;
        }
    }
    return nullptr;
}

削除操作

削除処理は以下の手順で行います：

1. 子ノードがない場合：単純に削除。
2. 一つだけ子ノードがある場合：その子ノードを上昇させる。
3. 両方の子ノードがある場合：

• 左サブツリーの最大値または右サブツリーの最小値を探す。
• この値を削除対象ノードに置き換える。

TreeNode* getMinimum(TreeNode* node) {
    while (node && node->left) {
        node = node->left;
    }
    return node;
}

TreeNode* removeNode(TreeNode* root, int key) {
    if (root == nullptr) return root;

    if (key < root->key) {
        root->left = removeNode(root->left, key);
    } else if (key > root->key) {
        root->right = removeNode(root->right, key);
    } else {
        if (root->left == nullptr) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }

        TreeNode* minNode = getMinimum(root->right);
        root->key = minNode->key;
        root->right = removeNode(root->right, minNode->key);
    }
    return root;
}

部分木の確認

bool isSubtreePresent(TreeNode* s, TreeNode* t) {
    if (t == nullptr) return true;
    if (s == nullptr) return false;
    if (areTreesIdentical(s, t)) return true;
    return isSubtreePresent(s->left, t) || isSubtreePresent(s->right, t);
}

bool areTreesIdentical(TreeNode* a, TreeNode* b) {
    if (a == nullptr && b == nullptr) return true;
    if (a == nullptr || b == nullptr) return false;
    return (a->key == b->key && areTreesIdentical(a->left, b->left) && areTreesIdentical(a->right, b->right));
}

注意点

二分探索木には深刻な問題があります。極端なケースでは、リスト構造に退化し、探索効率が低下します。