C++ 高阶数据结构：二叉搜索树（BST）万字详解 | 原理、增删查、key 与 key‑value 双版本实现、看懂 set/map 底层

引言：

1.二叉搜索树的概念

2.二叉搜索树的性能分析

3.二叉搜索树的插入原理

4.二叉搜索树的查找原理

5.二叉搜索树的删除原理

6.二叉搜索树的实现

6.1.构建初架构

拓展：using关键字

6.2.插入实现（Insert）

6.3.析构实现

6.4.Print实现（测试）

6.5.查找实现（find）

6.6.删除实现（erase）

6.7.拷贝构造，赋值实现

6.8.源码

7.二叉搜索树key和key/value使用场景

7.1.key搜索场景（对应set容器）

7.2.key/value搜索场景（对应map容器）

7.3.key/value二叉搜索树代码实现

结语：

引言：

从本篇开始，我们正式进入高阶数据结构的学习阶段。标准进阶学习路线推荐：普通二叉搜索树 → 平衡二叉搜索树 → AVL 树 → 红黑树 → B 树 / B + 树系列。

二叉搜索树是所有后续平衡树的基石，也是 C++ set/map的底层原型，非常重要。

那么话不多说，直接进入正文————>

1.二叉搜索树的概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值
若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值
它的左右子树也分别为二叉搜索树
二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义，后续我们学习 map/set/multimap/multiset 系列容器底层就是二叉搜索树，其中 map/set 不支持插入相等值，multimap/multiset 支持插入相等值

这种就是二叉搜索树

特别注意：二叉搜索树中序遍历得到升序序列。

二叉树左子树中所有节点一定不大于根节点，右子树中所有节点一定不小于根节点，中序遍历的访问顺序是左中右，所以以中序遍历得到的序列就是升序序列

2.二叉搜索树的性能分析

最优情况下，二叉搜索树为完全二叉树 (或者接近完全二叉树)，其高度为：log N

最差情况下，二叉搜索树退化为单支树 (或者类似单支)，其高度为：N

所以综合而言二叉搜索树增删查改时间复杂度为：O(N)

那么这样的效率显然是无法满足我们需求的，我后续会继续讲解二叉搜索树的变形，平衡二叉搜索树 AVL 树和红黑树，才能适用于我们在内存中存储和搜索数据。二叉搜索树主要是为了打好铺垫

另外需要说明的是，二分查找也可以实现O(log N)级别的查找效率，但是二分查找有两大缺陷：

需要存储在支持下标随机访问的结构中，并且有序。

插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。

这里也就体现出了平衡二叉搜索树的价值。

3.二叉搜索树的插入原理

我这里先讲理论，后实现

插入的具体过程如下：

树为空，则直接新增结点，赋值给 root 指针

树不空，按二叉搜索树性质，插入值比当前结点大往右走，插入值比当前结点小往左走，找到空位置，插入新结点。

如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑一致性，插入相等的值不要一会往右走，一会往左走）

就比如，一个二叉搜索树已经构建成了这样

我想插入16就走这条红线路

我想插入3就走这条红线路（这里相同情况下是往右走，往左走当然也可以，只要逻辑一致就可以）

4.二叉搜索树的查找原理

从根开始比较，查找 x，x 比根的值大则往右边走查找，x 比根值小则往左边走查找。
最多查找高度次，走到到空，还没找到，这个值不存在。
如果不支持插入相等的值，找到 x 即可返回
如果支持插入相等的值，意味着有多个 x 存在，一般要求查找中序的第一个 x。如下图，查找 3，要找到 1 的右孩子的那个 3 返回（因为是查找中序的第一个x，所以我们遇到找到x后要往左子树接着找）

5.二叉搜索树的删除原理

首先查找元素是否在二叉搜索树中，如果不存在，则返回 false。如果查找元素存在则分以下四种情况分别处理：（假设要删除的结点为 N）

要删除结点 N 左右孩子均为空

要删除的结点 N 左孩子为空，右孩子结点不为空

