前言
"搜索二叉树"就是二叉搜索树（binary search tree, BST），有的教材也叫二叉排序树。它是最基础的动态查找结构：每个结点最多两个子结点，且满足"左子树所有键小于根、右子树所有键大于根"的有序性质。有了这条性质，查找、插入、删除都能沿着一条从根到叶的路径完成，平均代价与树高成正比。
很多人学完定义就以为 BST 查找一定是 O(log n)，这是一个需要纠正的印象：O(log n) 只在树大致平衡时成立。如果按升序依次插入1, 2, 3, ...，树会退化成一条链，查找变成 O(n)，和链表没有区别。BST 本身不保证平衡，保证平衡的是它的变体（AVL 树、红黑树、B 树等）。理解这一点，才能明白为什么标准库的std::map/std::set通常用红黑树而不是裸 BST。
本文从结点定义讲起，逐步实现查找、插入、删除（重点是最麻烦的"两个子结点"情形），再讨论遍历、复杂度与退化问题。示例用std::unique_ptr管理结点，避免手写new/delete，以 C++17 为基准。
一、结点定义与有序性质
一个 BST 结点包含键、左孩子指针、右孩子指针，业务场景里还常有值。这里用模板让键类型可替换，并要求键类型支持<比较（或者由调用方提供比较器，本文从简）。
// 适用于 C++17
#include <memory>
template <class Key>
struct Node {
Key key;
std::unique_ptr<Node> left;
std::unique_ptr<Node> right;
explicit Node(const Key& k) : key(k) {}
};有序性质的标准表述是：对任意结点n，其左子树中所有键都小于n->key，右子树中所有键都大于n->key。注意这是整棵子树的约束，不只是直接孩子。很多错误实现只比较父子，导致中序遍历并非有序。
由此可以直接推出一个重要结论：BST 的中序遍历（左—根—右）得到升序序列。这条性质既是检验实现是否正确的手段，也是很多算法（范围查询、第 k 小、有序输出）的基础。
关于重复键，有三种常见策略：拒绝插入（保持集合语义，类似std::set）、允许重复并统一放右侧、每个结点维护计数（类似std::multiset）。本文采用第一种，插入时发现相等就返回失败。策略没有对错，但必须在接口文档里写清楚，否则删除和查找的语义会含糊。
二、查找与插入
查找是 BST 最基本的操作：从根开始，目标小于当前键就走左，大于就走右，相等就命中，走到空指针说明不存在。整个过程是一个循环，不需要递归。
// 适用于 C++17
template <class Key>
bool contains(const std::unique_ptr<Node<Key>>& root, const Key& target) {
const Node<Key>* cur = root.get();
while (cur != nullptr) {
if (target < cur->key) {
cur = cur->left.get();
} else if (cur->key < target) {
cur = cur->right.get();
} else {
return true;
}
}
return false;
}这里用target < cur->key和cur->key < target两次比较，而不是target == cur->key加一次<。原因是模板参数只要求支持<，不要求==；这也是一般泛型代码的写法。C++20 有了三路比较后可以写<=>，但那是另一个话题。
插入的路径与查找相同，区别是走到空位后把新结点挂上去。为了不改动根指针的持有者，可以用"指向指针的指针"（或指向unique_ptr的指针）自顶向下走：
// 适用于 C++17
template <class Key>
bool insert(std::unique_ptr<Node<Key>>& root, const Key& key) {
auto* slot = &root; // 指向当前待填的指针槽
while (*slot != nullptr) {
Node<Key>* cur = slot->get();
if (key < cur->key) {
slot = &cur->left;
} else if (cur->key < key) {
slot = &cur->right;
} else {
return false; // 已存在，拒绝重复
}
}
*slot = std::make_unique<Node<Key>>(key);
return true;
}slot的类型是std::unique_ptr<Node<Key>>*。初始指向root；之后指向某个结点的left或right成员。这种写法避免了"记录父结点再判断是左还是右"的分支，也天然处理了空树。*slot = std::make_unique<...>直接完成挂接，所有权清晰。
插入的复杂度同样是 O(h)，h 为树高。树平衡时 h 约为 log₂n，退化时 h 为 n。
三、删除：三种情形与后继结点
删除是 BST 里最容易写错的操作。设待删结点为z，分三种情况：
- z 是叶子：直接删除，父结点对应指针置空。
- z 只有一个孩子：用这个孩子顶替 z 的位置。
- z 有两个孩子：不能简单删除，否则左右两棵子树无处安放。标准做法是找到 z 的中序后继（右子树中的最小结点），把它的键复制到 z，然后转而删除那个后继结点。后继结点最多只有右孩子（它没有左孩子，否则它不是最小），于是问题退化成情形 1 或 2。
也可以改用中序前驱（左子树最大结点），两者对称，选一个即可。
// 适用于 C++17
template <class Key>
std::unique_ptr<Node<Key>> erase(std::unique_ptr<Node<Key>> node, const Key& key) {
if (node == nullptr) {
return nullptr; // 没找到
}
if (key < node->key) {
node->left = erase(std::move(node->left), key);
} else if (node->key < key) {
node->right = erase(std::move(node->right), key);
} else {
if (node->left == nullptr) {
return std::move(node->right); // 情形 1 或 2（只有右孩子）
}
if (node->right == nullptr) {
return std::move(node->left); // 情形 2（只有左孩子）
}
// 情形 3：找右子树最小结点
Node<Key>* successor = node->right.get();
while (successor->left != nullptr) {
successor = successor->left.get();
}
node->key = successor->key; // 复制键（值语义）
node->right = erase(std::move(node->right), successor->key);
}
return node;
}这段代码用递归返回新的子树根，配合unique_ptr的移动语义，删除结点时所有权自然转移，不需要手动delete。几个细节：
return std::move(node->right);把右子树的所有权交出去，node随即被销毁。这里必须写std::move，因为unique_ptr不可拷贝；如果直接return node->right;，编译器会尝试拷贝，编译失败（C++17 的 guaranteed copy elision 不适用于成员访问表达式）。- 情形 3 里先复制键，再递归删除后继。复制要求
Key可拷贝赋值；如果键类型只能移动，需要换一种实现（比如把后继结点整体摘下来拼接）。 - 递归深度等于树高。退化树可能很深，递归有栈溢出风险。工程实现常改成迭代版本，或者用带父指针的结点。
四、遍历、复杂度与退化
中序遍历可以用递归，也可以用显式栈迭代。递归写法最简洁：
// 适用于 C++17
template <class Key, class Fn>
void inorder(const Node<Key>* node, Fn&& visit) {
if (node == nullptr) return;
inorder(node->left.get(), visit);
visit(node->key);
inorder(node->right.get(), visit);
}传入的Fn是按转发引用接收的，调用visit(node->key)时不会产生额外拷贝。这种"回调式遍历"比"返回一个std::vector"更灵活，调用方可以累加、打印或提前终止（提前终止需要让回调返回bool，或者用异常，前者更清晰）。
复杂度总结如下：
| 操作 | 平均（平衡） | 最坏（退化） | 说明 |
|---|
| 查找 | O(log n) | O(n) | 与树高 h 成正比 |
| 插入 | O(log n) | O(n) | 先查找空位再挂接 |
| 删除 | O(log n) | O(n) | 找后继也是 O(h) |
| 中序遍历 | O(n) | O(n) | 每个结点访问一次 |
| 空间 | O(n) | O(n) | 每个结点两个指针 |
退化是 BST 的固有缺陷。插入有序序列1..n时，每次都在最右侧挂新结点，树高为 n。解决方向有两类：一是使用自平衡结构（AVL 树通过旋转维持左右子树高度差不超过 1；红黑树用颜色约束把树高控制在 2log(n+1) 以内），二是使用随机化（ treap 给每个结点分配随机优先级，按堆性质调整），三是改用 B 树/B+ 树应对磁盘或缓存场景。标准库的std::map、std::set、std::multimap、std::multiset通常以红黑树实现，但标准只规定接口与复杂度，不规定必须用红黑树。
如果只是需要有序集合，优先用标准库容器；手写 BST 的价值在于理解结构与算法，或者需要标准库不提供的操作（如按秩查询、区间聚合）。
完整示例
下面把上面的片段组装成一个可用的BST类，并演示插入、查找、删除和中序输出：
// 适用于 C++17
#include <cstddef>
#include <functional>
#include <iostream>
#include <memory>
#include <vector>
template <class Key>
class BST {
public:
bool insert(const Key& key) {
auto* slot = &root_;
while (*slot != nullptr) {
Node* cur = slot->get();
if (key < cur->key) {
slot = &cur->left;
} else if (cur->key < key) {
slot = &cur->right;
} else {
return false;
}
}
*slot = std::make_unique<Node>(key);
++size_;
return true;
}
bool contains(const Key& key) const {
const Node* cur = root_.get();
while (cur != nullptr) {
if (key < cur->key) {
cur = cur->left.get();
} else if (cur->key < key) {
cur = cur->right.get();
} else {
return true;
}
}
return false;
}
bool erase(const Key& key) {
const std::size_t before = size_;
root_ = erase_impl(std::move(root_), key);
return size_ != before;
}
std::vector<Key> sorted() const {
std::vector<Key> out;
out.reserve(size_);
inorder(root_.get(), [&out](const Key& k) { out.push_back(k); });
return out;
}
std::size_t size() const { return size_; }
private:
struct Node {
Key key;
std::unique_ptr<Node> left;
std::unique_ptr<Node> right;
explicit Node(const Key& k) : key(k) {}
};
static void inorder(const Node* node, const std::function<void(const Key&)>& visit) {
if (node == nullptr) return;
inorder(node->left.get(), visit);
visit(node->key);
inorder(node->right.get(), visit);
}
std::unique_ptr<Node> erase_impl(std::unique_ptr<Node> node, const Key& key) {
if (node == nullptr) return nullptr;
if (key < node->key) {
node->left = erase_impl(std::move(node->left), key);
return node;
}
if (node->key < key) {
node->right = erase_impl(std::move(node->right), key);
return node;
}
if (node->left == nullptr) {
--size_;
return std::move(node->right);
}
if (node->right == nullptr) {
--size_;
return std::move(node->left);
}
Node* succ = node->right.get();
while (succ->left != nullptr) succ = succ->left.get();
node->key = succ->key;
node->right = erase_impl(std::move(node->right), succ->key);
return node;
}
std::unique_ptr<Node> root_;
std::size_t size_ = 0;
};
int main() {
BST<int> tree;
for (int v : {50, 30, 70, 20, 40, 60, 80}) {
tree.insert(v);
}
std::cout << "size = " << tree.size() << '\n'; // 7
std::cout << "contains 40: " << tree.contains(40) << '\n'; // 1
tree.erase(30); // 两个子结点：用中序后继 40 替换
for (int v : tree.sorted()) {
std::cout << v << ' ';
}
std::cout << '\n'; // 20 40 50 60 70 80
return 0;
}按标准语义，sorted()输出升序序列20 40 50 60 70 80。删除 30 时，右子树最小结点是 40，于是 40 的键被复制到 30 的位置，再删除原来的 40 结点。
这里为了简化，inorder用了std::function；前文提到过它有类型擦除开销，生产代码可以改成模板参数。另外erase_impl在情形 3 里递归删除后继时不会再次减少size_（因为后继最多一个孩子，会在情形 1/2 分支里减一次），整体恰好减一，逻辑是自洽的。
常见坑点
- ❌ 只比较父子结点，不保证整棵子树有序
✅ 左子树全部键小于根、右子树全部键大于根；用中序遍历是否升序来自检
- ❌ 用
std::vector<Key>存树并指望插入是 O(log n)
✅ 顺序存储只适合完全二叉树；普通 BST 需要结点指针
- ❌ 删除有两个孩子的结点时，直接把整棵子树丢掉
✅ 用中序后继（或前驱）替换键，再删除后继结点
- ❌ 删除时忘记处理"只有一个孩子"的情况
✅ 用唯一的孩子顶替，unique_ptr直接移动返回即可
- ❌
return node->right;想转移unique_ptr所有权
✅ 写return std::move(node->right);，成员访问不会自动移动
- ❌ 认为 BST 查找一定是 O(log n)
✅ 只有平衡时才是；有序插入会退化成 O(n)，需要自平衡或随机化
- ❌ 递归实现不评估树高
✅ 退化树递归深度可达 n，深树应改迭代或使用平衡树
- ❌ 重复键策略不明确，插入/删除/查找三处行为不一致
✅ 明确拒绝、计数或统一放右侧，并在接口文档中写清
总结
| 要点 | 做法 | 原因 |
|---|
| 有序性 | 左小右大，整棵子树成立 | 支撑查找、插入、删除沿单路径进行 |
| 查找 | 循环比较，走到空即失败 | O(h)，无需递归 |
| 插入 | 用指向指针槽的指针定位空位 | 避免记录父结点与左右分支 |
| 删除 | 叶子/单孩子/双孩子三种情形 | 双孩子用中序后继替换 |
| 所有权 | std::unique_ptr加移动 | 异常安全，无需手写 delete |
| 平衡 | AVL、红黑树、treap 等变体 | 裸 BST 最坏 O(n) |
| 遍历 | 中序得升序；回调式更灵活 | 检验有序性、支持范围操作 |
二叉搜索树的价值在于把"有序"和"可快速查找"结合起来。实现时真正需要想清楚的是三件事：有序性约束如何在每次修改后保持、删除双孩子结点时如何不破坏结构、以及树的形状是否会因输入分布而退化。前两点靠严谨的分支处理，第三点则要靠平衡策略或对输入分布的清醒认识。
