C++ 二叉搜索树：原理与增删查实现详解

C++ 二叉搜索树：原理与增删查实现详解

二叉搜索树（Binary Search Tree, BST）是数据结构中非常基础且重要的一种树形结构。它不仅仅是面试中的常客，更是理解红黑树、AVL 树等平衡树的基础。今天我们就从原理出发，结合 C++ 代码，把它的增删查操作彻底搞懂。

理解二叉搜索树

一棵二叉搜索树必须满足以下两个核心性质：

1. 左小右大：若根节点存在，其左子树中所有节点的值都小于根节点的值，右子树中所有节点的值都大于根节点的值。
2. 递归定义：任意节点的左右子树也必须是二叉搜索树。

这意味着，对于树中的任意节点，其左侧的所有后代都比它小，右侧的所有后代都比它大。这种有序性使得查找效率远高于普通链表或无序树。

需要注意的是，如果插入的数据本身是有序的（例如 1, 2, 3, 4...），BST 会退化成一条链表，此时性能会急剧下降至 O(n)。这也是后续学习平衡树的原因，但在掌握 BST 本身之前，我们先专注于其基本逻辑。

核心操作解析

我们将树封装为一个模板类 BSTree，内部维护一个指向根节点的指针 _root。

1. 查找操作

查找的逻辑其实和二分查找非常像。给定目标值 val，我们从根节点开始比较：

• 如果 val < cur->_key，说明目标在左边，往左走；
• 如果 val > cur->_key，说明目标在右边，往右走；
• 如果相等，直接返回当前节点。

当遍历到空指针时，说明树中不存在该值。平均情况下，时间复杂度为 O(log n)，最坏情况（退化链表）为 O(n)。

Node* find(const K& val) {
    Node* cur = _root;
    while (cur) {
        if (val < cur->_key)
            cur = cur->_left;
        else if (val > cur->_key)
            cur = cur->_right;
        else
            break; // 找到目标
    }
    return cur;
}

2. 插入操作

插入的核心在于保持'左小右大'的性质。流程如下：

1. 处理空树：如果树是空的，新节点直接成为根节点。
2. 寻找位置：从根节点出发，根据大小关系向下遍历，直到遇到空指针。
3. 插入节点：在空指针处挂上新节点。

这里有个细节要注意：BST 通常不允许重复键值。如果在查找过程中发现已存在该值，应直接返回失败，不执行插入。

bool insert(const K& val) {
    // 空树情况
    if (_root == nullptr) {
        _root = new Node(val);
        return true;
    }

    Node* cur = _root;
    Node* curPre = nullptr; // 记录父节点，方便挂载

    while (cur) {
        if (val == cur->_key)
            return false; // 重复值，不插入
        else if (val < cur->_key) {
            curPre = cur;
            cur = cur->_left;
        } else {
            curPre = cur;
            cur = cur->_right;
        }
    }

    // 确定挂载方向
    if (curPre->_key > val)
        curPre->_left = new Node(val);
    else
        curPre->_right = new Node(val);

    return true;
}

3. 删除操作

删除是 BST 中最复杂的部分，因为删除后必须保证树的性质不被破坏。我们需要分三种情况讨论：

情况一：待删除节点是叶子节点（无孩子）

直接删除即可，不影响其他节点。

情况二：待删除节点只有一个孩子

用唯一的子节点替换待删除节点的位置，相当于把子节点'提上来'。

情况三：待删除节点有两个孩子

这是难点。不能直接删除，否则左右子树无法连接。策略是：找替代者。

通常选择右子树的最小节点（即右子树的最左下节点）或者左子树的最大节点来覆盖待删除节点的值，然后删除那个替代节点。这样既保持了有序性，又避免了复杂的指针重连。

以选择右子树最小节点为例：

1. 找到右子树的最小节点 rightMin。
2. 将 rightMin 的值复制到待删除节点。
3. 删除 rightMin 节点（此时 rightMin 最多只有一个右孩子，简化了删除逻辑）。

bool erase(const K& val) {
    if (_root == nullptr) return false;

    Node* cur = _root;
    Node* curPre = nullptr;

    // 1. 查找待删除节点
    while (cur) {
        if (val < cur->_key) {
            curPre = cur;
            cur = cur->_left;
        } else if (val > cur->_key) {
            curPre = cur;
            cur = cur->_right;
        } else {
            break;
        }
    }

    if (cur == nullptr) return false; // 未找到

    // 2. 处理删除逻辑
    // 情况 A: 0 个或 1 个孩子
    if (cur->_left == nullptr || cur->_right == nullptr) {
        Node* curNext = cur->_left ? cur->_left : cur->_right;

        if (cur != _root) {
            if (curPre->_left == cur)
                curPre->_left = curNext;
            else
                curPre->_right = curNext;
        } else {
            _root = curNext; // 删除的是根节点
        }
        delete cur;
    }
    // 情况 B: 2 个孩子
    else {
        // 找右子树最小节点
        Node* rightMin = cur->_right;
        Node* rightMinPre = cur;
        while (rightMin->_left) {
            rightMinPre = rightMin;
            rightMin = rightMin->_left;
        }

        // 值覆盖
        cur->_key = rightMin->_key;

        // 删除 rightMin 节点（此时 rightMin 最多只有右孩子）
        Node* rightMinNext = rightMin->_right;
        if (rightMinPre->_left == rightMin)
            rightMinPre->_left = rightMinNext;
        else
            rightMinPre->_right = rightMinNext;

        delete rightMin;
    }

    return true;
}

