【C++】二叉搜索树从入门到手写代码：一篇搞懂 map/set 底层原理-171主机测评

文章目录

前言
一、二叉搜索树是什么？
二、性能分析
- 1、最优情况：完全二叉树
- 2、最差情况：单支树
- 3、二叉搜索树 VS 二分查找
三、插入操作
四、查找操作
五、删除操作（重点 + 难点）
- 情况 1：要删的结点左右孩子都空
- 情况 2：要删的结点左空、右孩子不空
- 情况 3：要删的结点右空、左孩子不空
- 情况 4：要删的结点左右孩子都不空
- 删除代码实现：
六、完整代码实现（key 版本）
七、两种应用场景：key 搜索 vs key/value 搜索
- 1、纯 key 搜索场景
- 2、key/value 搜索场景
- 3、key/value 版本代码
总结

前言

学数据结构，二叉搜索树绝对是绕不开的经典。它既有链表插入删除方便的优点，又有接近二分查找的速度，后面我们要学的map、set这些 STL 容器，底层就是二叉搜索树（准确说是平衡二叉搜索树）。

本篇文章从二叉搜索树是什么、性质、插入查找删除操作，到完整代码实现，再到 key 和 key/value 两种应用场景进行教学，帮助大家手搓二叉搜索树。

一、二叉搜索树是什么？

二叉搜索树（Binary Search Tree，也叫二叉排序树），要么是空树，要么满足下面三条性质：

如果左子树不为空，左子树上所有结点的值都 ≤ 根结点的值

如果右子树不为空，右子树上所有结点的值都 ≥ 根结点的值

左右子树本身也分别是二叉搜索树

简单说就是：左小右大。在这里插入图片描述这就是一棵标准的二叉搜索树。根是 9，左边都比 9 小，右边都比 9 大；每个子树也都符合这个规则。

补充：二叉搜索树可以支持相等的值，也可以不支持，看具体需求。

二、性能分析

二叉搜索树的效率跟树的形状关系很大。

1、最优情况：完全二叉树

当树接近完全二叉树的时候，高度大概是 log₂N。增删查改的时间复杂度都是 O(log N)，效率很高。

2、最差情况：单支树

如果插入的数据本来就是有序的，树就退化成一条链表（单支树），高度就是 N。如下图在这里插入图片描述时间复杂度直接变成 O(N)，跟遍历差不多了。

所以单纯的二叉搜索树其实不稳定，最坏情况效率拉胯。后面才有了平衡二叉搜索树（AVL 树、红黑树），通过旋转让树尽量保持平衡，稳定在 O (logN)。

3、二叉搜索树 VS 二分查找

二分查找也是 O (logN) 的查找效率，但二分查找有两个硬伤：

必须存在支持随机访问的结构里（比如数组），而且必须有序

插入删除效率很低，要挪动大量数据

二叉搜索树就平衡了查找和插入删除的效率，这也是它的价值所在。

三、插入操作

插入的逻辑很简单，核心就是：大了往右走，小了往左走，找到空位就插入。

具体步骤：

树是空的 → 直接新建结点作为根

树不空 → 从根开始比

插入值 > 当前结点值 → 往右走
插入值 < 当前结点值 → 往左走

走到空位置了 → 新建结点插进去

如果支持插入相等的值，统一往左或者往右都行，但要保持一致，别一会左一会右。

插入代码实现：

template<class K>
struct BSTNode
{
K _key; // 键值
BSTNode<K>* _left; // 左孩子
BSTNode<K>* _right; // 右孩子

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

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

public:
// 构造
BSTree()
: _root(nullptr)
{
}

// 插入
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;
}
private:
Node* _root = nullptr;
};

四、查找操作

查找跟插入思路差不多：

从根结点开始比较

要找的值 > 当前结点 → 往右

要找的值 < 当前结点 → 往左

相等 → 找到了，返回 true

走到空了还没找到 → 不存在，返回 false

最多找高度次，所以最优 O (logN)，最差 O (N)。

如果支持重复值，一般要求找到中序第一个出现的那个。

查找代码实现：

// 查找
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;
}

五、删除操作（重点 + 难点）

删除是二叉搜索树最复杂的操作，因为要分情况处理。

首先先找到要删的结点，找不到直接返回 false。找到了分四种情况：

情况 1：要删的结点左右孩子都空

最简单的情况：直接把父结点对应指针置空，然后删掉这个结点就行。在这里插入图片描述

比如删上图里的1，它没孩子，直接删掉，3 的左指针置空。

