二叉搜索树 C++ 实现：增删查改详解

什么是二叉搜索树

二叉搜索树（Binary Search Tree, BST）又称二叉排序树。它或者是一棵空树，或者是具有以下性质的二叉树：

• 左子树上所有节点的值都小于等于根结点的值；
• 右子树上所有节点的值都大于等于根结点的值；
• 它的左右子树也分别为二叉搜索树。

注意：二叉搜索树中可以支持插入相等的值，也可以不支持。具体取决于使用场景定义。例如标准库中的 std::map/std::set 不支持插入相等值，而 std::multimap/std::multiset 支持。

性能分析

在最优情况下，二叉搜索树为完全二叉树（或接近完全二叉树），其高度约为 log₂N。

最差情况下，二叉搜索树退化为单支树（类似链表），其高度为 N。

因此平均时间复杂度为 O(log n)，最差情况为 O(n)。

虽然二分查找也能实现 O(log₂N) 级别的查找效率，但存在两大缺陷：

1. 需要存储在支持下标随机访问的结构中，并且数据必须有序。
2. 插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除通常需要挪动大量数据。

Key 类型二叉搜索树的实现

后续要学习的 std::set/std::multiset 容器底层数据结构就是红黑树——一种'近似平衡'的二叉搜索树。对于 set/multiset 容器，集合是一种按照特定顺序存储唯一元素的容器。

节点结构

template<class K> struct BSTNode {
    K _key;
    BSTNode<K>* _left;
    BSTNode<K>* _right;
    
    BSTNode(const K& key = 0)
        :_key(key), _left(nullptr), _right(nullptr) {}
};

类结构

template<class K> class BSTree {
    using Node = BSTNode<K>;
public:
    // ... 成员函数
private:
    Node* _root = nullptr;
};

下面实现过程中默认为值不重复的情形。

插入操作

思路如下：

1. 若树为空，直接新增结点，赋值给 root 指针。
2. 若树不空，按二叉搜索树性质，用 cur 指针遍历，parent 指针记下父亲节点。若插入值 key 比当前节点大往右走，小则往左走，直到找到空位置插入新结点。
3. 确定新节点是插在 parent 的左边还是右边。
4. 若支持插入相等值，需统一规则（如全部往右走）。这里我们实现不支持重复值的逻辑。

bool Insert(const K& key) {
    Node* node = new Node(key);
    if (_root == nullptr) {
        _root = node;
        return true;
    }
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur) {
        if (key < cur->_key) {
            parent = cur;
            cur = cur->_left;
        } else if (key > cur->_key) {
            parent = cur;
            cur = cur->_right;
        } else {
            return false; // 已存在
        }
    }
    if (key < parent->_key) {
        parent->_left = node;
    } else {
        parent->_right = node;
    }
    return true;
}

中序遍历

根据二叉搜索树的特性，其中序遍历的结果恰好为一个有序序列（升序）。由于 _root 是成员变量，在类外调用无法直接传参，通常采用辅助递归函数实现。

void MidOrder() {
    _MidOrder(_root);
}

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

查找操作

从根开始比较，val 比根大往右找，小则往左找。最多查找高度次，若走到空仍未找到则返回 false。

bool 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 {
            return true;
        }
    }
    return false;
}

删除操作

删除是最复杂的部分，主要分三种情况处理：

1. 左为空：将父节点的指针指向右孩子（若为根节点则更新_root）。
2. 右为空：将父节点的指针指向左孩子（若为根节点则更新_root）。
3. 左右都不为空：无法直接删除，需用替换法。找 N 左子树的最大结点（最右结点）或 N 右子树的最小结点（最左结点）替代 N。交换值后，问题转化为删除那个替代结点（此时该结点必属于情况 1 或 2）。