要删除的结点 N 右孩子为空，左孩子结点不为空

要删除的结点 N 左右孩子结点均不为空

对应以上四种情况的解决方案：

把 N 结点的父亲对应孩子指针指向空，直接删除 N 结点（情况 1 可以当成 2 或者 3 处理，效果是一样的）

把 N 结点的父亲对应孩子指针指向 N 的右孩子，直接删除 N 结点

把 N 结点的父亲对应孩子指针指向 N 的左孩子，直接删除 N 结点

无法直接删除 N 结点，因为 N 的两个孩子无处安放，只能用替换法删除。找 N 左子树的值最大结点 R (最右结点) 或者 N 右子树的值最小结点 R (最左结点) 替代 N，因为这两个结点中任意一个，放到 N 的位置，都满足二叉搜索树的规则。替代 N 的意思就是 N 和 R 的两个结点的值交换，转而变成删除 R 结点，R 结点符合情况 2 或情况 3，可以直接删除。

6.二叉搜索树的实现

我们设计二叉搜索树的时候会有俩份版本，一份是支持冗余的（有重复数字），一份是不支持冗余的（没有重复数字），这其实就是set和map底层的区别，我们这里实现不支持冗余的版本

我们这里实现的二叉搜索树实现了增删查的功能，改不实现，因为普通的二叉搜索树是不允许修改的（因为如果改了，那树就可能不是二叉搜索树了，性质就被破坏了）

6.1.构建初架构

#pragma once
#include <iostream>
template<class K>
class BSTNode
{
public:
BSTNode() = default;
BSTNode(const K& _key)
:_val(_key)
, _left(nullptr)
, _right(nullptr)
{

}

K _val = 0;
BSTNode<K>* _left = nullptr;
BSTNode<K>* _right = nullptr;
};

template<class K>
class BSTree
{
using Node = BSTNode<K>;
//typedef BSTNode<K> Node;
public:

private:
Node* _root = nullptr;
};

BSTNode就是代表节点，BSTree就是树

拓展：using关键字

我们先前用重命名用的是typedef，也就是

typedef BSTNode<K> Node;

这里拓展一点，我们可以用using关键字来进行重命名，这效果是C++11后新增的东西，现在可以从typedef转到用using，因为using在普通场景下效果和typedef是一样的，但在有些场景挺有用，具体会在C++11部分具体讲using，这个用法也很简单，就是如下这样

using Node = BSTNode<K>;

6.2.插入实现（Insert）

这里实现的是无重复数据版本

template<class K>
bool BSTree<K>::insert(const K& key)
{
if (_root == nullptr)
{
Node* node = new Node(key);
_root = node;
return true;
}
else
{
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
parent = cur;
if (cur->_val > key)
cur = cur->_left;
else if (cur->_val < key)
cur = cur->_right;
else
return false;
}
Node* node = new Node(key);
if (parent->_val > key)
parent->_left = node;
else
parent->_right = node;
return true;
}
}

6.3.析构实现

insert函数涉及了堆内存的开辟，那我们就实现一下析构

//类内
//…..
~BSTree()
{
Destroy(_root);
}
void Destroy(Node* root);
//…

//类外
template<class K>
void BSTree<K>::Destroy(Node* root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}

6.4.Print实现（测试）

这里实现Print函数是为了测试实现的二叉搜索树有没有问题，为了不让外部直接调用带参的Print，我们可以封装一层,然后把带参的Print设为私有

template<class K>
void BSTree<K>::Print()
{
Print(_root);
}

template<class K>
void BSTree<K>::Print(Node* root)
{
if (root == nullptr)
return;
Print(root->_left);
std::cout << root->_val << " ";
Print(root->_right);
}

接下来，我们测试一下insert有没有问题