情况 2：要删的结点左空、右孩子不空

父结点的对应指针直接指向这个结点的右孩子，然后删掉它。在这里插入图片描述

比如删10，它只有右孩子 14，直接让 9 的右指针指向 14，删掉 10。

情况 3：要删的结点右空、左孩子不空

跟情况 2 反过来：父结点对应指针指向它的左孩子，删掉它。在这里插入图片描述

比如删14，它只有左孩子 12，让 10 的右指针指向 12，删掉 14。

情况 1 其实可以当成情况 2 或 3 的特例处理，代码里不用单独写。

情况 4：要删的结点左右孩子都不空

这是最麻烦的情况，不能直接删 —— 删了两个孩子没地方放。这时候用替换法。在这里插入图片描述

做法：

找这个结点右子树里最小的结点（或者左子树最大的结点也行）

把这个最小结点的值，替换到要删的结点上

删掉那个最小的结点

为啥找右子树最小？因为右子树最小的那个，放到当前位置，依然满足 “左小右大” 的规则。而且那个最小结点肯定没有左孩子（不然就不是最小了），所以删它的时候属于情况 2，直接删就行。

比如删根结点9：

找右子树（10 那棵）最小的，是 10

把 9 的值换成 10

删掉原来的 10 结点

效果就像这样在这里插入图片描述这样就完成了删除，树依然符合二叉搜索树规则。

删除代码实现：

// 删除
bool Erase(const K& key) {
// 找到要删除的位置
Node* cur = _root;
Node* parent = nullptr;
while (cur) {
if (cur->_key < key) {
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key) {
parent = cur;
cur = cur->_left;
}
// 相等
else {
// 判断各种情况：
// 1.cur左孩子为空
if (cur->_left == nullptr) {
// 特殊情况：cur==_root
if (cur == _root) {
_root = cur->_right;
}
else {
if (parent->_left == cur) {
parent->_left = cur->_right;
}
else {
parent->_right = cur->_right;
}
}
delete cur;
}
// 2.cur右孩子为空
else if (cur->_right == nullptr) {
// 特殊情况：cur==_root
if (cur == _root) {
_root = cur->_left;
}
else {
if (parent->_left == cur) {
parent->_left = cur->_left;
}
else {
parent->_right = cur->_left;
}
}
delete cur;
}
// 3.cur左右孩子都不为空，交换左边孩子最大节点或者右边孩子最小节点
else {
// 取右边孩子最小节点
Node* replace = cur->_right;
Node* replaceParent = cur;
while (replace->_left) {
replaceParent = replace;
replace = replace->_left;
}
// 此时replace是最小节点，赋值
cur->_key = replace->_key;
// 替换节点的父亲接上replace的右子节点
if (replaceParent->_left == replace) {
replaceParent->_left = replace->_right;
}
else {
//特例：replaceParent就是cur（cur‑>right没有左孩子）
replaceParent->_right = replace->_right;
}
delete replace;
}
return true;
}
}
return false;
}

六、完整代码实现（key 版本）

下面我们写一个完整的二叉搜索树，用模板实现，支持不同类型的 key。

#include <iostream>
using namespace std;

