C++ 二叉搜索树实现与性能分析

这里需要特别注意，由于涉及递归操作（如销毁、拷贝），私有成员 _root 无法在外部直接访问，因此必须封装私有辅助函数供公有接口调用。

3. 插入操作

插入逻辑遵循 BST 性质：比当前节点大往右走，小往左走，直到找到空位。

bool Insert(const K& key) {
    if (_root == nullptr) {
        _root = new Node(key);
        return true;
    }
    
    Node* cur = _root;
    Node* parent = nullptr;
    
    while (cur) {
        if (cur->_key < key) {
            parent = cur;
            cur = cur->_right;
        } else if (cur->_key > key) {
            parent = cur;
            cur = cur->_left;
        } else {
            // 已存在，根据需求决定是否允许重复
            return false;
        }
    }
    
    cur = new Node(key);
    if (parent->_key < key)
        parent->_right = cur;
    else
        parent->_left = cur;
        
    return true;
}

4. 查找操作

查找相对简单，利用 BST 的有序性剪枝。

bool Find(const K& key) {
    Node* cur = _root;
    while (cur) {
        if (cur->_key < key)
            cur = cur->_right;
        else if (cur->_key > key)
            cur = cur->_left;
        else
            return true;
    }
    return false;
}

5. 删除操作（难点）

删除是最复杂的操作，需分情况讨论：

1. 无子节点：直接删除，父节点对应指针置空。
2. 单子节点：父节点指针指向该节点的子节点。
3. 双子节点：无法直接删除。通常用右子树的最小值（或左子树的最大值）替换当前节点的值，然后递归删除那个最小值节点（此时它必然是单子节点或叶子节点）。

bool Erase(const K& key) {
    Node* parent = nullptr;
    Node* cur = _root;
    
    while (cur) {
        if (cur->_key < key) {
            parent = cur;
            cur = cur->_right;
        } else if (cur->_key > key) {
            parent = cur;
            cur = cur->_left;
        } else {
            // 找到目标节点，开始删除逻辑
            if (cur->_left == nullptr) {
                // 左为空，处理右孩子或空
                if (cur == _root)
                    _root = cur->_right;
                else {
                    if (cur == parent->_left)
                        parent->_left = cur->_right;
                    else
                        parent->_right = cur->_right;
                }
                delete cur;
            } else if (cur->_right == nullptr) {
                // 右为空，处理左孩子
                if (cur == _root)
                    _root = cur->_left;
                else {
                    if (cur == parent->_left)
                        parent->_left = cur->_left;
                    else
                        parent->_right = cur->_left;
                }
                delete cur;
            } else {
                // 双孩子：找右子树最小值替代
                Node* pMinRight = cur;
                Node* minRight = cur->_right;
                while (minRight->_left) {
                    pMinRight = minRight;
                    minRight = minRight->_left;
                }
                
                // 交换值
                std::swap(minRight->_key, cur->_key);
                
                // 删除原最小值节点（此时必为单子节点或叶子）
                if (pMinRight->_left == minRight)
                    pMinRight->_left = minRight->_right;
                else
                    pMinRight->_right = minRight->_right;
                
                delete minRight;
            }
            return true;
        }
    }
    return false;
}

6. 中序遍历

验证 BST 是否有序的标准方法。

void InOrder() {
    _InOrder(_root);
    cout << endl;
}

private:
void _InOrder(Node* root) {
    if (root == nullptr) return;
    _InOrder(root->_left);
    cout << root->_key << " ";
    _InOrder(root->_right);
}

三、Key 与 Key-Value 结构扩展

上述实现仅存储 Key。在实际应用中，往往需要关联一个 Value，例如字典查询或统计词频。

1. 结构定义

namespace key_value {
template<class K, class V> struct BSTreeNode {
    BSTreeNode<K, V>* _left;
    BSTreeNode<K, V>* _right;
    K _key;
    V _value;
    
    BSTreeNode(const K& key, const V& value) 
        :_left(nullptr), _right(nullptr), _key(key), _value(value) {}
};
// 类实现逻辑与 Key 版本类似，只是节点多了一个 _value 成员
// 注意：Erase 时只根据 Key 删除，Value 随 Key 一起移除
} // namespace

2. 应用场景

• Key 场景：车牌识别系统（判断是否在白名单）、拼写检查（单词是否存在于词典）。
• Key-Value 场景：中英翻译字典（Key=英文，Value=中文）、停车场计费（Key=车牌，Value=入场时间）、词频统计（Key=单词，Value=次数）。

通过这种方式，二叉搜索树不仅实现了高效查找，还能灵活承载业务数据。