#define _CRT_SECURE_NO_WARNINGS
#include "Binary Search Tree.h"
#include <string>
using namespace std;
int main()
{
BSTree<int> bsti;
bsti.insert(1);
bsti.insert(3);
bsti.insert(2);
bsti.insert(4);
bsti.insert(4);
bsti.Print();

cout << endl;

BSTree<string> bsts;
bsts.insert("ababab");
bsts.insert("baabab");
bsts.insert("aabbab");
bsts.insert("bbabab");
bsts.insert("bbabab");
bsts.Print();

return 0;
}

对于内置类型和自定义类型都是没问题的

6.5.查找实现（find）

template<class K>
bool BSTree<K>::find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_val > key)
cur = cur->_left;
else if (cur->_val < key)
cur = cur->_right;
else
return true;
}
return false;
}

测试一下

6.6.删除实现（erase）

template<class K>
bool BSTree<K>::erase(const K& key)
{
if (_root == nullptr)
return false;
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_val > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_val < key)
{
parent = cur;
cur = cur->_right;
}
else
{
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_right == cur)
parent->_right = cur->_right;
else
parent->_left = cur->_right;
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_right == cur)
parent->_right = cur->_left;
else
parent->_left = cur->_left;
}
delete cur;
}
else
{
Node* sparent = cur;
Node* scur = cur->_right;
while (scur->_left)
{
sparent = scur;
scur = scur->_left;
}
cur->_val = scur->_val;
if (sparent == cur)
sparent->_right = scur->_right;
else
sparent->_left = scur->_right;
delete scur;
break;
}
return true;
}
}
return false;
}

我用这份测试代码测试一下

#define _CRT_SECURE_NO_WARNINGS
#include "Binary Search Tree.h"
#include <string>
using namespace std;
int main()
{
int a[] = { 8,3,1,10,6,4,7,14,13 };
BSTree<int> bsti;
for (auto x : a)
bsti.insert(x);
bsti.Print();
cout << endl;

bsti.erase(3);
bsti.Print();
cout << endl;

bsti.erase(14);
bsti.Print();
cout << endl;

bsti.erase(8);
bsti.Print();
cout << endl;

//BSTree<string> bsts;
//bsts.insert("ababab");
//bsts.insert("baabab");
//bsts.insert("aabbab");
//bsts.insert("bbabab");
//bsts.insert("bbabab");
//bsts.Print();
//cout << bsts.find("aabbab") << " " << bsts.find("aabbbb");

return 0;
}

没有问题

6.7.拷贝构造，赋值实现

为了预防浅拷贝，最后把拷贝构造和赋值实现一下就OK了

//类内
BSTree<K>& operator=(BSTree<K> bst);

BSTree() = default;

BSTree(const BSTree& bst)
{
_root = Creat(bst._root);
}
Node* Creat(Node* root);

//类外
template<class K>
typename BSTree<K>::Node* BSTree<K>::Creat(Node* root)
{
if (root == nullptr)
return nullptr;
Node* cur = new Node(root->_val);
cur->_left = Creat(root->_left);
cur->_right = Creat(root->_right);
return cur;
}

template<class K>
BSTree<K>& BSTree<K>::operator=(BSTree<K> bst)
{
std::swap(_root, bst._root);
return *this;
}

6.8.源码

#pragma once
#include <iostream>
template<class K>
class BSTNode
{
public:
BSTNode() = default;
BSTNode(const K& _key)
:_val(_key)
, _left(nullptr)
, _right(nullptr)
{

}

K _val = 0;
BSTNode<K>* _left = nullptr;
BSTNode<K>* _right = nullptr;
};
//

template<class K>
class BSTree
{
using Node = BSTNode<K>;

//typedef BSTNode<K> Node;
public:
bool insert(const K& key);
bool find(const K& key);
bool erase(const K& key);
void Print();
BSTree<K>& operator=(BSTree<K> bst);

BSTree() = default;

BSTree(const BSTree& bst)
{
_root = Creat(bst._root);
}

~BSTree()
{
Destroy(_root);
}

private:
Node* Creat(Node* root);
void Print(Node* root);
void Destroy(Node* root);
Node* _root = nullptr;
};

