二叉搜索树

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */
#content_views .toc,
/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */
#content_views.markdown_views > p:empty:has(+ .toc),
#content_views.markdown_views > .toc + p:empty,
/* 富文本旧版目录标记 */
#content_views.htmledit_views #main-toc,
#content_views.htmledit_views #hr-toc,
#content_views.htmledit_views p[id*=\”-toc\”] {
display: none !important;
}
/* 目录去掉后，紧跟的首个标题不再多出一块上边距 */
#content_views.markdown_views > .toc + h1,
#content_views.markdown_views > .toc + h2,
#content_views.markdown_views > .toc + h3,
#content_views.markdown_views > .toc + h4,
#content_views.markdown_views > .toc + p:empty + h1,
#content_views.markdown_views > .toc + p:empty + h2,
#content_views.markdown_views > .toc + p:empty + h3,
#content_views.markdown_views > .toc + p:empty + h4 {
margin-top: 0 !important;
}

C++ 二叉搜索树（BST）详解：概念、增删查实现与 key/value 应用场景

前面用过的 map、set，底层都是二叉搜索树。这篇从"为什么需要它"讲到"自己写一棵出来"：结构性质、插入、查找、删除（四种情况 + 替换法）、完整代码，以及 key 和 key/value 两种场景该怎么选。写完之后再看 map，很多接口的设计就能一眼看懂了。

文章目录

• C++ 二叉搜索树（BST）详解：概念、增删查实现与 key/value 应用场景
• • 一、前言：为什么需要二叉搜索树
  • 二、二叉搜索树的概念
  • • 2.1 关于"重复值"
    • 2.2 最重要的一个性质
  • 三、性能分析
  • 四、插入
  • 五、查找
  • 六、删除（最容易写错的一节）
  • • 6.1 情况 4：替换法
    • 6.2 这里有一个必须注意的坑
  • 七、完整实现（key 版）
  • • 7.1 四个实现细节
  • 八、key 与 key/value 两种使用场景
  • • 8.1 key 搜索场景
    • 8.2 key/value 搜索场景
  • 九、key/value 版实现
  • • 9.1 两个典型用法
  • 十、局限与下一步
  • 十一、总结

一、前言：为什么需要二叉搜索树

要在数据里找一个值，常见的手段有三种：

二分查找看起来很美，但有两个绕不过去的缺陷：

也就是说："查得快"和"改得快"在数组上不可兼得。

二叉搜索树要解决的正是这个矛盾——用链式的树形结构同时拿到"接近 log N 的查找"和"O(1) 的节点插入删除"。

这也是我们接下来学习 map / set 系列容器的基础：它们的底层就是二叉搜索树（更准确地说，是它的平衡版本）。

二、二叉搜索树的概念

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

注意第 3 条：这是递归定义——每一棵子树都必须是 BST，整棵树才是 BST。

2.1 关于"重复值"

二叉搜索树可以支持插入相等的值，也可以不支持，具体看使用场景定义：

本节的实现按"不允许重复"来做（插入重复值直接返回 false），这也是最常见的需求。

2.2 最重要的一个性质

对二叉搜索树做中序遍历（左 → 根 → 右），得到的一定是一个有序序列。

这条性质极其有用：它既是"验证一棵树是不是 BST"的最简单方法，也是"用 BST 做排序"的原理。

8
/ \\
3 10
/ \\ \\
1 6 14
/ \\ /
4 7 13

中序遍历：1 3 4 6 7 8 10 13 14 ← 升序

三、性能分析

BST 的效率完全取决于树的高度（因为一次查找最多走一条从根到叶的路径）。

退化是怎么发生的？ 如果按有序序列插入：

插入 1, 2, 3, 4, 5 …

1
\\
2
\\
3
\\
4
\\
5 ← 完全退化成一个链表，查找退化为 O(N)

因为每次插入的值都比现有所有值大，只能一路往右挂——树彻底退化成链表。

所以综合来看，普通二叉搜索树的增删查时间复杂度是 O(N)（最坏情况），平均是 O(log N)（随机数据）。