// 结点结构体
template<class K>
struct BSTNode
{
K _key; // 键值
BSTNode<K>* _left; // 左孩子
BSTNode<K>* _right; // 右孩子

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

// 二叉树搜索类
template<class K>
class BSTree
{
typedef BSTNode<K> Node;

public:
// 构造
BSTree()
: _root(nullptr)
{
}

// 拷贝构造
BSTree(const BSTree<K>& t) {
_root = Copy(t._root);
}

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

// 析构
~BSTree() {
Destroy(_root);
}

// 插入
bool Insert(const K& key) {
// 如果二叉树还没有根
if (_root == nullptr) {
_root = new Node(key);
return true;
}
// 有根
Node* parent = nullptr;// cur的父节点
Node* cur = _root;// 从根节点开始
// 循环查找，直到cur为空
while (cur) {
// cur的值比key小，继续查右孩子
if (cur->_key < key) {
parent = cur;
cur = cur->_right;
}
// cur的值比key大，继续查左孩子
else if (cur->_key > key) {
parent = cur;
cur = cur->_left;
}
// 如果cur的值与key相等，就不插入key
else {
return false;
}
}
// 循环结束，此时cur为空，parent是cur的父节点
// 创建节点，存入key，连接父节点
cur = new Node(key);
// parent的_key比key小，cur存入右孩子
if (parent->_key < key) {
parent->_right = cur;
}
// parent的_key比key大，cur存入左孩子
else {
parent->_left = cur;
}
return true;
}

// 中序遍历
void InOrder() {
_InOrder(_root);// 调用私有的_InOrder
cout << endl;
}
private:
// 拷贝采用前序递归
Node* Copy(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;
}

// 析构采用后序递归
void Destroy(Node* root) {
if (root == nullptr) {
return;
}
// 左
Destroy(root->_left);
// 右
Destroy(root->_right);
// 根
delete root;
return;
}

// 遍历采用中序遍历
void _InOrder(Node* root) {
if (root == nullptr) {
return;
}
// 左
_InOrder(root->_left);
// 根
cout << root->_key << " ";
// 右
_InOrder(root->_right);
}

Node* _root = nullptr;
};

中序遍历二叉搜索树，输出就是升序的，这也是 “二叉排序树” 名字的由来。

七、两种应用场景：key 搜索 vs key/value 搜索

1、纯 key 搜索场景

结构里只存 key，作用就是判断 “在不在”。

例子 1：小区车牌识别把买了车位的车牌号存进树里，车辆进来扫车牌，查得到就抬杆，查不到就不让进。

例子 2：单词拼写检查把正确单词存进树里，文章里的单词挨个查，不在就标红提示拼写错误。

2、key/value 搜索场景

结点结构体除了有key，还有value。每个 key 对应一个 value，结点里既要存 key 也要存 value。增删查还是按 key 来，但能快速拿到对应的 value。

例子 1：英汉词典 key 是英文，value 是中文。输入英文，直接查出中文意思。

例子 2：停车场计时收费 key 是车牌号，value 是入场时间。出场扫车牌，查到入场时间，算时长算费用。

例子 3：单词计数 key 是单词，value 是出现次数。读到一个单词，不存在就插入 <单词，1>，存在就次数 + 1。

3、key/value 版本代码

#include <iostream>
using namespace std;

// 结点结构体
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()
: _root(nullptr)
{
}

// 拷贝构造
BSTree(const BSTree<K, V>& t) {
_root = Copy(t._root);
}

// 赋值重载
BSTree<K, V>& operator=(BSTree<K, V> t) {
swap(_root, t._root);
return *this;
}

// 析构
~BSTree() {
Destroy(_root);
}

// 插入
bool Insert(const K& key, const V& value) {
// 如果二叉树还没有根
if (_root == nullptr) {
_root = new Node(key, value);
return true;
}
// 有根
Node* parent = nullptr;// cur的父节点
Node* cur = _root;// 从根节点开始
// 循环查找，直到cur为空
while (cur) {
// cur的值比key小，继续查右孩子
if (cur->_key < key) {
parent = cur;
cur = cur->_right;
}
// cur的值比key大，继续查左孩子
else if (cur->_key > key) {
parent = cur;
cur = cur->_left;
}
// 如果cur的值与key相等，就不插入key
else {
return false;
}
}
// 循环结束，此时cur为空，parent是cur的父节点
// 创建节点，存入key，连接父节点
cur = new Node(key, value);
// parent的_key比key小，cur存入右孩子
if (parent->_key < key) {
parent->_right = cur;
}
// parent的_key比key大，cur存入左孩子
else {
parent->_left = cur;
}
return true;
}

// 查找
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;
}

// 中序遍历
void InOrder() {
_InOrder(_root);// 调用私有的_InOrder
cout << endl;
}
private:
// 拷贝采用前序递归
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;
}

// 析构采用后序递归
void Destroy(Node* root) {
if (root == nullptr) {
return;
}
// 左
Destroy(root->_left);
// 右
Destroy(root->_right);
// 根
delete root;
return;
}

// 遍历采用中序遍历
void _InOrder(Node* root) {
if (root == nullptr) {
return;
}
// 左
_InOrder(root->_left);
// 根
cout << root->_key << "：" << root->_value << endl;
// 右
_InOrder(root->_right);
}

Node* _root = nullptr;
};

总结

普通二叉搜索树虽然简单，但最坏情况效率太差，所以实际工业界用的都是平衡二叉搜索树，比如红黑树。后面我们讲 map、set 的时候，再深入聊平衡树和红黑树。

如果这篇文章对你有帮助，点个赞收藏一下，后续持续更新数据结构与 STL 系列～

【C++】二叉搜索树从入门到手写代码：一篇搞懂 map/set 底层原理

文章目录

前言

一、二叉搜索树是什么？