文章目录
前言
在本节中，我们来介绍数据结构中一种特殊的二叉树——搜索二叉树。
一、二叉搜索树的概念
这节内容，其实我们在数据结构阶段就已经学习过了，不过我们当时只是仅仅学习这个二叉搜索树的用法以及如何通过给定的数据来画出这样的搜索二叉树，当时我们并没有详细介绍它，也没有介绍如何去实现它，现在咱们学习C++这么久了，也有能力去模拟实现一个二叉搜索树了，首先，我们先来了解一下什么是二叉搜索树。
二叉搜索树又称之为二叉排序树，它或是一个空树，或是一个具备以下特点的二叉树：
1.若它的左子树不为空，那么它的左子树上所有的值都是小于等于根节点的值；
2.若它的右子树不为空，那么它的右子树上所有的值都是大于等于根节点的值；
3.它的左右子树也是一个二叉搜索树；
4.二叉搜索树既支持插入相同的值又支持插入不同的值，这根据使用的场景来决定，我们后面学习的map/set/multimap/multiset等系列容器就是以二叉搜索树为底层实现的，其中map/set是不支持插入相同的值的，multimap/multiset是支持插入相同的值的。
二叉搜索树的主要功能是用来搜索某个值的，虽然我们在上面也介绍了它还叫做二叉排序树，但是这并不是它的主要功能，我们对这个二叉排序树进行中序遍历的话，我们就能够得到一个升序的有序序列。
我们在数据结构阶段就学习过了，时间复杂度我们一般并非只是看它的最优时间复杂度，我们也要看它的最差时间复杂度。当二叉搜索树是类似一个完全二叉树时，我们根据前面学习二叉树的经验可以得知，我们在这里面搜索查找某个值的时间复杂度是O（log N)；当二叉搜索树是一个单支树时，我们在里面查找某个值的时间复杂度就是O（N）。那么我们综合来看，它增删查的时间复杂度是O(N)。虽说不是特别的好，但是它也不差。
二、二叉搜索树的实现
1.二叉搜索树的基本框架
我们在之前数据结构中模拟实现一个二叉树时，我们首先是写一个结点的结构体，然后我们在使用这个结点来创建二叉树。这里我们同样需要这样做：我们首先写一个结点的类模板（我们现在学习类模板之后，我们模拟实现某个结构时基本都是需要使用类模板的，因为我们不能够明确结点的具体数据类型），注意我们在写结点的类模板时，我们要将结点的构造函数写上，这样我们后面在实现二叉搜索树时想创建一个结点时，直接可以new一个树结点了（调用结点类的构造函数）。至于二叉搜索树的类，我们可以再创建一个类模板来进行模拟实现。
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:
private:
Node* _root=nullptr;
};2.二叉搜素树的插入
对于二叉搜索树的插入主要分为如下两种情况：
1.当我们的二叉搜素树是一个空树时，我们直接创建一个新的结点并赋值作为新的根节点，这样也算是插入；
2.当我们的二叉搜素树不是一个空树时，我们需要根据二叉搜素树的规则（左小右大）来找出插入位置，然后再创建一个新的结点进行插入，注意这些插入位置可能与其他的结点有关系，我们需要处理好这些结点间的关系；
3.当我们支持插入相同的值时，当插入值与当前结点的值相同时，我们可以向左走也可以向右走，找到空位置后插入新结点，但是我们要保持逻辑一致性（开始就明确好，如果遇到相等的值就一直往左走或一直往右走，不要一会往左走一会往右走）。
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->_left = cur;
}
else if (parent->_key < key)
{
parent->_right = cur;
}
return true;
}3.二叉搜素树的查找
对于查找的实现原理就简单多了，我们只要遍历一遍二叉搜索树，如果找到了我们给定的值，我们就返回true，没有找到的话，我们就返回false。遍历的方法其实也很简单：我们首先创建一个结点并将其初始化为根节点，然后我们根据它的值与给定的值进行大小比较，然后再遵循二叉搜素树的规则遍历即可。
bool Find(const K& key)
{
if (_root == nullptr)
{
return false;
}
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
cur = cur->_left;
}
else if (cur->_key < key)
{
cur = cur->_right;
}
else
{
return true;
}
}
return false;
}4.二叉搜素树的删除
对于删除的实现原理相比较上面两种操作就麻烦多了，我们需要的考虑的情况也更加多。我们首先先判断我们要删除的值是否在二叉排序树中，如果没有的话，我们就直接返回false。如果有的话，我们就需要来找删除的结点，对于删除的结点我们要分为下面四种情况：
1.我们删除的结点的左右孩子都是空；
2.我们删除的结点的左孩子为空；
3.我们删除的结点的右孩子为空；
4.我们删除的结点的左右孩子都不为空。
针对于上面四种情况的处理方式如下所示：
1.对于我们结点无孩子结点的情况，我们可以直接将删除结点的双亲结点指向nullptr即可，然后再delete要删除的结点；
2，3.对于我们删除结点只有一个孩子结点的情况，我们处理的方式类似，我们首先先判断一下，我们要删除的那个结点是不是特殊结点（根节点），如果是根节点的话，我们直接将我们删除结点有结点的子树赋值给我们的根节点作为新的根节点；如果只是一个普通结点，我们找出其双亲结点与那个删除结点的关系（要删除结点是我们删除结点的左孩子还是右孩子），然后处理好被删除结点的子树与删除结点的双亲结点的关系，最后我们delete那个删除结点；
4.对于我们删除结点两个孩子结点都有的情况，我们就不能跟上面的三种处理方式一样了，我们不能够直接进行删除，我们需要自己寻找一个可以代替被删除结点的结点，并将两者的值进行替换，对于可以替代的结点，我们一般选择删除结点的左子树的最大结点和右子树的最小结点，因为这两个结点的值在其中序序列中排在我们删除值的两侧。
bool Erase(const K&key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur) //进入循环找删除位置
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else //找到要删除的位置了
{
//(1)我们删除位置的结点的左子树是空的
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
else
{
Node* minRightParent = cur;
Node* minRight = cur->_right;
while (minRight->_left)
{
minRightParent = minRight;
minRight = minRight->_left;
}
cur->_key = minRight->_key;
if (minRightParent->_left == cur)
{
minRightParent->_left = cur->_right;
}
else
{
minRightParent->_right = cur->_right;
}
delete minRight;
}
return true;
}
}
//出了循环，如果没有返回结果就说明没有找到，返回false
return false;
}5. 二叉搜索树的实现代码（源码）
//使用类模板，我们将树节点中的值类型使用模板参数K表示
//我们后面写结点类型时注意要带上这个模板参数
template<class K>
struct BSTNode
{
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
//树节点类的构造函数，我们使用初始化列表进行初始化，对于值我们直接使用传递过来的参数，两个左右子树的指针
//我们初始化为空指针nullptr
BSTNode(const K& key)
:_key(key)
, _left(nullptr)
, _right(nullptr)
{}
};
//我们再使用模板来定义一个二叉搜索树的类
//class SearchBinaryTree
template<class K>
class BSTree
{
typedef BSTNode<K> Node; //首先我们对树节点进行一下重命名，便于后续的类型使用
public:
//我们将那些二叉搜索树的基本接口定义实现在其public公有成员中
//插入（这里我们模拟实现的二叉搜索树只允许插入原来树中没有的值）
//我们这个接口的返回值定义为bool类型，如果那个值在原来的那个树中有的话，我们就不能进行插入，返回false
//如果不存在的话，我们就可以进行插入，根据左小右大的规则来找出插入位置，并返回true
//我们插入分为两大情况：（1)当树为一个空树的时候，我们直接创建一个树节点作为这个树的根节点
//（2）当树不为一个空树的时候，我们需要找出我们要插入的位置，然后再创建一个树节点进行插入
bool Insert(const K& key)
{
//（1）树为空树的情况
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
//（2）树不为空树的情况
//我们需要定义两个指针来找插入位置：我们定义一个当前结点指针（最终的插入位置）并将其初始化为根节点
//，然后我们再定义一个这个结点的上一个结点，因为我们最后要通过这个结点来实现对插入结点的连接，我们将其定义为空指针
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;
}
//查找
//我们将其返回值定义为boo类型，我们找到了就返回true，找不到就返回false，我们的传递的参数就是我们想要查找的值
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;
}
//删除
//我们的返回值也定义为bool类型，传递的参数就是我们想要删除的数据，如果我们找到了要删除的数据并进行了删除就返回一个true
//如果我们找不到要删除的数据，我们就不用执行删除操作了，我们直接进行返回false即可
bool Erase(const K& key)
{
//同上面的insert操作一样，我们首先定义两个指针，一个是指向删除位置的指针，一个是指向删除位置的双亲结点的指针
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
//按照左小右大的规则进行遍历查找，当cur—>key==key时，我们就找到了要删除数据的位置
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
//找到了要删除数据的位置
else
{
//（1）我们删除结点的左子树是空的
if (cur->_left == nullptr)
{
//对于上面这种情况又分为两种小情况：如果那个结点恰好是根节点的话，我们就要将其的右孩子结点定为新的根节点
//if (parent == nullptr)
if (cur == _root)
{
_root = cur->_right;
}
//如果那个结点不是根节点的话，我们就要判断我们要删除的那个结点是他双亲结点的左孩子结点还是右孩子结点
//我们上面的大条件是我们的删除结点的左右孩子情况，我们的小条件是删除结点的双亲结点的左右孩子情况
else
{
// 父亲指向我的右
if (cur == parent->_right)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
//在上面的条件语句中，我们已经将我们删除结点的右子树都给了删除结点的双亲结点了，于是我们直接删除那个删除结点
delete cur;
}
//（2）我们删除结点的右子树是空的
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
// 父亲指向我的左（我们删除结点的左子树不是空的，我们要将其交付给我们删除结点的双亲结点）
if (cur == parent->_right)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
delete cur;
}
//（3）我们要删除结点的左右子树都不是空的
//这种情况我们就不能贸然删除结点了，我们需要找出一个结点来替代我们的要删除结点
//我们一般可以进行替换的结点有：左子树中的最大结点（最右小端）和右子树的最小结点（最左下端），我们任意选择一个就行
else
{
// 找右子树最小节点(最左)替代我的位置
//我们这里也是定义两个指针来找那个右子树的最小结点，但是我们对于那个双亲结点的初始化，不能够再指向空指针了
//因为如果我们的minRight恰好是左子树为空的节点，那么我们在进行查找那个右子树的最小结点时，我们就无法进行了
//因为我们连下面的循环都没有进去，此时我们的minRightParent是一个nullptr，后面我们使用的minRightParent也是nullptr
//这样就不合理了，于是我们就索性将我们的minRightParent初始化为我们的删除结点，cur初始化删除节点的右子树根节点
Node* minRightParent = cur;
Node* minRight = cur->_right;
while (minRight->_left)
{
minRightParent = minRight;
minRight = minRight->_left;
}
//当结点的左子树指向空指针时就是我们的右子树最小结点，我们将那个结点的值与我们的要删除的值进行替换（直接覆盖，因为那个结点反正要删除了）
cur->_key = minRight->_key;
//右子树最小结点只是他在最左下角，因此他的左孩子是指向nullptr的，但是它的右孩子可能是有的
//我们要判断一下那个右子树最小结点与其双亲结点的联系，并将其的右子树交付给其的双亲结点
if (minRightParent->_left == minRight)
{
minRightParent->_left = minRight->_right;
}
else
{
minRightParent->_right = minRight->_right;
}
//由于要删除的结点的数据已经被我们替换覆盖了，我们直接将那个右子树最小结点删除即可
delete minRight;
}
return true;
}
}
return false;
}
//我们将在private域中定义的中序遍历进行了封装，作为公有成员方法
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
//这是二叉树的中序遍历，我们使用了递归的方式来实现的（LDR）
//我们把它设为私有成员是因为我们要将根节点作为参数传递过去，根节点作为私有成员
//如果想要在main函数中调用中序遍历，我们显然是无法调用这个私有成员方法的，于是我们在公有成员中
//再封装一个函数来表示中序遍历，毕竟在public中的成员是可以调用private的成员
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
//我们将树的根节点定义为私有成员，我们是不希望别人来访问我们的根节点的
Node* _root = nullptr;
};三、二叉搜索树的key和key/value使用场景
二叉搜索树的基本结构是每个结点都有一个键（key),用于决定结点的位置。比如，插入一个结点的时候，是根据键的大小来决定是放在左子树还是右子树。那如果BST只存储key，那么它主要是用来做什么的呢？应该是用来存储和查找这些键，比如在集合中添加元素或者检查元素是否存在。比如，如果我们有一个集合，里面有许多数字，如果我们使用BST来存储的话，插入和查找的时间复杂度都是O(logN),这个比数组的O（N）要快多了。
如果BST不仅存储key还存储value的话，那会有什么不同的呢？这时候，BST就不仅仅是一个集合了，而更像是一个字典（python中一种使用索引值来存储数据的结构）或哈希表（C++中一种使用索引值来存储数据的结构）。比如，我们用它来存储键值对，比如单词和它的中文意思，或者用户的ID和用户的相关信息。这时候，每个结点不仅有键，还有对应的值。这样在查找时，我们只有通过查找对应的索引值，我们就能够获取想要的值。这在存储一些具有关联数据的情况下是十分有用的，比如数据库中的索引，或者缓存系统中的数据存储。
那么在实际应用中，我们如何来选择呢？比如，我们只需要检查某个元素是否存在，那么只要用key的BST就足够了，因为我们不需要额外的值。而如果我们需要通过键来获取相应的值，于是我们就需要使用存储key和value的BST了。
在性能方面，我认为来着并没有什么区别，因为不论是只存储key还是既存储key还存储value，二叉树的结构和操作都是类似，只不过在每个结点中多了一个value字段，所以在插入，删除，查找等操作的时间复杂度还是O（log N)。
1. 仅存储键（Key-only BST）
- 结构：每个节点仅包含一个键（key）。
- 应用场景：
- 集合操作：用于存储一组唯一的键，支持插入、删除和查找操作。例如，检查一个元素是否存在于集合中。
- 排序：由于BST的性质，可以方便地进行中序遍历以获取有序的键列表。
- 优点：
- 简单高效，适合处理集合相关的操作。
- 插入、查找和删除的时间复杂度均为O(log n)。
- 缺点：
- 无法存储额外的信息，仅适用于简单的键存储。
2. 存储键值对（Key-Value BST）
- 结构：每个节点包含键（key）和对应的值（value）。
- 应用场景：
- 字典/映射表：用于存储键值对，支持根据键快速查找对应的值。例如，存储单词及其定义。
- 数据库索引：作为索引结构，允许根据键快速定位记录。
- 缓存系统：存储键值对，支持高效的缓存操作。
- 优点：
- 支持键值对的存储，适用于需要关联存储的场景。
- 同样具备BST的高效查找、插入和删除性能。
- 缺点：
- 每个节点存储额外的值，可能占用更多内存，但对性能影响较小。
3. 选择依据
- 需求分析：如果只需要处理键的存在性或集合操作，选择key-only BST；如果需要存储和检索关联的值，选择key-value BST。
- 性能考虑：两者的时间复杂度相似，主要区别在于空间占用和功能需求。
- 扩展性：key-value BST更具灵活性，适用于更复杂的数据存储需求。
示例
- Key-only BST：用于管理用户ID的集合，检查用户是否已注册。
- Key-value BST：用于存储用户ID与用户详细信息的映射，允许快速查找用户资料。
总结
BST的key-only和key-value版本分别适用于不同的场景。选择时需根据具体需求，权衡功能和性能。key-only适合简单的集合操作，而key-value适合需要存储和检索关联值的场景。
四、key-value二叉搜索树的模拟实现
对于key-value二叉搜索树的模拟实现，我们只需要在我们上面实现的key二叉搜索树的代码基础上修改一下即可。key-value的二叉搜索树的基本接口是一样的，我们还是通过key值来查找对应结点位置，我们在插入时，需要对value也进行存储了。接下来，我来附上key-value二叉搜素树的实现代码。
//我们一个结点中要放两个数据，因此我们在模板参数定义的时候，定义两个参数
template<class K,class V>
struct BSTNode
{
K _key;
V _value;
BSTNode<K>* _left;
BSTNode<K>* _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:
//插入的时候，我们传给Insert函数的函数参数也要传递两个参数
bool Insert(const K& key,const V& value)
{
//当树为空树时
if (_root == nullptr)
{
_root = new Node(key,value);
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,value);
if (parent->_key > key)
{
parent->_left = cur;
}
else if (parent->_key < key)
{
parent->_right = cur;
}
return true;
}
//在key-value二叉搜索树中，我们查找某个结点的位置，我们还是通过key来进行查找的，我们仅传递key参数即可
bool Find(const K& key)
{
if (_root == nullptr)
{
return false;
}
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
cur = cur->_left;
}
else if (cur->_key < key)
{
cur = cur->_right;
}
else
{
return true;
}
}
return false;
}
//我们的Erase函数传递的参数是我们想要删除的值（表示结点的索引值）
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur) //进入循环找删除位置
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else //找到要删除的位置了
{
//(1)我们删除位置的结点的左子树是空的
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
else
{
Node* minRightParent = cur;
Node* minRight = cur->_right;
while (minRight->_left)
{
minRightParent = minRight;
minRight = minRight->_left;
}
cur->_key = minRight->_key;
if (minRightParent->_left == cur)
{
minRightParent->_left = cur->_right;
}
else
{
minRightParent->_right = cur->_right;
}
delete minRight;
}
return true;
}
}
//出了循环，如果没有返回结果就说明没有找到，返回false
return false;
}
//中序遍历
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " "<<root->_value; //我们中序遍历时，输出结果时，我们既要输出索引值也要输出对应的值
_InOrder(root->_right);
}
Node* _root = nullptr;
};