这样的效率显然无法满足需求，所以后续还需要它的变形——平衡二叉搜索树：AVL 树和红黑树，才能真正适用于在内存中存储和搜索数据。这里也就体现出了平衡二叉搜索树的价值。

四、插入

插入过程分三步：

要点：插入一定发生在叶子位置（新结点总是挂在某个空指针上），所以不需要调整树的结构，也不需要记录"父结点"以外的任何信息。

实现时必须维护 parent 指针：走到 cur == nullptr 时，你手上只有空指针，得靠 parent 才知道该把新结点接到谁的左/右。

五、查找

5
/ \\
3 7
/ \\
3 4 ← 两个 3，中序第一个是最左边的那个

查找 3 时，如果找到根左边那个 3 就返回，虽然值对，但它不是"中序第一个"。要做到语义严格，就必须一路往左走到底——这也是 multiset::find 的语义要求。

六、删除（最容易写错的一节）

首先查找元素是否在树中，不存在直接返回 false。

存在时，设要删除的结点为 N，分四种情况：

情况 1 可以当成情况 2 或 3 处理，效果一样（把空指针接上去，等于把父亲指向空）。所以代码里只需要写三个分支。

6.1 情况 4：替换法

N 的两个孩子无处安放，不能直接删。做法是：

找 N 左子树中值最大的结点 R（最右结点），或者 N 右子树中值最小的结点 R（最左结点），用 R 替代 N。

为什么这两个结点一定行？

• 左子树最大值：它比左子树里所有值都大，又比右子树里所有值都小 → 放到 N 的位置，左右两边的大小关系都成立。
• 右子树最小值：同理。

替代的意思是"交换 N 和 R 的值，转而删除 R 结点"——而 R 一定是情况 2 或情况 3（它最多只有一个孩子），可以直接删。

删除 8（左右都有孩子）
8 10
/ \\ / \\
3 10 ──▶ 3 14
/ \\ \\ / \\ /
1 6 14 1 6 13
/ \\ / / \\
4 7 13 4 7

右子树最小结点是 10（它没有左孩子），把 10 的值搬到 8 的位置，
再删除原来那个 10 结点 —— 它的右孩子 14 顶上来。

6.2 这里有一个必须注意的坑

找右子树最小结点时，代码通常写成：

Node* rightMinP = cur; // 父结点，初值是 cur —— 这一句是关键
Node* rightMin = cur->_right;
while (rightMin->_left) {
rightMinP = rightMin;
rightMin = rightMin->_left;
}

rightMinP 的初值必须是 cur，不能是 nullptr。

因为存在一种特殊情况：cur->_right 本身就没有左孩子（比如上面删 8 时，右子树根 10 就是最小值）。这时 while 循环一次都不执行，rightMinP 仍然是初值——如果初值是 nullptr，后面去访问 rightMinP->_left 就是空指针解引用，直接崩。

初值给 cur 之后，后面用 if (rightMinP->_left == rightMin) 判断挂在哪边，两种情况都能正确处理。

七、完整实现（key 版）

#include <iostream>
#include <cassert>
using namespace std;

namespace bit {

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

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

// Binary Search Tree
template<class K>
class BSTree {
typedef BSTNode<K> Node;

public:
BSTree() = default;

bool Insert(const K& key) {
if (_root == nullptr) {
_root = new Node(key);
return true;
}

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 {
return false; // 已存在，不允许重复插入
}
}

cur = new Node(key);
if (parent->_key < key)
parent->_right = cur;
else
parent->_left = cur;
return true;
}

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;
}

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 {
// 找到，开始删除

// —- 情况 1、2：左孩子为空（含左右都空）—-
if (cur->_left == nullptr) {
if (parent == nullptr) // 删的是根
_root = cur->_right;
else if (parent->_left == cur)
parent->_left = cur->_right;
else
parent->_right = cur->_right;

delete cur;
return true;
}
// —- 情况 3：右孩子为空 —-
else if (cur->_right == nullptr) {
if (parent == nullptr)
_root = cur->_left;
else if (parent->_left == cur)
parent->_left = cur->_left;
else
parent->_right = cur->_left;

delete cur;
return true;
}
// —- 情况 4：左右都不为空，替换法 —-
else {
// 取右子树的最小结点（最左结点）作为替代结点
Node* rightMinP = cur; // 初值必须是 cur，不能是 nullptr
Node* rightMin = cur->_right;
while (rightMin->_left) {
rightMinP = rightMin;
rightMin = rightMin->_left;
}

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

// 把 rightMin 的孩子接到它的父亲上
if (rightMinP->_left == rightMin)
rightMinP->_left = rightMin->_right;
else
rightMinP->_right = rightMin->_right;

delete rightMin;
return true;
}
}
}
return false;
}

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

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

