1. 二叉搜索树的概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
- 若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值
- 若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值
- 它的左右子树也分别为二叉搜索树
- 二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义，后续我们学习map/set/multimap/multiset 系列容器底层就是二叉搜索树，其中 map/set 不支持插入相等值，multimap/multiset 支持插入相等值
2. 二叉搜索树的性能分析
最优情况下，二叉搜索树为完全二叉树 (或者接近完全二叉树)，其高度为：log2 N 最差情况下，二叉搜索树退化为单支树 (或者类似单支)，其高度为：N
所以综合而言二叉搜索树增删查改时间复杂度为：O(N)
因此单纯的二叉搜索树的效率不能满足我们的要求，后续二叉搜索树的变形比如平衡搜索二叉树即 AVLTree，红黑树 RBTree，他们由于一些特殊的设计使得二叉搜索树的效率接近 log2N
我们都知道有一个二分查找的算法可以快速帮我查询数据，其时间复杂度为 logN。那么大家是否有一个疑问为什么有了该算法后又要设计出搜索二叉树这种数据结构呢？
二分查找的缺陷:
需要存储在支持下标随机访问的结构中，并且有序。比如有序数组****插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。
正是二分查找的缺陷体现了二叉搜索树的价值
最优二叉搜索树的大概情况：
最差二叉搜索树的大概情况：
3. 二叉搜索树的插入
插入的过程：
树为空，则直接新增结点，赋值给 root 指针 树不空，按二叉搜索树性质，插入值比当前结点大往右走，插入值比当前结点小往左走，找到空位置，插入新结点。 如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑一致性，插入相等的值不要一会往右走，一会往左走）,具体设计自己决定
int a[]={8,3,1,10,6,4,7,14,13};
有这些数据的二叉搜索树：
此时再插入 16
此时再插入 13
4. 二叉搜索树的查找
从根开始比较，查找 x，x 比根的值大则往右边查找，x 比根值小则往左边查找最多查找高度次，走到到空，还没找到，这个值不存在。 如果不支持插入相等的值，找到 x 即可返回 如果支持插入相等的值，意味着有多个 x 存在，一般要求查找中序的第一个 x。 如下图，查找 3，要找到 1 的右孩子的那个 3
返回前序：根左右 中序：左根右 后序：左右根
5. 二叉搜索树的删除
过程： 首先查找元素是否在二叉搜索树中，如果不存在，则返回 false 如果查找元素存在则分以下四种情况分别处理：（假设要删除的结点为 N）
要删除结点 N 左右孩子均为空 要删除的结点 N 左孩子位空，右孩子结点不为空 要删除的结点 N 右孩子位空，左孩子结点不为空 要删除的结点 N 左右孩子结点均不为空
但其实在代码实现上可以划分为两种情况：
没有孩子和只有一个孩子视为一种情况 因为可以将没有孩子视作只有一个孩子，只不过这个孩子是 nullptr 罢了 有两个孩子
以下是具体的解决方案：
第一种情况：以只有右孩子为例子，把 N 结点的父亲对应孩子指针指向 N 的右孩子，直接删除 N 结点 没有孩子时 N 结点的父亲对应孩子的指针指向 nullptr 符合逻辑 第二种情况：无法直接删除 N 结点，因为 N 的两个孩子无处安放，只能用替换法删除。 找N 左子树的值最大结点 R(最右结点) 或者 N 右子树的值最小结点 R(最左结点) 替代 N，因为这两个结点中任意一个，放到 N 的位置，都满足二叉搜索树的规则。 替代 N 的意思就是 N 和 R 的两个结点的值交换，转而变成删除 R 结点
手绘图举例
6. 二叉搜索树 key 和 key/value 使用场景
6.1 key 搜索场景：
只有 key 作为关键码，结构中只需要存储 key 即可，关键码即为需要搜索到的值，搜索场景只需要判断 key 在不在。key 的搜索场景实现的二叉树搜索树支持增删查，但是不支持修改，修改 key 破坏搜索树结构了。
简单举例：
车牌抬杆识别系统，判断车牌字符是否存在（后台将车牌号录入搜索二叉树） 检查一篇英文文章是否有错（词典录入二叉树） 编译器的语法检查（将库，自定义，关键词放入二叉树）
总之 key 的搜索二叉树一般用于快速查询数据是否存在
6.2 key/val 搜索场景
每一个关键码 key，都有与之对应的值 value，value 可以任意类型对象。树的结构中 (结点) 除了需要存储 key 还要存储对应的 value，增/删/查还是以 key 为关键字走二叉搜索树的规则进行比较，可以快速查找到 key 对应的 value。key/value 的搜索场景实现的二叉树搜索树支持修改，但是不支持修改 key，修改 key 破坏搜索树性质了，可以修改 value
简单举例：
检查中英文互译系统（key 即英文，value 即中文） 商场车库系统（收费自助类，通过存车票号，和入场时间计算租金） 读取一篇文章中英文出现的次数
7. 二叉搜索树的实现代码
7.1 key 模型代码实现
这里的 set 不是完全 set 的底层封装，本代码只是二叉搜索树 key 模型的实现代码
#pragma once
#include <assert.h>
#include <iostream>
using namespace std;
// 搜索二叉树 - >>>
// 简述：搜索二叉树：分为分为两种情况：
// 1. 左子树 和右子树 不等于根 即 该树里的所有值没有冗余
// 2. 左右子树可以等于根植 即该树中的值可以有相等的
// 总体 大小划分 左子树 < 根 < 右子树
// 平衡性概念：- >>>
// 搜索二叉树的结构一般用来增删查数据 最主要的是用来快速查询数据
// 查询遍历一般是 中序 为了降低极端情况下的树的时间复杂度 提出了平衡性的
// 概念 即 左右子树的高度绝对值不超过 1 这样就可以将中序遍历查找某个数据
// 的时间复杂度降到了 0 (logN)
// stl 中的 平衡搜索二叉树
// 根据应用场景 设计了两个适配器 set 和 map 底层是红黑树（平衡搜索二叉树）
// 去重 搜索二叉树的第一种
// set 适用 key 模型（单参数）
// map 使用 key / val 模型（双参数一般用类模板 pair 作为参数）
// 值可冗余 搜索二叉树的第二种
// multi set 适用 key 模型（单参数）
// multi map 使用 key / val 模型（双参数一般用类模板 pair 作为参数）
// eg: 字典
// 本文件 仅 set 和 map 的底层实现
// 主要实现 增删查的函数功能
// 本文件不是完全的封装实现 后续会更新 完全体的封装实现代码
#include <iostream>
using namespace std;
// 去重版 set
namespace twg {
// set -> ket 模型
// 搜索二叉树节点
template<class K>
struct BSTnode {
// 数据 K _key;
// 根值
BSTnode* left; // 左孩子
BSTnode* right; // 右孩子
// 构造
BSTnode(const K& key = K()) { _key = key; left = nullptr; right = nullptr; }
K _key;
};
// 单参数的去重搜索二叉树容器 -> set
template<class K>
class set {
typedef BSTnode<K> Node;
public:
// 增删查
// set and unoredered_set 不支持改（会破坏结构）
// 增 ---- stl 中的 set 参数是 pair 但本文件只是简单实现
bool Insert(const K& key) {
// 在二叉搜索树的规则下 查询 新加入的节点的位置
// 能循环 尽量不 递归 这里采用双指针循环的方法
// 判断是否为空树
if (_root == nullptr) {
// 新加入的节点为根节点
_root = new Node(key);
}
// 双指针 从根节点出发寻找合适位置
Node* cur = _root;
Node* parent = nullptr;
while (cur) {
if (key < cur->_key) {
// 该节点在 cur 的左子树处
parent = cur;
cur = cur->left;
} else if (key > cur->_key) {
// 该节点在 cur 的右子树处
parent = cur;
cur = cur->right;
} else {
// key == cur->_key 即相同节点 直接跳过
return true;
}
}
// 当 cur 为空时 即新节点的位置找到了
cur = new Node(key);
// 链接
// 判断子相对父的位置
if (parent->right == nullptr) {
// 链接
parent->right = cur;
} else {
parent->left = cur;
}
return true;
}
// 删
bool Erase(const K& key) {
// 查询当前数据在哪个地方
// 双指针 从根节点出发寻找合适位置
Node* cur = _root;
Node* parent = nullptr;
while (cur) {
if (key < cur->_key) {
// 该节点在 cur 的左子树处
parent = cur;
cur = cur->left;
} else if (key > cur->_key) {
// 该节点在 cur 的右子树处
parent = cur;
cur = cur->right;
} else {
// key == cur->_key 即相同节点 找到该位置
// 删除
// 根绝删除节点的孩子个数 执行不同的删除逻辑
// 0~1 个孩子的代码实现可以合并
// 即可以把 0 个孩子看成 1 个空孩子
// 假设只有右孩子
if (cur->left == nullptr) {
// 删除根节点
if (parent == nullptr) {
_root = cur->right;
}
// 删除局部节点
// 将 cur 的右孩子链接成为 parent 的孩子
if (parent->left == cur) {
parent->left = cur->right;
} else {
parent->right = cur->right;
}
delete cur; // 删除节点
cur = nullptr;
return true;
} else {
// 有两个孩子
// 替代法
// 这里以右子树的最小孩子替代 cur 为例
Node* rightMinf = cur;
Node* rightMin = cur->left;
// 最小孩子一定在右子树的最左节点处（不一定为叶子节点）
while (rightMin->left) {
rightMinf = rightMin;
rightMin = rightMin->left;
}
// 调整链接关系
// 调整 parent 的链接关系
if (parent->left == cur) {
parent->left = rightMin;
} else {
parent->right = rightMin;
}
// 调整 rightMinp 的链接关系
rightMinf->left = rightMin->right;
// rightMin 不一定为叶子节点
// 调整替换节点的父子链接关系
rightMin->left = cur->left;
rightMin->right = cur->right;
// 删除节点
delete cur;
cur = nullptr;
return true;
}
}
}
cout << "没有该节点" << endl;
return false;
}
// 查
bool Find(const K& key) {
// 双指针 从根节点出发寻找合适位置
Node* cur = _root;
Node* parent = nullptr;
while (cur) {
if (key < cur->_key) {
// 该节点在 cur 的左子树处
parent = cur;
cur = cur->left;
} else if (key > cur->_key) {
// 该节点在 cur 的右子树处
parent = cur;
cur = cur->right;
} else {
// key == cur->_key 即相同节点 直接跳过
return true;
}
}
// 没找到
return false;
}
void Inorder() {
assert(_root);
inorder(_root);
}
private:
// 中序遍历
void inorder(const Node* root) {
// 递归出口
if (root == nullptr)
return;
// 左根右
inorder(root->left); // 左子树
cout << root->_key << endl;
inorder(root->right);
}
Node* _root = nullptr; // 根节点
};
}
// 模拟 unordered_set 即不去重版
namespace Twg {
// set -> ket 模型
// 搜索二叉树节点
template<class K>
struct BSTnode {
// 数据 K _key;
// 根值
BSTnode* left; // 左孩子
BSTnode* right; // 右孩子
// 构造
BSTnode(const K& key = K()) { _key = key; left = nullptr; right = nullptr; }
K _key;
};
// 单参数的去重搜索二叉树容器 -> set
template<class K>
class set {
typedef BSTnode<K> Node;
public:
// 增删查
// set and unoredered_set 不支持改（会破坏结构）
// 增 ---- stl 中的 set 参数是 pair 但本文件只是简单实现
bool Insert(const K& key) {
// 在二叉搜索树的规则下 查询 新加入的节点的位置
// 能循环 尽量不 递归 这里采用双指针循环的方法
// 判断是否为空树
if (_root == nullptr) {
// 新加入的节点为根节点
_root = new Node(key);
return true;
}
// 双指针 从根节点出发寻找合适位置
Node* cur = _root;
Node* parent = nullptr;
while (cur) {
if (key <= cur->_key) {
// 该节点在 cur 的左子树处
parent = cur;
cur = cur->left;
} else if (key > cur->_key) {
// 该节点在 cur 的右子树处
parent = cur;
cur = cur->right;
}
}
// 当 cur 为空时 即新节点的位置找到了
cur = new Node(key);
// 链接
// 判断子相对父的位置
if (parent->right == nullptr) {
// 链接
parent->right = cur;
} else {
parent->left = cur;
}
return true;
}
// 删
bool Erase(const K& key) {
// 查询当前数据在哪个地方
// 双指针 从根节点出发寻找合适位置
Node* cur = _root;
Node* parent = nullptr;
while (cur) {
if (key < cur->_key) {
// 该节点在 cur 的左子树处
parent = cur;
cur = cur->left;
} else if (key > cur->_key) {
// 该节点在 cur 的右子树处
parent = cur;
cur = cur->right;
} else {
// key == cur->_key 即相同节点 找到该位置
// 删除
// 根绝删除节点的孩子个数 执行不同的删除逻辑
// 0~1 个孩子的代码实现可以合并
// 即可以把 0 个孩子看成 1 个空孩子
// 假设只有右孩子
if (cur->left == nullptr) {
// 删除根节点
if (parent == nullptr) {
_root = cur->right;
}
// 删除局部节点
// 将 cur 的右孩子链接成为 parent 的孩子
if (parent->left == cur) {
parent->left = cur->right;
} else {
parent->right = cur->right;
}
delete cur; // 删除节点
cur = nullptr;
return true;
} else {
// 有两个孩子
// 替代法
// 这里以右子树的最小孩子替代 cur 为例
Node* rightMinf = cur;
Node* rightMin = cur->left;
// 最小孩子一定在右子树的最左节点处（不一定为叶子节点）
while (rightMin->left) {
rightMinf = rightMin;
rightMin = rightMin->left;
}
// 调整链接关系
// 调整 parent 的链接关系
if (parent->left == cur) {
parent->left = rightMin;
} else {
parent->right = rightMin;
}
// 调整 rightMinp 的链接关系
rightMinf->left = rightMin->right;
// rightMin 不一定为叶子节点
// 调整替换节点的父子链接关系
rightMin->left = cur->left;
rightMin->right = cur->right;
// 删除节点
delete cur;
cur = nullptr;
return true;
}
}
}
cout << "没有该节点" << endl;
return false;
}
// 查
bool Find(const K& key) {
// 双指针 从根节点出发寻找合适位置
Node* cur = _root;
Node* parent = nullptr;
while (cur) {
if (key < cur->_key) {
// 该节点在 cur 的左子树处
parent = cur;
cur = cur->left;
} else if (key > cur->_key) {
// 该节点在 cur 的右子树处
parent = cur;
cur = cur->right;
} else {
// key == cur->_key 即相同节点 直接跳过
return true;
}
}
// 没找到
return false;
}
void Inorder() {
assert(_root);
inorder(_root);
}
private:
// 中序遍历
void inorder(const Node* root) {
// 递归出口
if (root == nullptr)
return;
// 左根右
inorder(root->left); // 左子树
cout << root->_key << endl;
inorder(root->right);
}
Node* _root = nullptr; // 根节点
};
}
7.2 key/val 代码实现
二叉搜索树 key/val 模型代码实现
#pragma once
// key/val 模型的实现
#include <iostream>
using namespace std;
namespace twg {
// key/val 节点
template<class K, class V>
struct BSTnode // 其实就是 pair
{
// 数据
K _key;
V _val;
BSTnode* left; // 左孩子
BSTnode* right; // 右孩子
// 构造函数
BSTnode(const K& key, const V& val):_key(key),_val(val),left(nullptr),right(nullptr){}
};
// key/val 模型 容器 map
template<class K, class V>
class map {
typedef BSTnode<K, V> Node;
public:
// 默认成员函数
// 显示默认构造
map() = default;
// C++11 引用 告诉编译器帮我生成一个默认构造函数
/*map() { _root = nullptr; }*/
// 拷贝构造
map(const map<K, V>& a) {
// 递归式深拷贝
_root = Copy(a._root);
}
// 析构函数
~map() {
Destory(_root);
}
// 赋值
map<K, V>& operator=(map<K, V> a) {
std::swap(_root, a._root); // 现代式写法 a 是临时拷贝对象 出了函数会自动析构
return *this;
}
// 增删查改
// 增
bool Insert(const K& key, const V& val) {
// 先寻找位置
// 判断是否为空树
if (_root == nullptr) {
// 新节点为根节点
_root = new Node(key, val);
return true;
}
// 双指针循环
Node* cur = _root;
Node* parent = nullptr;
while (cur) {
// 根据 key 找
if (key <= cur->_key) {
// 新节点的位置在左子树处
parent = cur;
cur = cur->left;
} else if (key > cur->_key) {
// 新节点的位置在右子树处
parent = cur;
cur = cur->right;
}
}
// 找到了 新节点的位置
cur = new Node(key, val);
// 链接父子
if (cur->_key <= parent->_key) {
// 新节点为 parent 的左孩子
parent->left = cur;
} else {
// 新节点为 parent 的右孩子
parent->right = cur;
}
return true;
}
// 遍历
void Inorder() {
_inorder(_root);
cout << endl;
}
// 查 根据 key
bool Find(const K& key) {
// 双指针 从根节点出发寻找合适位置
Node* cur = _root;
Node* parent = nullptr;
while (cur) {
if (key < cur->_key) {
// 该节点在 cur 的左子树处
parent = cur;
cur = cur->left;
} else if (key > cur->_key) {
// 该节点在 cur 的右子树处
parent = cur;
cur = cur->right;
} else {
// key == cur->_key 即相同节点 直接跳过
return true;
}
}
// 没找到
return false;
}
// 删除
bool Erase(const K& key) {
// 先找
Node* cur = _root;
Node* parent = nullptr;
while (cur) {
// 根据 key 找
if (key < cur->_key) {
parent = cur;
cur = cur->left;
} else if (key > cur->_key) {
parent = cur;
cur = cur->right;
} else {
// 找到了
// 根据孩子的个数 执行不同的删除逻辑
// 0~1 个孩子代码实现上相同
// 可将叶子节点 视作只有一个空孩子
// 假设只有右孩子
if (cur->right != nullptr) {
// 判断该节点是否为根节点
if (parent == nullptr) {
// 该节点为根节点
// 右子树成为新的根节点
_root = cur->right;
}
// 删除的是子树上的节点
else {
if (parent->left == cur) {
parent->left = cur->right;
} else {
parent->right = cur->right;
}
}
// 删除节点
delete cur;
cur = nullptr;
return true;
}
// 有两个孩子
// 替换法
// 以 左子树的最大孩子为替代 不一定为叶子节点
Node* leftMax = cur->right;
Node* leftMaxf = cur;
while (leftMax->right) {
leftMaxf = leftMax;
leftMax = leftMax->right;
}
// 找到了替换节点
// 调整链接
cur->_val = leftMax->_val;
cur->_key = leftMax->_key;
leftMaxf->right = leftMax->left;
// 删除节点
delete leftMax;
leftMax = nullptr;
return true;
}
}
// 删除失败
cout << "没有该节点，删除失败" << endl;
return false;
}
// 改
V& operator[](const K& key) {
// 1. 查找键，若存在则返回对应值的引用
Node* cur = _root;
Node* parent = nullptr;
while (cur) {
if (key < cur->_key) {
parent = cur;
cur = cur->left;
} else if (key > cur->_key) {
parent = cur;
cur = cur->right;
} else {
// 找到键，返回值的引用
return cur->_val;
}
}
// 2. 键不存在，插入新节点（值用默认构造）
cur = new Node(key, V());
// 插入默认值（如 int 默认 0）
if (parent == nullptr) {
// 空树，新节点作为根
_root = cur;
} else {
// 链接到父节点的左/右子树
if (key < parent->_key)
parent->left = cur;
else
parent->right = cur;
}
// 3. 返回新插入节点的值的引用
return cur->_val;
}
private:
// 函数
Node* Copy(const Node* root) {
// 递归出口
if (root == nullptr)
return nullptr;
Node* newNode = new Node(root->_key, root->_val);
newNode->left = Copy(root->left); // 拷贝左子树
newNode->right = Copy(root->right); // 拷贝右子树
return newNode;
}
void Destory(Node* root) {
// 递归出口
if (root == nullptr)
return;
// 递归式析构
// 先析构左右子树
Destory(root->left);
Destory(root->right);
// 析构根
delete root;
// 核心 root = nullptr;
}
// 遍历
void _inorder(const Node* root) {
// 递归出口
if (root == nullptr)
return;
// 中序遍历
_inorder(root->left); // 左子树
cout << root->_key << ": " << root->_val << endl; // 根值
_inorder(root->right); // 右子树
}
// 数据
Node* _root = nullptr; // 根节点
};
}
结语
二叉搜索树的'左小右大'特性的背后，是高效数据查询的核心逻辑 —— 它既弥补了二分查找的插入删除短板，也为后续平衡树（AVL、红黑树）打下基础。掌握双场景适配与增删查改的边界处理后，你已能应对简单数据存储需求。