完整代码实现

下面是整合后的完整类定义及测试用例，包含了析构函数和中序遍历打印功能，方便验证结果。

#pragma once
#include <iostream>
#include <vector>
using namespace std;

template<class K>
struct BSTNode {
    BSTNode<K>* _left;
    BSTNode<K>* _right;
    K _key;

    BSTNode(const K& val) : _left(nullptr), _right(nullptr), _key(val) {}
};

template<class K>
class BSTree {
public:
    typedef BSTNode<K> Node;

    BSTree() : _root(nullptr) {}

    ~BSTree() {
        destroy(_root);
    }

    Node* find(const K& val) {
        Node* cur = _root;
        while (cur) {
            if (val < cur->_key) cur = cur->_left;
            else if (val > cur->_key) cur = cur->_right;
            else break;
        }
        return cur;
    }

    bool insert(const K& val) {
        if (_root == nullptr) {
            _root = new Node(val);
            return true;
        }
        Node* cur = _root;
        Node* curPre = nullptr;
        while (cur) {
            if (val == cur->_key) return false;
            else if (val < cur->_key) {
                curPre = cur;
                cur = cur->_left;
            } else {
                curPre = cur;
                cur = cur->_right;
            }
        }
        if (curPre->_key > val)
            curPre->_left = new Node(val);
        else
            curPre->_right = new Node(val);
        return true;
    }

    bool erase(const K& val) {
        if (_root == nullptr) return false;
        Node* cur = _root;
        Node* curPre = nullptr;
        while (cur) {
            if (val < cur->_key) { curPre = cur; cur = cur->_left; }
            else if (val > cur->_key) { curPre = cur; cur = cur->_right; }
            else break;
        }
        if (cur == nullptr) return false;

        if (cur->_left == nullptr || cur->_right == nullptr) {
            Node* curNext = cur->_left ? cur->_left : cur->_right;
            if (cur != _root) {
                if (curPre->_left == cur) curPre->_left = curNext;
                else curPre->_right = curNext;
            } else {
                _root = curNext;
            }
            delete cur;
        } else {
            Node* rightMin = cur->_right;
            Node* rightMinPre = cur;
            while (rightMin->_left) {
                rightMinPre = rightMin;
                rightMin = rightMin->_left;
            }
            cur->_key = rightMin->_key;
            Node* rightMinNext = rightMin->_right;
            if (rightMinPre->_left == rightMin) rightMinPre->_left = rightMinNext;
            else rightMinPre->_right = rightMinNext;
            delete rightMin;
        }
        return true;
    }

    void inOrder() {
        _inOrder(_root);
        cout << endl;
    }

private:
    Node* _root;

    void destroy(Node* root) {
        if (root == nullptr) return;
        destroy(root->_left);
        destroy(root->_right);
        delete root;
    }

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

void testBST() {
    BSTree<int> bst;
    vector<int> arr = {8, 3, 10, 1, 6, 14, 5, 7, 13};
    cout << "=== 创建二叉搜索树 ===\n";
    for (const auto& e : arr) bst.insert(e);
    cout << "中序遍历结果：";
    bst.inOrder();

    cout << "=== 查找数据 ===\n";
    cout << "查找 14: " << (bst.find(14) ? "存在" : "不存在") << endl;
    cout << "查找 28: " << (bst.find(28) ? "存在" : "不存在") << endl;

    cout << "=== 删除数据 ===\n";
    cout << "删除前：";
    bst.inOrder();
    bst.erase(6); // 双子节点
    cout << "删除 6 后：";
    bst.inOrder();
    bst.erase(1); // 叶子节点
    cout << "删除 1 后：";
    bst.inOrder();
}

典型应用场景

理解了增删查，我们来看看 BST 在实际中能做什么。

1. K 模型（Key Model）

只存储 Key，用于判断某个元素是否存在。

• 词库校验：将字典里的单词作为 Key 存入 BST，输入单词时查询是否存在，快速判断拼写错误。
• 门禁系统：记录授权人员 ID，判断是否在名单内。

2. KV 模型（Key-Value Model）

每个 Key 对应一个 Value，形成键值对。

• 英汉词典：Key 是英文单词，Value 是中文释义。
• 频率统计：Key 是单词，Value 是出现次数。遍历文本时，若 Key 存在则 Value+1，否则插入并置为 1。

// KV 模型示例：统计单词频率
template<class K, class V>
struct BSTNodeKV {
    K _key;
    V _value;
    BSTNodeKV<K, V>* _left;
    BSTNodeKV<K, V>* _right;
    BSTNodeKV(const K& k, const V& v) : _key(k), _value(v), _left(nullptr), _right(nullptr) {}
};

// 使用逻辑类似，只需在节点中增加 value 字段，并在插入/更新时处理 value 的增减

总结

二叉搜索树通过简单的规则实现了高效的查找能力。只要记住三个关键点：

1. 有序性：左 < 根 < 右。
2. 删除策略：双子节点时，用后继（右子树最小）或前驱（左子树最大）替换。
3. 性能瓶颈：数据有序会导致退化，实际工程中常配合平衡机制使用。

掌握了 BST，你就迈进了高级数据结构的大门，后续的 AVL 树和红黑树本质上都是在解决 BST 不平衡的问题。