private:
Node* _root = nullptr;
};

} // namespace bit

用法：

int main() {
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
bit::BSTree<int> t;
for (auto e : a)
t.Insert(e);

t.InOrder(); // 1 3 4 6 7 8 10 13 14

t.Erase(8); // 删有两个孩子的结点
t.InOrder(); // 1 3 4 6 7 10 13 14

t.Erase(1); // 删叶子
t.Erase(14); // 删只有一个孩子的结点
t.InOrder(); // 3 4 6 7 10 13
return 0;
}

7.1 四个实现细节

① parent == nullptr 这个判断不能省

它对应"删除的是根结点"的情况。此时没有父亲可以改指针，必须直接改 _root。这是最容易漏的分支——只测非根结点的删除，代码看起来完全正确，一删根就崩。

② if (parent->_left == cur) 判断挂在哪边

因为 while 循环里没有记录"是从左边下来的还是右边下来的"，只能靠指针比较反推。也可以用 parent->_key > key 来判断，但指针比较更直接（值可能重复，指针不会）。

③ 情况 4 只交换值，不交换结点

cur->_key = rightMin->_key; 然后删 rightMin。不要试图交换两个结点的链接关系——那需要处理 rightMinP == cur 的特殊情况，代码复杂度高得多，而且没有任何收益。

④ 删完要 return true

因为 delete cur 之后 cur 已失效，不能再继续循环，必须立刻返回。

八、key 与 key/value 两种使用场景

同样的 BST 结构，按"结点里存什么"分成两种用法。

8.1 key 搜索场景

只有 key 作为关键码，结构中只需要存储 key，关键码即为需要搜索到的值。搜索场景只需要判断 key 在不在。

这种 BST 支持增、删、查，但不支持修改——修改 key 会破坏搜索树的结构。

场景 1：小区无人值守车库

买了车位的业主车才能进小区。物业把买了车位的业主的车牌号录入后台系统，车辆进入时扫描车牌，在系统中则抬杆，不在则提示非本小区车辆。

这里只需要判断"车牌在不在"，车牌本身就是 key，不需要额外信息 → key 场景。

场景 2：英文文章单词拼写检查

把词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在树中，不在则波浪线标红提示。

同样只需要判断"在不在" → key 场景。

8.2 key/value 搜索场景

每一个关键码 key，都有与之对应的值 value，value 可以是任意类型对象。

树的结构中（结点里）除了 key 还要存储对应的 value。增、删、查仍然以 key 为关键字走 BST 规则比较，从而快速找到 key 对应的 value。

这种 BST 支持修改 value，但不支持修改 key（修改 key 同样会破坏 BST 性质）。

场景 1：简单的英汉词典

结点存 key（英文）和 value（中文）。输入英文，就能同时查到对应的中文。

场景 2：商场无人值守车库

• 入口进场时扫描车牌，记录车牌和入场时间；
• 出口离场时扫描车牌，查找入场时间，用 当前时间 – 入场时间 算出停车时长，算出费用，缴费后抬杆。

这里"车牌 → 入场时间"就是典型的键值对 → key/value 场景。

注意和 8.1 场景 1 的区别：那个小区车库只需要判断"有没有资格进"，是纯 key；这个商场车库要存"入场时间"这个额外数据，必须 value。

场景 3：统计文章中单词出现次数

读取一个单词，查找是否存在：

• 不存在 → 说明第一次出现，插入 (单词, 1)；
• 存在 → ++ 该单词对应的次数。