template<class K>
void BSTree<K>::Destroy(Node* root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}

template<class K>
void BSTree<K>::Print()
{
Print(_root);
}

template<class K>
void BSTree<K>::Print(Node* root)
{
if (root == nullptr)
return;
Print(root->_left);
std::cout << root->_val << " ";
Print(root->_right);
}

template<class K>
bool BSTree<K>::find(const K& key)
{
if (_root == nullptr)
return false;
Node* cur = _root;
while (cur)
{
if (cur->_val > key)
cur = cur->_left;
else if (cur->_val < key)
cur = cur->_right;
else
return true;
}
return false;
}

template<class K>
typename BSTree<K>::Node* BSTree<K>::Creat(Node* root)
{
if (root == nullptr)
return nullptr;
Node* cur = new Node(root->_val);
cur->_left = Creat(root->_left);
cur->_right = Creat(root->_right);
return cur;
}

template<class K>
BSTree<K>& BSTree<K>::operator=(BSTree<K> bst)
{
std::swap(_root, bst._root);
return *this;
}

7.二叉搜索树key和key/value使用场景

二叉搜索树使用主要是俩个场景，key搜索场景和key/value搜索场景

7.1.key搜索场景（对应set容器）

只有 key 作为关键码，结构中只需要存储 key 即可，关键码即为需要搜索到的值（也就是我们上面实现的那种BST），搜索场景只需要判断 key 在不在。key 的搜索场景实现的二叉树搜索树支持增删查，但是不支持修改，修改 key 破坏搜索树结构了。

场景 1：小区无人值守车库，小区车库买了车位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录入后台系统，车辆进入时扫描车牌在不在系统中，在则抬杆，不在则提示非本小区车辆，无法进入。

场景 2：检查一篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，不在则波浪线标红提示。（可以把VS我们输错关键词爆红理解成这样）

key搜索场景简单说就是在不在（也就是对应我们之后的set容器）

7.2.key/value搜索场景（对应map容器）

每一个关键码 key，都有与之对应的值 value，value 可以任意类型对象。树的结构中 (结点) 除了需要存储 key 还要存储对应的 value，增 / 删 / 查还是以 key 为关键字走二叉搜索树的规则进行比较，可以快速查找到 key 对应的 value。key/value 的搜索场景实现的二叉树搜索树支持修改，但是不支持修改 key，修改 key 破坏搜索树性质了，可以修改 value。

场景 1：简单中英互译字典，树的结构中 (结点) 存储 key (英文) 和 value (中文)，搜索时输入英文，则同时查找到了英文对应的中文。

场景 2：商场无人值守车库，入口进场时扫描车牌，记录车牌和入场时间，出口离场时，扫描车牌，查找入场时间，用当前时间‑入场时间计算出停车时长，计算出停车费用，缴费后抬杆，车辆离场。

场景 3：统计一篇文章中单词出现的次数，读取一个单词，查找单词是否存在，不存在这个说明第一次出现，（单词，1），单词存在，则 ++ 单词对应的次数。

7.3.key/value二叉搜索树代码实现

这个实现其实就是在原先的key搜索场景的基础上改改就行了，这里我就直接放代码了

namespace key_value
{
template<class K,class V>
class BSTNode
{
public:
BSTNode() = default;
BSTNode(const K& key, const V& value)
:_key(key)
,_value(value)
, _left(nullptr)
, _right(nullptr)
{

}

K _key;
V _value;
BSTNode<K, V>* _left = nullptr;
BSTNode<K, V>* _right = nullptr;
};
//

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

//typedef BSTNode<K> Node;
public:
bool insert(const K& key, const V& value);
Node* find(const K& key);
bool erase(const K& key);
void Print();
BSTree<K,V>& operator=(BSTree<K,V> bst);

BSTree() = default;

BSTree(const BSTree& bst)
{
_root = Creat(bst._root);
}

~BSTree()
{
Destroy(_root);
}

private:
Node* Creat(Node* root);
void Print(Node* root);
void Destroy(Node* root);
Node* _root = nullptr;
};

