C++ 二叉搜索树全解析！增删查改 + key/value 场景 + 完整代码，一篇通关
✨ 孤廖：个人主页
🎯 个人专栏：《C++：从代码到机器》
🎯 个人专栏：《Linux系统探幽：从入门到内核》
🎯 个人专栏：《算法磨剑：用C++思考的艺术》
折而不挠，中不为下
文章目录
正文：
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模型的实现代码
#pragmaonce#include<assert.h>#include<iostream>#include<time.h>usingnamespace 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>usingnamespace std;//去重版setnamespace twg {//set -> ket 模型//搜索二叉树节点template<classK>structBSTnode{//数据 K _key;//根值 BSTnode* left;//左孩子 BSTnode* right;//右孩子//构造BSTnode(const K& key=K()){ _key = key; left =nullptr; right =nullptr;}};//单参数的去重搜索二叉树容器 - > settemplate<classK>classset{typedef BSTnode<K> Node;public://增删查//set and unoredered_set 不支持改 （会破坏结构）//增 ---- stl 中的set 参数是pair 但本文件只是简单实现 boolInsert(const K& key){//在二叉搜索树的规则下 查询 新加入的节点的位置//能循环 尽量不 递归 这里采用双指针循环的方法 //判断是否为空树if(_root ==nullptr){//新加入的节点为根节点 _root =newNode(key);}//双指针 从根节点出发寻找合适位置 Node* cur = _root; Node* parent =nullptr;while(cur){if(key < cur->_key){//该节点在cur的左子树处 parent = cur; cur = cur->left;}elseif(key > cur->_key){//该节点在cur 的右子树处 parent = cur; cur = cur->right;}else{//key == cur->_key 即相同节点 直接跳过returntrue;}}//当cur 为空时 即新节点的位置找到了 cur =newNode(key);//链接 //判断子相对父的位置 if(parent->right ==nullptr){//链接 parent->right = cur;}else{ parent->left = cur;}returntrue;}//删boolErase(const K& key){//查询当前数据在哪个地方//双指针 从根节点出发寻找合适位置 Node* cur = _root; Node* parent =nullptr;while(cur){if(key < cur->_key){//该节点在cur的左子树处 parent = cur; cur = cur->left;}elseif(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;returntrue;}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;returntrue;}}} cout <<"没有该节点 "<< endl;returnfalse;}//查boolFind(const K& key){//双指针 从根节点出发寻找合适位置 Node* cur = _root; Node* parent =nullptr;while(cur){if(key < cur->_key){//该节点在cur的左子树处 parent = cur; cur = cur->left;}elseif(key > cur->_key){//该节点在cur 的右子树处 parent = cur; cur = cur->right;}else{//key == cur->_key 即相同节点 直接跳过returntrue;}}//没找到returnfalse;}voidInorder(){assert(_root);inorder(_root);}private://中序遍历voidinorder(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<classK>structBSTnode{//数据 K _key;//根值 BSTnode* left;//左孩子 BSTnode* right;//右孩子//构造BSTnode(const K& key =K()){ _key = key; left =nullptr; right =nullptr;}};//单参数的去重搜索二叉树容器 - > settemplate<classK>classset{typedef BSTnode<K> Node;public://增删查//set and unoredered_set 不支持改 （会破坏结构）//增 ---- stl 中的set 参数是pair 但本文件只是简单实现 boolInsert(const K& key){//在二叉搜索树的规则下 查询 新加入的节点的位置//能循环 尽量不 递归 这里采用双指针循环的方法 //判断是否为空树if(_root ==nullptr){//新加入的节点为根节点 _root =newNode(key);returntrue;}//双指针 从根节点出发寻找合适位置 Node* cur = _root; Node* parent =nullptr;while(cur){if(key <= cur->_key){//该节点在cur的左子树处 parent = cur; cur = cur->left;}elseif(key > cur->_key){//该节点在cur 的右子树处 parent = cur; cur = cur->right;}}//当cur 为空时 即新节点的位置找到了 cur =newNode(key);//链接 //判断子相对父的位置 if(parent->right ==nullptr){//链接 parent->right = cur;}else{ parent->left = cur;}returntrue;}//删boolErase(const K& key){//查询当前数据在哪个地方//双指针 从根节点出发寻找合适位置 Node* cur = _root; Node* parent =nullptr;while(cur){if(key < cur->_key){//该节点在cur的左子树处 parent = cur; cur = cur->left;}elseif(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;returntrue;}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;returntrue;}}} cout <<"没有该节点 "<< endl;returnfalse;}//查boolFind(const K& key){//双指针 从根节点出发寻找合适位置 Node* cur = _root; Node* parent =nullptr;while(cur){if(key < cur->_key){//该节点在cur的左子树处 parent = cur; cur = cur->left;}elseif(key > cur->_key){//该节点在cur 的右子树处 parent = cur; cur = cur->right;}else{//key == cur->_key 即相同节点 直接跳过returntrue;}}//没找到returnfalse;}voidInorder(){assert(_root);inorder(_root);}private://中序遍历voidinorder(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 模型代码实现
#pragmaonce////key/val 模型的实现#include<iostream>usingnamespace std;namespace twg {//key/val 节点template<classK,classV>structBSTnode//其实就是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 模型 容器 maptemplate<classK,classV>classmap{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;}//增删查改//增 boolInsert(const K& key,const V& val){//先寻找位置//判断是否为空树if(_root==nullptr){//新节点为根节点 _root =newNode(key, val);returntrue;}//双指针循环 Node* cur = _root; Node* parent =nullptr;while(cur){//根据key 找if(key <= cur->_key){//新节点的位置在左子树处 parent = cur; cur = cur->left;}elseif(key > cur->_key){//新节点的位置在右子树处 parent = cur; cur = cur->right;}}//找到了 新节点的位置 cur =newNode(key, val);//链接父子if(cur->_key <= parent->_key){//新节点为parent 的左孩子 parent->left = cur;}else{//新节点为parent的右孩子 parent->right = cur;}returntrue;}//遍历voidInorder(){_inorder(_root); cout << endl;}//查 根据keyboolFind(const K& key){//双指针 从根节点出发寻找合适位置 Node* cur = _root; Node* parent =nullptr;while(cur){if(key < cur->_key){//该节点在cur的左子树处 parent = cur; cur = cur->left;}elseif(key > cur->_key){//该节点在cur 的右子树处 parent = cur; cur = cur->right;}else{//key == cur->_key 即相同节点 直接跳过returntrue;}}//没找到returnfalse;}//删除boolErase(const K& key){//先找 Node* cur = _root; Node* parent =nullptr;while(cur){//根据key 找if(key < cur->_key){ parent = cur; cur = cur->left;}elseif(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;returntrue;}//有两个孩子//替换法//以 左子树的最大孩子为替代 不一定为叶子节点 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;returntrue;}}//删除失败 cout <<"没有该节点，删除失败"<< endl;returnfalse;}//改 V&operator[](const K& key){// 1. 查找键，若存在则返回对应值的引用 Node* cur = _root; Node* parent =nullptr;while(cur){if(key < cur->_key){ parent = cur; cur = cur->left;}elseif(key > cur->_key){ parent = cur; cur = cur->right;}else{// 找到键，返回值的引用return cur->_val;}}// 2. 键不存在，插入新节点（值用默认构造） cur =newNode(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)returnnullptr; Node* newNode =newNode(root->_key, root->_val); newNode->left =Copy(root->left);//拷贝左子树 newNode->right =Copy(root->right);//拷贝右子树return newNode;}voidDestory(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、红黑树）打下基础。掌握双场景适配与增删查改的边界处理后，你已能应对简单数据存储需求。
下一篇，我们将聚焦二叉搜索树的 “退化痛点”，探索 AVL 树如何通过平衡调整将性能稳定在 logN 级别。不妨先用本文代码实操不同数据插入场景，观察树的结构变化，欢迎在评论区分享你的发现，咱们一起向更高效的平衡树进阶～