这就是 std::map<string, int> 的经典用法。

九、key/value 版实现

结构上只比 key 版多一个 _value 字段，另外补上"管理资源"需要的四件套（拷贝构造、赋值、析构），因为结点是用 new 出来的，默认的浅拷贝会导致两个树共用同一批结点 → 二次释放。

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

BSTNode(const K& key, const V& value)
: _key(key)
, _value(value)
, _left(nullptr)
, _right(nullptr)
{}
};

template<class K, class V>
class BSTree {
typedef BSTNode<K, V> Node;

public:
BSTree() = default;

BSTree(const BSTree<K, V>& t) {
_root = Copy(t._root);
}

// 现代写法：传值 + swap
BSTree<K, V>& operator=(BSTree<K, V> t) {
swap(_root, t._root);
return *this;
}

~BSTree() {
Destroy(_root);
_root = nullptr;
}

bool Insert(const K& key, const V& value) {
if (_root == nullptr) {
_root = new Node(key, value);
return true;
}

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

cur = new Node(key, value);
if (parent->_key < key)
parent->_right = cur;
else
parent->_left = cur;
return true;
}

// 注意返回的是结点指针 —— 调用方要能改 value
Node* 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 cur;
}
return nullptr;
}

bool Erase(const K& key) {
// 与 key 版完全相同，省略
// …
return false;
}

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

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

void Destroy(Node* root) {
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete 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;
}

private:
Node* _root = nullptr;
};

为什么 Find 要返回 Node* 而不是 bool？

因为 key/value 场景的核心价值是"通过 key 拿到 value"。返回 bool 只能说"在不在"，拿不到值，也就改不了值。返回结点指针之后：

auto ret = tree.Find("苹果");
if (ret)
ret->_value++; // 直接改，不需要再插入一次

9.1 两个典型用法

词典

int main() {
bit::BSTree<string, string> dict;
dict.Insert("left", "左边");
dict.Insert("right", "右边");
dict.Insert("insert", "插入");
dict.Insert("string", "字符串");

string str;
while (cin >> str) {
auto ret = dict.Find(str);
if (ret)
cout << "->" << ret->_value << endl;
else
cout << "无此单词，请重新输入" << endl;
}
return 0;
}

统计词频

int main() {
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果",
"西瓜", "苹果", "香蕉", "苹果", "香蕉" };

bit::BSTree<string, int> countTree;
for (const auto& str : arr) {
auto ret = countTree.Find(str);
if (ret == nullptr)
countTree.Insert(str, 1); // 第一次出现
else
ret->_value++; // 已存在，次数 ++
}

countTree.InOrder(); // 按 key 升序输出
return 0;
}

输出是按 key 升序的（因为中序遍历），这正是 BST 相比哈希表的额外好处：它天然有序。

十、局限与下一步

普通 BST 的问题在第三节已经说清楚了：结构依赖插入顺序，最坏退化成链表。

插入顺序 4,2,6,1,3,5,7 → 插入顺序 1,2,3,4,5,6,7 →
4 1
/ \\ \\
2 6 2
/ \\ / \\ \\
1 3 5 7 3
\\
（高度 3，查找 O(log N)） 4 …（高度 7，查找 O(N)）

解决思路是让树在插入/删除后自动调整，把高度压在 O(log N)，这就是平衡二叉搜索树：

另外两个可以顺带记住的点：

• BST 天然支持排序：全部插入后中序遍历即得升序序列，平均 O(N log N)。
• BST 天然支持范围查询：找 [a, b] 区间的值，比哈希表容易得多（哈希表完全无序）。这也是 map/set 选择树而不是哈希的原因之一。

十一、总结

全篇的脉络：

为什么需要 → 结构性质 → 三个操作 → 两种场景

如果只能记三句话：

① 中序遍历有序，是 BST 的灵魂；一条路径走到底，是 BST 的效率来源。 ② 删除两个孩子的结点，靠"用后继/前驱替换值"，不是替换结点。 ③ 普通 BST 会退化，真正能用的是平衡版本——所以要接着学 AVL 和红黑树。