template<class K, class V>
bool BSTree<K,V>::insert(const K& key, const V& value)
{
if (_root == nullptr)
{
Node* node = new Node(key, value);
_root = node;
return true;
}
else
{
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
parent = cur;
if (cur->_key > key)
cur = cur->_left;
else if (cur->_key < key)
cur = cur->_right;
else
return false;
}
Node* node = new Node(key, value);
if (parent->_key > key)
parent->_left = node;
else
parent->_right = node;
return true;
}
}

template<class K, class V>
void BSTree<K, V>::Destroy(Node* root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}

template<class K, class V>
void BSTree<K, V>::Print()
{
Print(_root);
}

template<class K, class V>
void BSTree<K, V>::Print(Node* root)
{
if (root == nullptr)
return;
Print(root->_left);
std::cout << root->_key << "->" << root->_value << " ";
Print(root->_right);
}

template<class K, class V>
typename BSTree<K, V>::Node* BSTree<K, V>::find(const K& key)
{
if (_root == nullptr)
return nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
cur = cur->_left;
else if (cur->_key < key)
cur = cur->_right;
else
return cur;
}
return nullptr;
}

template<class K, class V>
bool BSTree<K, V>::erase(const K& key)
{
if (_root == nullptr)
return false;
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_right == cur)
parent->_right = cur->_right;
else
parent->_left = cur->_right;
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_right == cur)
parent->_right = cur->_left;
else
parent->_left = cur->_left;
}
delete cur;
}
else
{
Node* sparent = cur;
Node* scur = cur->_right;
while (scur->_left)
{
sparent = scur;
scur = scur->_left;
}
cur->_key = scur->_key;
cur->_value = scur->_value;
if (sparent == cur)
sparent->_right = scur->_right;
else
sparent->_left = scur->_right;
delete scur;
break;
}
return true;
}
}
return false;
}

template<class K, class V>
typename BSTree<K, V>::Node* BSTree<K, V>::Creat(Node* root)
{
if (root == nullptr)
return nullptr;
Node* cur = new Node(root->_key, root->_value);
cur->_left = Creat(root->_left);
cur->_right = Creat(root->_right);
return cur;
}

template<class K, class V>
BSTree<K, V>& BSTree<K, V>::operator=(BSTree<K, V> bst)
{
std::swap(_root, bst._root);
return *this;
}
}

实现完了后可以用下面俩份测试代码测试一下

#define _CRT_SECURE_NO_WARNINGS
#include "Binary Search Tree.h"
#include <string>
using namespace std;
int main()
{
key_value::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;
}
#define _CRT_SECURE_NO_WARNINGS
#include "Binary Search Tree.h"
#include <string>
using namespace std;

int main()
{
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
key_value::BSTree<string, int> countTree;
for (const auto& str : arr)
{
// 先查找⽔果在不在搜索树中
// 1、不在，说明⽔果第⼀次出现，则插⼊<⽔果, 1>
// 2、在，则查找到的结点中⽔果对应的次数++
//BSTreeNode<string, int>* ret = countTree.Find(str);
auto ret = countTree.find(str);
if (ret == NULL)
{
countTree.insert(str, 1);
}
else
{
ret->_value++;
}
}
countTree.Print();
return 0;
}

结语：

那么，用C++实现的高阶数据结构的二叉搜索树部分的内容就全部讲解完毕啦，希望以上内容对你有所帮助，感谢观看，若觉得写的还可以，可以分享给朋友一起来看哦，毕竟一起进步更有动力嘛，当然能关注一下就更好啦。

C++ 高阶数据结构：二叉搜索树（BST）万字详解 | 原理、增删查、key 与 key‑value 双版本实现、看懂 set/map 底层

引言：

1.二叉搜索树的概念

2.二叉搜索树的性能分析

3.二叉搜索树的插入原理

4.二叉搜索树的查找原理

5.二叉搜索树的删除原理