C++ 二叉搜索树详解：从一个结点到完整 BST 实现
C++ 二叉搜索树详解：从一个结点到完整 BST 实现
文章目录
- C++ 二叉搜索树详解：从一个结点到完整 BST 实现
- 前言
- 一、先从一个二叉树结点开始
- 二、从局部大小关系构成二叉搜索树
- 三、为什么中序遍历会得到有序序列？
- 四、查找：每比较一次，就排除一半方向
- 五、插入：查找失败的位置就是新结点的位置
- 六、删除：二叉搜索树中最复杂的操作
- 七、删除代码逐步实现
- 八、一个完整的二叉搜索树实现
- 九、为什么析构要使用后序遍历？
- 十、为什么二叉搜索树需要深拷贝？
- 十一、为什么使用 Compare，而不是直接写小于号？
- 十二、测试完整代码
- 十三、key 模型：只关心一个值是否存在
- 十四、key/value 模型：通过 key 查找对应信息
- 十五、key/value 的查找接口应该返回什么？
- 十六、应用一：简单中英词典
- 十七、应用二：统计单词出现次数
- 十八、二叉搜索树的性能分析
- 十九、二分查找和二叉搜索树有什么区别？
- 二十、为什么还要学习 AVL 树和红黑树？
- 二十三、把所有知识点串起来
前言
在学习普通二叉树时，我们主要关注的是树的结构，以及前序、中序、后序、层序等遍历方式。
但普通二叉树有一个问题：结点之间没有统一的大小关系。
假设现在要在一棵普通二叉树中查找数字 13，除了把整棵树遍历一遍，我们通常没有更好的办法。因为站在某个结点上时，并不知道目标应该在左子树还是右子树。
二叉搜索树在普通二叉树的基础上增加了一条有序规则：
较小的数据放在左边
较大的数据放在右边
正是这条看起来很简单的规则，让树具备了定向查找、插入和删除的能力。
一、先从一个二叉树结点开始
1.1 一个结点需要保存什么？
最基础的二叉树结点通常包含三部分：
当前结点的数据
指向左孩子的指针
指向右孩子的指针
使用 C++ 模板可以写成：
template<class K>
struct BSTNode
{
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
explicit BSTNode(const K& key)
: _key(key)
, _left(nullptr)
, _right(nullptr)
{
}
};
其中：
_key ：当前结点保存的关键字
_left ：指向左子树
_right ：指向右子树
刚创建结点时，它还没有孩子，所以：
_left = nullptr;
_right = nullptr;
一个结点可以简单画成：
┌─────────┐
│ key │
└─────────┘
/ \
left right
目前这个结构还只是普通二叉树结点。
想让它成为二叉搜索树，还需要增加一条关于数据大小的规则。
二、从局部大小关系构成二叉搜索树
2.1 二叉搜索树的基本规则
二叉搜索树也叫二叉排序树，英文是：
Binary Search Tree
BST
一棵二叉搜索树需要满足：
1. 左子树中的所有关键字都小于当前结点
2. 右子树中的所有关键字都大于当前结点
3. 左子树和右子树本身也分别是二叉搜索树
例如：
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
观察根结点 8：
左子树：1、3、4、6、7，都小于 8
右子树：10、13、14，都大于 8
再观察结点 3：
左边的 1 小于 3
右边的 4、6、7 大于 3
这条规则并不是只对根结点成立，而是对树中的每一个结点都成立。
2.2 不只是比较直接孩子
一个常见误区是把二叉搜索树理解成：
左孩子小于根
右孩子大于根
这还不够。
正确规则要求：
整棵左子树的所有结点都小于根
整棵右子树的所有结点都大于根
例如下面这棵树不是二叉搜索树：
8
/
3
\
10
虽然 3 < 8，但 10 位于 8 的左子树中，而：
10 > 8
所以它破坏了二叉搜索树的整体性质。
2.3 是否允许重复关键字？
二叉搜索树可以设计成允许重复，也可以设计成不允许重复。
不允许重复时：
左子树 < 根 < 右子树
允许重复时，可以规定：
左子树 < 根 <= 右子树
或者规定：
左子树 <= 根 < 右子树
关键不在于重复值必须放哪一边，而在于规则必须保持一致。
不能出现：
这一次相等往左走
下一次相等又往右走
否则查找、删除和遍历时很难确定重复元素的位置。
本文实现的是不允许重复关键字的二叉搜索树：
key 小于当前结点：向左
key 大于当前结点：向右
key 等于当前结点：插入失败
这类似于唯一键集合的语义。
三、为什么中序遍历会得到有序序列？
3.1 中序遍历的访问顺序
中序遍历的顺序是：
左子树
根结点
右子树
代码形式是：
void InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
InOrder(root->_left);
cout << root->_key << " ";
InOrder(root->_right);
}
对于下面的二叉搜索树：
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
中序遍历结果为：
1 3 4 6 7 8 10 13 14
这是一个递增序列。
3.2 为什么一定有序？
站在任意一个结点的位置看：
左子树所有值 < 当前结点 < 右子树所有值
中序遍历先访问左子树，所以较小的值先输出。
然后输出当前结点。
最后访问右子树，所以较大的值最后输出。
而左右子树本身又是二叉搜索树，所以它们内部的中序遍历也是有序的。
因此：
左子树的有序序列
+ 当前结点
+ 右子树的有序序列
拼接起来仍然是有序序列。
这不是遍历结束后再排序，而是树本身的结构已经维护了顺序。
3.3 中序遍历可以用来检查 BST
如果一棵不包含重复关键字的二叉树是二叉搜索树，那么它的中序遍历结果应当严格递增。
例如：
1 3 4 6 7 8 10 13 14
如果遍历结果出现：
1 3 10 8 14
就说明树中的大小关系可能已经被破坏。
不过要注意：
中序有序是判断 BST 的重要依据，但实际验证时还要注意重复值策略以及比较器的定义。
四、查找：每比较一次，就排除一半方向
4.1 查找的核心思路
假设要查找 13：
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
第一步比较：
13 > 8
所以不用再看 8 的左子树，直接向右走。
第二步：
13 > 10
继续向右。
第三步：
13 < 14
转向左子树。
第四步找到：
13 == 13
完整路径是：
8 → 10 → 14 → 13
每次比较后，只有一个方向可能包含目标。
4.2 查找失败的情况
假设查找 12：
12 > 8 → 向右
12 > 10 → 向右
12 < 14 → 向左
12 < 13 → 向左
最后走到：
nullptr
说明目标不存在。
因此查找只有两个结束条件：
找到相等结点：查找成功
走到空指针：查找失败
4.3 迭代查找代码
bool Find(const K& key) const
{
Node* cur = _root;
while (cur != nullptr)
{
if (key < cur->_key)
{
cur = cur->_left;
}
else if (key > cur->_key)
{
cur = cur->_right;
}
else
{
return true;
}
}
return false;
}
主循环中只有三种情况：
key < 当前值：向左走
key > 当前值：向右走
key == 当前值：返回成功
4.4 查找次数取决于什么？
查找过程只会沿着树中的一条路径向下。
因此查找次数与树高 h 成正比：
时间复杂度：O(h)
如果树接近平衡：
h ≈ log₂N
查找效率接近：
O(log N)
如果树退化成单支树：
h ≈ N
查找效率就变成：
O(N)
所以二叉搜索树真正影响效率的不是结点总数本身，而是树高。
五、插入：查找失败的位置就是新结点的位置
5.1 插入的本质
在二叉搜索树中插入一个值，实际上就是先执行一次查找。
区别是：
普通查找走到空位置后结束
插入操作走到空位置后创建新结点
例如依次插入：
8, 3, 1, 10, 6, 4, 7, 14, 13
插入 6 时：
6 < 8 → 向左
6 > 3 → 向右
当前位置为空 → 插入 6
插入结果：
8
/
3
\
6
5.2 为什么需要 parent 指针？
查找插入位置时，cur 最终会走到空：
cur == nullptr
但空指针本身无法告诉我们新结点应该连接到谁。
所以需要额外保存一个 parent：
Node* parent = nullptr;
Node* cur = _root;
每次移动之前，先记录当前结点：
parent = cur;
最后：
cur 指向空位置
parent 指向空位置的父结点
再根据大小关系决定连接到父结点左边还是右边。
5.3 插入代码
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur != nullptr)
{
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
Node* newNode = new Node(key);
if (key < parent->_key)
{
parent->_left = newNode;
}
else
{
parent->_right = newNode;
}
return true;
}
5.4 根结点需要单独处理
如果树为空：
_root == nullptr
此时没有父结点，新结点本身就是根：
_root = new Node(key);
这是插入操作中的第一个边界情况。
5.5 插入顺序会影响树的形状
插入顺序：
8 3 1 10 6 4 7 14 13
可以得到一棵相对均匀的树：
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
如果按递增顺序插入：
1 3 4 6 7 8 10 13 14
树会退化成：
1
\
3
\
4
\
6
\
7
\
8
\
10
\
13
\
14
这棵树在结构上已经很像单链表。
因此：
二叉搜索树的形状不仅由数据决定，也由插入顺序决定。
六、删除：二叉搜索树中最复杂的操作
查找和插入都只需要沿着一条路径向下走。
删除不仅要找到目标，还要在删除后保持二叉搜索树的结构，因此情况更多。
假设要删除的结点为 N，可以根据孩子数量进行分类。
6.1 情况一：删除叶子结点
叶子结点没有左右孩子：
parent
|
N
/ \
nullptr nullptr
删除时，只需要让父结点对应的孩子指针指向空：
parent 的孩子指针 = nullptr
delete N
例如删除 1：
删除前：
3
/
1
删除后：
3
叶子结点也可以统一看成“只有零个有效孩子”的单孩子情况。
6.2 情况二：只有右孩子
例如删除 10：
10
\
14
删除后，应当让 10 的父结点直接连接 14：
parent
\
14
也就是：
parent 的孩子指针 = cur->_right;
delete cur;
6.3 情况三：只有左孩子
例如：
14
/
13
删除 14 后，让它的父结点直接连接 13：
parent 的孩子指针 = cur->_left;
delete cur;
情况一、二、三可以合并为：
删除拥有零个或一个孩子的结点
统一处理方式是：
Node* child = cur->_left != nullptr
? cur->_left
: cur->_right;
然后让父结点连接 child。
如果两个孩子都为空，child 自然就是 nullptr。
6.4 删除的是根结点怎么办？
如果：
parent == nullptr
说明当前删除的结点就是根结点。
此时不能修改父结点，因为根本没有父结点。
应当直接修改：
_root
例如根只有右孩子：
_root = cur->_right;
根只有左孩子：
_root = cur->_left;
删除代码中，这是非常容易遗漏的边界情况。
6.5 情况四：左右孩子都存在
假设要删除 8：
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
不能直接把 8 删除，因为：
左子树和右子树都失去了连接位置
这时通常采用替换法。
可以选择：
左子树中的最大结点：前驱
或者：
右子树中的最小结点：后继
本文选择右子树中的最小结点。
在 8 的右子树中：
10
\
14
/
13
最小结点是：
10
因为右子树最小结点就是不断向左走到尽头的位置。
将 10 的值复制到原来的 8：
原结点 8 改成 10
然后转而删除右子树中原来的 10。
6.6 为什么后继结点容易删除？
右子树中的最小结点不可能有左孩子。
如果它有左孩子，那么左孩子会比它更小，它就不是最小结点了。
所以后继结点只可能是：
叶子结点
或者只有右孩子
它最终会退化成前面已经解决的零孩子或单孩子删除。
这就是替换法的核心：
把复杂的双孩子删除，转化为简单的零孩子或单孩子删除。
七、删除代码逐步实现
7.1 先找到目标结点和父结点
Node* parent = nullptr;
Node* cur = _root;
while (cur != nullptr)
{
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else
{
break;
}
}
如果循环结束后：
cur == nullptr
说明目标不存在：
return false;
7.2 处理零个或一个孩子
if (cur->_left == nullptr || cur->_right == nullptr)
{
Node* child = cur->_left != nullptr
? cur->_left
: cur->_right;
if (parent == nullptr)
{
_root = child;
}
else if (parent->_left == cur)
{
parent->_left = child;
}
else
{
parent->_right = child;
}
delete cur;
return true;
}
这一段同时覆盖：
叶子结点
只有左孩子
只有右孩子
删除根结点且根至多只有一个孩子
7.3 处理两个孩子
Node* successorParent = cur;
Node* successor = cur->_right;
while (successor->_left != nullptr)
{
successorParent = successor;
successor = successor->_left;
}
此时：
successor 指向右子树最小结点
successorParent 指向它的父结点
用后继值覆盖待删除结点：
cur->_key = successor->_key;
再删除后继结点：
if (successorParent->_left == successor)
{
successorParent->_left = successor->_right;
}
else
{
successorParent->_right = successor->_right;
}
delete successor;
return true;
为什么连接的是：
successor->_right
因为后继结点不可能有左孩子，但可能有右孩子。
7.4 右孩子本身就是后继的特殊情况
例如删除：
8
\
10
8 的右子树最小值就是右孩子 10 本身。
初始化时必须写：
Node* successorParent = cur;
Node* successor = cur->_right;
这样没有进入 while 循环时：
successorParent 仍然是待删除结点 cur
successor 是 cur 的右孩子
后面才能正确执行：
successorParent->_right = successor->_right;
如果错误地把：
successorParent
初始化为空，或者初始化成不正确的位置，这种边界情况就很容易出错。
八、一个完整的二叉搜索树实现
下面实现一个不允许重复关键字的二叉搜索树。
除了插入、查找、删除和中序遍历，还补充：
析构函数
深拷贝
拷贝赋值
移动构造
自定义比较器
完整代码如下：
#include <functional>
#include <iostream>
#include <utility>
template<class K, class Compare = std::less<K>>
class BSTree
{
private:
struct Node
{
K _key;
Node* _left;
Node* _right;
explicit Node(const K& key)
: _key(key)
, _left(nullptr)
, _right(nullptr)
{
}
};
public:
BSTree() = default;
BSTree(const BSTree& other)
: _root(Copy(other._root))
, _compare(other._compare)
{
}
BSTree(BSTree&& other) noexcept
: _root(other._root)
, _compare(std::move(other._compare))
{
other._root = nullptr;
}
BSTree& operator=(BSTree other)
{
Swap(other);
return *this;
}
~BSTree()
{
Destroy(_root);
_root = nullptr;
}
void Swap(BSTree& other)
{
using std::swap;
swap(_root, other._root);
swap(_compare, other._compare);
}
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur != nullptr)
{
if (_compare(key, cur->_key))
{
parent = cur;
cur = cur->_left;
}
else if (_compare(cur->_key, key))
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
Node* newNode = new Node(key);
if (_compare(key, parent->_key))
{
parent->_left = newNode;
}
else
{
parent->_right = newNode;
}
return true;
}
bool Contains(const K& key) const
{
const Node* cur = _root;
while (cur != nullptr)
{
if (_compare(key, cur->_key))
{
cur = cur->_left;
}
else if (_compare(cur->_key, key))
{
cur = cur->_right;
}
else
{
return true;
}
}
return false;
}
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur != nullptr)
{
if (_compare(key, cur->_key))
{
parent = cur;
cur = cur->_left;
}
else if (_compare(cur->_key, key))
{
parent = cur;
cur = cur->_right;
}
else
{
break;
}
}
if (cur == nullptr)
{
return false;
}
// 零个或一个孩子
if (cur->_left == nullptr || cur->_right == nullptr)
{
Node* child = cur->_left != nullptr
? cur->_left
: cur->_right;
if (parent == nullptr)
{
_root = child;
}
else if (parent->_left == cur)
{
parent->_left = child;
}
else
{
parent->_right = child;
}
delete cur;
return true;
}
// 两个孩子：寻找右子树最小结点
Node* successorParent = cur;
Node* successor = cur->_right;
while (successor->_left != nullptr)
{
successorParent = successor;
successor = successor->_left;
}
cur->_key = successor->_key;
if (successorParent->_left == successor)
{
successorParent->_left = successor->_right;
}
else
{
successorParent->_right = successor->_right;
}
delete successor;
return true;
}
void InOrder(std::ostream& out = std::cout) const
{
InOrder(_root, out);
out << '\n';
}
bool Empty() const
{
return _root == nullptr;
}
private:
static void InOrder(const Node* root, std::ostream& out)
{
if (root == nullptr)
{
return;
}
InOrder(root->_left, out);
out << root->_key << ' ';
InOrder(root->_right, out);
}
static void Destroy(Node* root)
{
if (root == nullptr)
{
return;
}
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
static Node* Copy(const Node* root)
{
if (root == nullptr)
{
return nullptr;
}
Node* newRoot = new Node(root->_key);
try
{
newRoot->_left = Copy(root->_left);
newRoot->_right = Copy(root->_right);
}
catch (...)
{
Destroy(newRoot);
throw;
}
return newRoot;
}
private:
Node* _root = nullptr;
Compare _compare;
};
九、为什么析构要使用后序遍历？
9.1 错误的释放顺序
如果先删除根结点：
delete root;
然后再访问：
root->_left
root->_right
这时 root 已经成为悬空指针，继续访问会产生未定义行为。
9.2 正确释放顺序
应该先释放左右子树，再释放根：
左子树
右子树
根结点
这正好是后序遍历。
static void Destroy(Node* root)
{
if (root == nullptr)
{
return;
}
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
可以把它理解为拆房子：
先拆上层结构
再拆最下面的支撑点
如果先把根结点删除，就无法再通过它找到左右子树。
十、为什么二叉搜索树需要深拷贝？
10.1 默认拷贝的问题
BSTree 中保存了一个指针：
Node* _root;
如果直接使用编译器生成的默认拷贝：
BSTree<int> tree2 = tree1;
默认行为只会复制 _root 指针的地址。
结果是：
tree1._root ─┐
├── 指向同一棵树
tree2._root ─┘
这属于浅拷贝。
后果包括：
修改一棵树可能影响另一棵树
一棵树析构后，另一棵树留下悬空指针
两个对象析构时重复释放同一批结点
10.2 深拷贝的思路
深拷贝要重新创建所有结点：
static Node* Copy(const Node* root)
{
if (root == nullptr)
{
return nullptr;
}
Node* newRoot = new Node(root->_key);
newRoot->_left = Copy(root->_left);
newRoot->_right = Copy(root->_right);
return newRoot;
}
它的递归结构是：
复制当前根
复制左子树
复制右子树
最终两棵树的结构和数据相同，但内存完全独立。
tree1 → 原树
tree2 → 新树
10.3 copy-and-swap 赋值
赋值运算符写成：
BSTree& operator=(BSTree other)
{
Swap(other);
return *this;
}
参数 other 是传值对象，进入函数前已经完成拷贝。
函数中交换两棵树的资源：
Swap(other);
函数结束时，other 析构，自动释放当前对象原来的旧资源。
这种写法将：
拷贝
旧资源释放
自赋值处理
统一交给构造函数、交换函数和析构函数完成，代码比较简洁。
十一、为什么使用 Compare，而不是直接写小于号？
前面的基础版本可以直接写：
key < cur->_key
但模板类型不一定使用默认升序，也不一定直接支持 <。
所以完整实现中使用比较器：
Compare _compare;
默认类型是：
std::less<K>
判断 key 是否更小：
_compare(key, cur->_key)
判断当前结点是否更小：
_compare(cur->_key, key)
如果两次比较都为假：
!_compare(key, cur->_key)
&&
!_compare(cur->_key, key)
说明两个关键字在当前比较规则下等价。
这种写法也对应有序关联容器常见的比较方式。
11.1 自定义降序比较器
struct Greater
{
bool operator()(int left, int right) const
{
return left > right;
}
};
使用：
BSTree<int, Greater> tree;
这时树的方向会与默认升序规则相反，但只要所有操作都使用同一个比较器，结构仍然是自洽的。
十二、测试完整代码
int main()
{
BSTree<int> tree;
int values[] = {
8, 3, 1, 10, 6, 4, 7, 14, 13
};
for (int value : values)
{
tree.Insert(value);
}
cout << "中序遍历：";
tree.InOrder();
cout << boolalpha;
cout << "查找 7：" << tree.Contains(7) << '\n';
cout << "查找 12：" << tree.Contains(12) << '\n';
tree.Erase(1); // 删除叶子
tree.Erase(14); // 删除只有一个孩子的结点
tree.Erase(3); // 删除有两个孩子的结点
tree.Erase(8); // 删除根结点
cout << "删除后：";
tree.InOrder();
BSTree<int> copy = tree;
cout << "拷贝结果：";
copy.InOrder();
return 0;
}
可能的输出：
中序遍历：1 3 4 6 7 8 10 13 14
查找 7：true
查找 12：false
删除后：4 6 7 10 13
拷贝结果：4 6 7 10 13
在 Linux 环境中，可以使用：
g++ -std=c++17 -Wall -Wextra -pedantic bst.cpp -o bst
./bst
建议同时打开 AddressSanitizer 检查内存问题：
g++ -std=c++17 \
-Wall -Wextra -pedantic \
-fsanitize=address,undefined \
-g bst.cpp -o bst
./bst
它可以帮助发现：
重复释放
越界访问
释放后继续使用
部分未定义行为
十三、key 模型：只关心一个值是否存在
13.1 什么是 key 模型？
有些场景只需要判断某个关键字在不在集合中。
结点只需要保存：
K _key;
例如：
车牌号是否属于本小区
单词是否在词典中
用户 ID 是否已经注册
黑名单中是否存在某个账号
查找结果通常只是：
存在
不存在
这种结构对应的是 key 搜索场景。
13.2 为什么不能直接修改 key？
假设原来有：
8
/
3
如果直接把 3 修改成 10：
8
/
10
此时 10 位于 8 的左边，破坏了二叉搜索树规则。
所以关键字通常不能直接修改。
如果确实要修改，应当执行：
删除旧 key
插入新 key
而不是在原位置直接赋值。
十四、key/value 模型：通过 key 查找对应信息
14.1 从集合升级为映射
有些场景不仅要知道 key 是否存在，还需要找到 key 对应的数据。
例如中英词典：
left → 左边
right → 右边
insert → 插入
string → 字符串
此时一个结点需要保存：
key
value
left
right
可以定义为：
template<class K, class V>
struct BSTMapNode
{
K _key;
V _value;
BSTMapNode<K, V>* _left;
BSTMapNode<K, V>* _right;
BSTMapNode(const K& key, const V& value)
: _key(key)
, _value(value)
, _left(nullptr)
, _right(nullptr)
{
}
};
14.2 树的顺序由谁决定？
即使结点中同时有 key 和 value，树的结构仍然只由 key 决定。
比较时使用：
cur->_key
而不是：
cur->_value
因此：
key 决定结点放在树中的位置
value 只是与 key 关联的数据
14.3 key 不能改，value 可以改
修改 key 可能破坏树的顺序。
修改 value 不会改变结点位置。
例如：
apple → 苹果
可以修改为：
apple → 苹果；苹果公司
结点仍然按照 apple 这个 key 存放，所以树结构不会受到影响。
十五、key/value 的查找接口应该返回什么？
对于 key 模型，查找只需要返回：
bool
对于 key/value 模型，只返回真假往往不够，因为调用者还需要访问对应的 value。
可以让查找函数返回 value 的指针：
V* Find(const K& key)
{
Node* cur = _root;
while (cur != nullptr)
{
if (key < cur->_key)
{
cur = cur->_left;
}
else if (key > cur->_key)
{
cur = cur->_right;
}
else
{
return &cur->_value;
}
}
return nullptr;
}
常量版本：
const V* Find(const K& key) const
{
const Node* cur = _root;
while (cur != nullptr)
{
if (key < cur->_key)
{
cur = cur->_left;
}
else if (key > cur->_key)
{
cur = cur->_right;
}
else
{
return &cur->_value;
}
}
return nullptr;
}
这样：
返回 nullptr：key 不存在
返回有效指针：可以读取或修改对应 value
十六、应用一：简单中英词典
BSTreeMap<string, string> dictionary;
dictionary.Insert("left", "左边");
dictionary.Insert("right", "右边");
dictionary.Insert("insert", "插入");
dictionary.Insert("string", "字符串");
查询：
string word;
while (cin >> word)
{
const string* translation = dictionary.Find(word);
if (translation != nullptr)
{
cout << word << " -> "
<< *translation << '\n';
}
else
{
cout << "未找到该单词\n";
}
}
这里的搜索过程是：
输入英文单词
→ 按 key 在树中查找
→ 找到结点
→ 读取对应中文 value
十七、应用二：统计单词出现次数
假设有一组水果名称：
string words[] = {
"苹果", "西瓜", "苹果",
"西瓜", "苹果", "香蕉",
"苹果", "香蕉"
};
用：
水果名称作为 key
出现次数作为 value
处理逻辑：
第一次出现：
插入 <水果, 1>
已经存在：
对应次数加 1
示例：
for (const string& word : words)
{
int* count = countTree.Find(word);
if (count == nullptr)
{
countTree.Insert(word, 1);
}
else
{
++(*count);
}
}
最终可能得到：
苹果：4
西瓜：2
香蕉：2
这个过程也是有序关联容器中常见的词频统计模型。
十八、二叉搜索树的性能分析
18.1 所有核心操作都依赖树高
二叉搜索树中的：
查找
插入
删除
查找最小值
查找最大值
本质上都是从某个结点沿着一条路径向下移动。
所以它们的时间复杂度都可以统一写成：
O(h)
其中 h 是树高。
18.2 接近平衡时
如果每一层的结点数量比较均匀：
●
/ \
● ●
/ \ / \
● ● ● ●
树高大约为：
log₂N
操作效率为：
O(log N)
18.3 退化时
如果按有序顺序插入：
1 2 3 4 5
可能形成：
1
\
2
\
3
\
4
\
5
树高变成：
N
操作效率退化为：
O(N)
18.4 不能笼统说 BST 一定是 O(log N)
普通二叉搜索树不保证平衡。
所以更准确的说法是：
查找、插入、删除：O(h)
接近平衡：O(log N)
最坏退化：O(N)
直接说：
二叉搜索树查找一定是 O(log N)
是不严谨的。
十九、二分查找和二叉搜索树有什么区别？
二分查找和二叉搜索树都利用了有序性，但使用场景不同。
19.1 二分查找
二分查找通常工作在支持随机访问的有序结构中，例如：
vector<int>
array<int, N>
查找复杂度为：
O(log N)
但在数组中间插入或删除元素时，通常需要搬移后面的数据：
插入和删除：O(N)
19.2 二叉搜索树
二叉搜索树中的结点通过指针连接。
找到目标位置后，插入或删除主要通过修改指针完成。
操作复杂度为：
O(h)
平衡时接近：
O(log N)
退化时是：
O(N)
19.3 简单对比
| 对比项 | 有序数组加二分查找 | 普通二叉搜索树 |
|---|---|---|
| 查找 | O(log N) | O(h) |
| 中间插入 | O(N) | O(h) |
| 删除 | O(N) | O(h) |
| 是否连续存储 | 是 | 否 |
| 是否需要随机访问 | 是 | 否 |
| 最坏查找 | O(log N) | O(N) |
| 内存局部性 | 较好 | 通常较弱 |
如果数据几乎不修改，只进行大量查询，有序数组可能很合适。
如果数据需要动态插入和删除，平衡搜索树更有优势。
二十、为什么还要学习 AVL 树和红黑树？
普通二叉搜索树最大的缺点是：
无法保证树高
一旦树退化成单支结构，性能就从：
O(log N)
下降到：
O(N)
平衡搜索树会在插入和删除后，通过旋转、颜色或高度规则控制树高。
常见结构包括：
AVL 树
红黑树
伸展树
B 树和 B+ 树
其中：
AVL 树：对高度平衡要求更严格
红黑树：通过颜色规则维持近似平衡
这些结构的共同目标是：
避免二叉搜索树退化，尽量把树高控制在对数级别。
二叉搜索树是这些平衡树的基础。
如果连普通 BST 的插入、查找和删除都没有理解，后面学习旋转和平衡调整时会比较吃力。
二十三、把所有知识点串起来
现在从最底层重新看一遍二叉搜索树。
23.1 从结点开始
每个结点保存：
key
left
right
指针把结点组织成二叉树。
23.2 加入有序规则
规定：
左边小
右边大
并且左右子树继续遵循相同规则。
普通二叉树由此变成二叉搜索树。
23.3 有序规则形成定向查找
查找一个 key 时：
比当前值小 → 向左
比当前值大 → 向右
相等 → 找到
每次比较只保留一个可能方向。
23.4 查找失败的位置成为插入位置
插入其实就是一次没有找到目标的查找。
走到空位置后，创建新结点并连接到父结点。
23.5 删除必须维护原有规则
零个或一个孩子时，父结点可以直接跨过被删除结点连接它的孩子。
两个孩子时，不能直接删除，需要使用前驱或后继替换。
23.6 有序结构带来中序有序
因为：
左子树 < 根 < 右子树
所以按照：
左 → 根 → 右
访问时，会自然得到有序序列。
23.7 所有操作都受树高控制
查找、插入和删除都只沿一条路径进行：
复杂度为 O(h)
所以：
树越矮，操作越快
树越高，操作越慢
23.8 普通 BST 引出平衡树
普通 BST 不会自动控制高度。
因此需要 AVL 树、红黑树等结构，在保留搜索树有序规则的同时，尽量维持较低高度。
最终完整知识链是：
二叉树结点
↓
左右孩子指针
↓
左小右大的局部规则
↓
递归形成全局有序结构
↓
定向查找
↓
在查找失败处插入
↓
通过指针调整完成删除
↓
中序遍历得到有序序列
↓
操作复杂度取决于树高
↓
普通 BST 可能退化
↓
AVL 树与红黑树维持平衡
↓
支撑更稳定的有序关联结构
这就是从一个结点出发，逐步构建出的二叉搜索树知识体系。
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
13
0- 0
已为社区贡献27条内容
所有评论(0)