bool Erase(const K& val) {
    Node* cur = _root;
    Node* parent = nullptr;
    
    while (cur) {
        if (val < cur->_key) {
            parent = cur;
            cur = cur->_left;
        } else if (val > cur->_key) {
            parent = cur;
            cur = cur->_right;
        } else {
            // 找到待删除节点
            // 左为空
            if (cur->_left == nullptr) {
                if (_root == cur) {
                    _root = cur->_right;
                } else if (parent->_left == cur) {
                    parent->_left = cur->_right;
                } else {
                    parent->_right = cur->_right;
                }
                delete cur;
            }
            // 右为空
            else if (cur->_right == nullptr) {
                if (_root == cur) {
                    _root = cur->_left;
                } else if (parent->_left == cur) {
                    parent->_left = cur->_left;
                } else {
                    parent->_right = cur->_left;
                }
                delete cur;
            }
            // 左右均不为空
            else {
                Node* replaceParent = cur;
                Node* replace = cur->_right;
                // 找右子树中最小值的节点 R
                while (replace->_left) {
                    replaceParent = replace;
                    replace = replace->_left;
                }
                // 交换值
                cur->_key = replace->_key;
                // 删除替代节点
                if (replaceParent->_left == replace) {
                    replaceParent->_left = replace->_right;
                } else {
                    replaceParent->_right = replace->_right;
                }
                delete replace;
            }
            return true;
        }
    }
    return false;
}

Key_Value 类型二叉搜索树的实现

对于 std::map/std::multimap 容器，映射是一种关联容器，存储由'键值（key value）'和'映射值（mapped value）'组合而成的元素。

节点与类结构

相比 Key 类型，节点多了 _value 成员，类结构基本一致。

template<class K, class V> struct BSTNode {
    K _key;
    V _value;
    BSTNode<K, V>* _left;
    BSTNode<K, V>* _right;
    
    BSTNode(const K& key = 0, const V& value = 0)
        :_key(key), _value(value), _left(nullptr), _right(nullptr) {}
};

template<class K, class V> class BSTree {
    using Node = BSTNode<K, V>;
public:
    // ...
private:
    Node* _root = nullptr;
};

除插入操作略有不同外，其他操作逻辑与 Key 类型基本相同，重点补充构造、析构及拷贝控制。

构造函数与拷贝构造

默认构造可直接使用 = default。拷贝构造需进行深拷贝，避免浅拷贝导致的悬空指针。

// 默认构造
BSTree() = default;

// 拷贝构造（深拷贝）
BSTree(const BSTree& tree) {
    _root = Copy(tree._root);
}

Node* Copy(Node* root) {
    if (root == nullptr) return nullptr;
    Node* newRoot = new Node(root->_key, root->_value);
    newRoot->_left = Copy(root->_left);
    newRoot->_right = Copy(root->_right);
    return newRoot;
}

赋值重载与析构

现代 C++ 写法中，赋值运算符可通过交换实现（Copy-and-Swap 惯用法）。析构函数需使用后序遍历释放内存，防止根节点释放后丢失子节点引用。

// 赋值重载
BSTree& operator=(BSTree tree) {
    swap(_root, tree._root);
    return *this;
}

// 析构函数
~BSTree() {
    Destroy(_root);
    _root = nullptr;
}

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

插入操作

bool Insert(const K& key, const V& value) {
    Node* node = new Node(key, value);
    if (_root == nullptr) {
        _root = node;
        return true;
    }
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur) {
        if (key < cur->_key) {
            parent = cur;
            cur = cur->_left;
        } else if (key > cur->_key) {
            parent = cur;
            cur = cur->_right;
        } else {
            return false;
        }
    }
    if (key < parent->_key) {
        parent->_left = node;
    } else {
        parent->_right = node;
    }
    return true;
}

总结

本文简单实现了二叉搜索树的基础版本，涵盖增删查改及构造析构等核心功能。它与 std::set/std::map 底层的平衡二叉搜索树（如红黑树）有所不同，未过多关注底层平衡细节，旨在帮助大家理解 BST 的基本原理，为后续学习平衡树打下基础。