C++《二叉搜索树》

在初阶数据结构中我学习了树基础的概念以及了解了顺序结构的二叉树——堆和链式结构二叉树该如何实现，那么接下来我们将进一步的学习二叉树，在此会先后学习到二叉搜索树、AVL树、红黑树；通过这些的学习将让我们更易于理解后面set、map、哈希等的使用以及对底层结构的了解。在此先本篇中我们将了解二次搜索树的概念以及实现二叉搜索树插入、删除等的操作，在了解了这些之后相信在下一篇的set和map的学习你将轻松许多，接下来就开始本篇的学习吧！！！

---

 1.二叉搜索树的概念

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

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

例如以下左边图示的就是不支持插入相等值得二叉搜索树，右边就是支持插入相等值得二叉搜索树

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

最好得情况下，在此在二叉搜索树当中最为完全二叉树(或者接近完全二叉树)，其高度为：

例如以下示例：

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

例如以下示例：

那么通过以上对二叉树最好和最坏情况的分析就可以得出综合而言二叉搜索树增删查改时间复杂度为： 

那么通过以上的分析可以看出二叉搜索树这样的效率显然无法满足我们需求的，我们后续需要继续讲解二叉搜索树的变形，平衡二叉搜索树AVL树和红黑树，才能适用于我们在内存中存储和搜索数据。

在此你可能会想到在二叉搜索树中查找数据不就类似与二分查找吗，那么直接使用之前学习的二分查找不就可以了吗，二分查找的效率相比二叉搜索树还更好，那为什么还要学习了解二叉搜索树呢？
在此二分查找也可以实现 O(logN) 级别的查找效率，但是二分查找有两大缺陷：

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

在使用到二分查找示我们使用的是数据对应的下标来实现查找，这就使得当被查找的一系列数据不是存储在数组里时就需要先将数据都存储在数组当中并且还要将数据排序成升序，在这个过程中就会有时间和空间上的损耗了 

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

在二分查找当中以上提到的缺点其实还不是最致命的，最要命的是当一组数据已经存储在数组当中时并且已经排序好时，如果之后我们要在这组数据当中再插入新的元素或者是要将原数据中的一个元素删除，那么通过之前顺序表的学习我们就知道每插入或者是删除一个元素时间复杂度都为O(N)，若多次进行操作这就使得时间复杂度非常高了

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

通过以上的分析这里也就体现出了平衡二叉搜索树的价值，在插入元素或者是删除元素都相比使用二分查找要有优势。

3. 二叉搜索树的插入

3.1插入分析

在此在二叉搜索树当中插入新的节点就要按照以下步骤进行分析：
1. 树为空，则直接新增结点，赋值给root指针
2. 树不空，按二叉搜索树性质，插入值比当前结点大往右走，插入值比当前结点小往左走，找到空位置，插入新结点。
3. 如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑⼀致性，插入相等的值不要⼀会往右走，⼀会往左走）

例如以下示例：
假设我们要将以下的数组元素依次插入到二叉搜索树当中

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

 所以元素插入完之后二叉搜索树的形式就如下所示：
 

这时如果我们要再插入值为16的元素在二叉搜索树中过程图就如下所示：

 再插入值为3的元素在二叉搜索树中过程图就如下所示：
 

3.2 插入代码实现 

在实现二叉搜索树的插入代码之前我们先要来实现二叉搜索树大体的结构代码

在此我们先创建一个BSTree.h的头文件在该文件当中来实现二叉搜索树的结构以及各个功能，再创建一个test.cpp的文件用于测试我们实现的二叉搜索树的各个功能是否能满足要求

实现了文件的创建之后接下来就来实现二叉搜索树的大体结构。在此由于二叉搜索树是由各个节点构成的，那么和之前实现链式结构的二叉树一样先要实现表示节点的结构体

#include<iostream>
using namespace std;template<class K>
struct BSTreeNode
{K _key;BSTreeNode<K>* left;BSTreeNode<K>* right;BSTreeNode(const K& key):_key(key),left(nullptr),right(nullptr){}
};

在此就创建一个结构体BSTreeNode来表示二叉树内节点，在节点当中有三个变量分别是_key表示节点内的数据、_left存储该节点左孩子节点的指针、_right存储该节点右孩子节点的指针。并且将该结构体实现成模板这样就可以支持节点内的元素是任意类型的数据，还有在结构体当中还实现了构造函数。

实现了节点的结构体之后接下来就可以来实现表示二叉搜索树的类，在此我们将类命名为BSTree，实现的是模板类，实现的大体结构如下所示：

template<class K>
class BSTree
{typedef BSTreeNode<K> Node;public://使用编译器生成的默认构造函数BSTree() = default;//实现各种功能的成员函数……private://头节点Node* _root = nullptr;};

完成了以上操作接下来就可以来实现插入函数的代码了

注：以下实现的插入函数是数据不支持冗余的情况也就是二叉树当中不支持插入相等的值

bool Insert(const K& key)
{//当根节点为空时if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;//节点的父节点Node* parentcur = nullptr;while (cur){//当key小于当前节点的值if (cur->_key < key){parentcur = cur;cur = cur->right;}当key大于当前节点的值else if (cur->_key > key){parentcur = cur;cur = cur->left;}//当key等于当前节点的值else{return false;}}cur = new Node(key);//当新节点内的值大于父节点内的值时if (parentcur->_key  <  key){parentcur->right = cur;}//当新节点内的值小于父节点内的值时else{parentcur->left = cur;}return true;}

4. 二叉搜索树的查找

4.1查找分析

在二叉搜索树中查找节点就要按照以下步骤进行分析：

1. 从根开始比较，查找x，x比根的值大则往右边走查找，x比根值小则往左边走查找。
2. 最多查找高度次，走到到空，还没找到，这个值不存在。
3. 如果不支持插入相等的值，找到x即可返回
4. 如果支持持插入相等的值，意味着有多个x存在，⼀般要求查找中序的第⼀个x。

例如以下示例： 

当要查找3时，要找到1的右孩子的那个3值返回 

4.2 查找代码实现 

在进行了二叉搜索树的节点查找的分析之后接下来我们就来实现查找代码

注：以下实现的查找函数是数据不支持冗余的情况也就是二叉树当中不支持插入相等的值 

Node* Find(const K& key)
{//当根结点为空时if (_root == nullptr){return nullptr;}Node* cur = _root;Node* parentcur = nullptr;while (cur){//当key大于当前节点的值if (cur->_key < key){parentcur = cur;cur = cur->right;}//当key小于当前节点的值else if (cur->_key > key){parentcur = cur;cur = cur->left;}//当key等于当前节点的值else{return cur;}}//当前二叉树中找不到值为key的节点return nullptr;
}

5. 二叉搜索树的删除 

5.1 删除分析

在二叉搜索树当中节点的删除相比插入和查找就复杂一些了，在此会出现以下的多种情况接下来就来一一分析

在此要删除的节点会有以下的四种情况：

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

当要删除节点的节点左右孩子节点都为空时就需要把N结点的父亲对应孩子指针指向空，直接删除N结点

例如以下示例：

在以上二叉搜索树当中要删除值为1的节点就需要将节点1删除之后再将其父节点的左孩子节点指向空

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

当要删除节点的节点左孩子节点为空时就需要把N结点的父亲对应孩子指针指向N的右孩子，之后直接删除N结点

例如以下示例：

 

在以上二叉搜索树当中要删除值为10的节点就需要将其父节点的左孩子变为原节点的右孩子节点之后再将节点10删除

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

当要删除节点的节点右孩子节点为空时就需要把N结点的父亲对应孩子指针指向N的左孩子，之后直接删除N结点

例如以下示例：

在以上二叉搜索树当中要删除值为14的节点就需要将其父节点的左孩子变为原节点的左孩子节点之后再将节点14删除

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

当要删除的节点左右孩子节点都不为空时，这是就不能像以上的情况一样简单的改变要删除节点的父节点指针，这时由于无法直接删除N结点，这是因为N的两个孩⼦无处安放，只能用替换法删除。在此根据二叉搜索树的性质就需要找N左子树的值最大结点R(最右结点)或者N右子树的值最小结点R(最左结点)替代N，因为这两个结点中任意⼀个，放到N的位置，都满足⼆叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换，转而变成删除R结点，R结点符合情况2或情况3，可以直接删除。 

例如以下示例：
 

在以上二叉搜索树当中要删除节点值为8的节点和值为3的节点，由于这两个节点都是左右孩子节点都不为空的节点，因此要删除值为8的节点就需要找到其左子树最右的节点或者是右子树最左的节点（在此我们是找右子树最左的节点）

之后交换要删除的节点和找出的节点的值

 

最后删除交换之后值为8的节点即可

注：要删除值为3的节点和以上的方式也类型在此就不再细致的讲解

5.2 删除代码实现

bool Erase(const K& key)
{//当根节点为空时if (_root == nullptr){return false;}//当前节点Node* cur = _root;//当前节点的父节点Node* parentcur = _root;while (cur){//当key的值大于当前节点的值if (cur->_key < key){parentcur = cur;cur = cur->right;}//当key的值大于当前节点的值else if (cur->_key > key){parentcur = cur;cur = cur->left;}//当key的值等于当前节点的值else{//当要删除的节点左孩子节点为空if (cur->left==nullptr){//当要删除的节点为根结点时直接改变_root指针的指向，之后再将原根结点释放if (cur == _root){Node* Right = cur->right;delete cur;_root = Right;}else{//当要删除的节点cur是其父节点的左节点时if (cur == parentcur->left){parentcur->left = cur->right;delete cur;}//当要删除的节点cur是其父节点的右节点时else if (cur == parentcur->right){parentcur->right = cur->right;delete cur;}}return true;}//当要删除的节点右孩子节点为空else if (cur->right==nullptr){//当要删除的节点为根结点时直接改变_root指针的指向，之后再将原根结点释放if (cur == _root){Node* Left = cur->left;delete cur;_root = Left;}else{//当要删除的节点cur是其父节点的左节点时if (cur == parentcur->left){parentcur->left = cur->left;delete cur;}//当要删除的节点cur是其父节点的右节点时else if (cur == parentcur->right){parentcur->right = cur->left;delete cur;}}return true;}//当要删除的节点左右孩子节点都为空else{Node* minrightParent = cur;Node* minright = cur->right;//找出当前节点右子树中的最左节点while (minright->left){minrightParent = minright;minright = minright->left;}cur->_key = minright->_key;//当最左节点为其父节点的左节点时if (minrightParent->left == minright){minrightParent->left = minright->right;}//当最左节点为其父节点的右节点时else {minrightParent->right = minright->right;}delete minright;return true;	}}}//当找不到要删除的节点就返回falsereturn false;}

 6. 二叉搜索树遍历

由于二叉搜索树的性质一棵二叉搜索树中序遍历输出的结果就是递增的，那么接下来我们就试着来实现中序遍历的代码

void Inorder()
{_Inorder(_root);cout << endl;
}void _Inorder(Node* root)
{if (root == nullptr){return;}_Inorder(root->left);cout << root->_key <<" ";_Inorder(root->right);
}

在此我们实现的中序遍历代码如上所示，那么这时你可能就会有疑问了，为什么要实现两个中序遍历的函数，不是直接使用一个函数就可以满足要求了吗？

在此要考虑到的是在BsTree类以外用户是无法得到二叉搜索树的根节点的，但是在调用中序遍历的函数根据之前我们使用递归的方式是需要一开始就需要将二叉树的根结点作为中序遍历函数的参数的。因此为了解决该问题就再在BSTree类内实现一个函数来调用中序遍历的成员函数，由于是在类的内部在此是可以访问私有的成员变量的，在类外部用户要使用中序遍历时就只需要调用无参的成员函数Inorder就可以得到二叉搜索树中序遍历的结果了。

7. 二叉搜索树完整代码

#include<iostream>
using namespace std;template<class K>
struct BSTreeNode
{K _key;BSTreeNode<K>* left;BSTreeNode<K>* right;BSTreeNode(const K& key):_key(key), left(nullptr), right(nullptr){}
};template<class K>
class BSTree
{typedef BSTreeNode<K> Node;public://使用编译器生成的默认构造函数BSTree() = default;bool Insert(const K& key){//当根节点为空时if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;//节点的父节点Node* parentcur = nullptr;while (cur){//当key小于当前节点的值if (cur->_key < key){parentcur = cur;cur = cur->right;}当key大于当前节点的值else if (cur->_key > key){parentcur = cur;cur = cur->left;}//当key等于当前节点的值else{return false;}}cur = new Node(key);//当新节点内的值大于父节点内的值时if (parentcur->_key < key){parentcur->right = cur;}//当新节点内的值小于父节点内的值时else{parentcur->left = cur;}return true;}Node* Find(const K& key){//当根结点为空时if (_root == nullptr){return nullptr;}Node* cur = _root;Node* parentcur = nullptr;while (cur){//当key大于当前节点的值if (cur->_key < key){parentcur = cur;cur = cur->right;}//当key小于当前节点的值else if (cur->_key > key){parentcur = cur;cur = cur->left;}//当key等于当前节点的值else{return cur;}}//当前二叉树中找不到值为key的节点return nullptr;}bool Erase(const K& key){//当根节点为空时if (_root == nullptr){return false;}//当前节点Node* cur = _root;//当前节点的父节点Node* parentcur = _root;while (cur){//当key的值大于当前节点的值if (cur->_key < key){parentcur = cur;cur = cur->right;}//当key的值大于当前节点的值else if (cur->_key > key){parentcur = cur;cur = cur->left;}//当key的值等于当前节点的值else{//当要删除的节点左孩子节点为空if (cur->left == nullptr){//当要删除的节点为根结点时直接改变_root指针的指向，之后再将原根结点释放if (cur == _root){Node* Right = cur->right;delete cur;_root = Right;}else{//当要删除的节点cur是其父节点的左节点时if (cur == parentcur->left){parentcur->left = cur->right;delete cur;}//当要删除的节点cur是其父节点的右节点时else if (cur == parentcur->right){parentcur->right = cur->right;delete cur;}}return true;}//当要删除的节点右孩子节点为空else if (cur->right == nullptr){//当要删除的节点为根结点时直接改变_root指针的指向，之后再将原根结点释放if (cur == _root){Node* Left = cur->left;delete cur;_root = Left;}else{//当要删除的节点cur是其父节点的左节点时if (cur == parentcur->left){parentcur->left = cur->left;delete cur;}//当要删除的节点cur是其父节点的右节点时else if (cur == parentcur->right){parentcur->right = cur->left;delete cur;}}return true;}//当要删除的节点左右孩子节点都为空else{Node* minrightParent = cur;Node* minright = cur->right;//找出当前节点右子树中的最左节点while (minright->left){minrightParent = minright;minright = minright->left;}cur->_key = minright->_key;//当最左节点为其父节点的左节点时if (minrightParent->left == minright){minrightParent->left = minright->right;}//当最左节点为其父节点的右节点时else{minrightParent->right = minright->right;}delete minright;return true;}}}//当找不到要删除的节点就返回falsereturn false;}void Inorder(){_Inorder(_root);cout << endl;}private://头节点Node* _root = nullptr;void _Inorder(Node* root){if (root == nullptr){return;}_Inorder(root->left);cout << root->_key << " ";_Inorder(root->right);}};

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

8.1 key搜索场景

key搜索场景的形式如下所示：

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

在以上我们了解实现的二叉搜索树其实是适用于key的场景，那么接下来就来看看那么场景是属于key的场景

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

场景2：检查⼀篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，不在则波浪线标红提示。 

8.2 key/value搜索场景

key/value搜索场景的形式如下所示：

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

接下来就来将以上我们实现的key二叉搜索树修改为key/value⼆叉搜索树代码，实现代码如下所示：

#include<iostream>
using namespace std;template<class K,class V>
struct BSTreeNode
{K _key;V _value;BSTreeNode<K ,V>* left;BSTreeNode<K ,V>* right;BSTreeNode(const K& key, const V& value):_key(key);_value(value), left(nullptr), right(nullptr){}
};template<class K,class V>
class BSTree
{typedef BSTreeNode<K,V> Node;public://使用编译器生成的默认构造函数BSTree() = default;bool Insert(const K& key, const V& value){//当根节点为空时if (_root == nullptr){_root = new Node(key,value);return true;}Node* cur = _root;//节点的父节点Node* parentcur = nullptr;while (cur){//当key小于当前节点的值if (cur->_key < key){parentcur = cur;cur = cur->right;}//当key大于当前节点的值else if (cur->_key > key){parentcur = cur;cur = cur->left;}//当key等于当前节点的值else{return false;}}cur = new Node(key, value);//当新节点内的值大于父节点内的值时if (parentcur->_key < key){parentcur->right = cur;}//当新节点内的值小于父节点内的值时else{parentcur->left = cur;}return true;}Node* Find(const K& key){//当根结点为空时if (_root == nullptr){return nullptr;}Node* cur = _root;Node* parentcur = nullptr;while (cur){//当key大于当前节点的值if (cur->_key < key){parentcur = cur;cur = cur->right;}//当key小于当前节点的值else if (cur->_key > key){parentcur = cur;cur = cur->left;}//当key等于当前节点的值else{return cur;}}//当前二叉树中找不到值为key的节点return nullptr;}bool Erase(const K& key){//当根节点为空时if (_root == nullptr){return false;}//当前节点Node* cur = _root;//当前节点的父节点Node* parentcur = _root;while (cur){//当key的值大于当前节点的值if (cur->_key < key){parentcur = cur;cur = cur->right;}//当key的值大于当前节点的值else if (cur->_key > key){parentcur = cur;cur = cur->left;}//当key的值等于当前节点的值else{//当要删除的节点左孩子节点为空if (cur->left == nullptr){//当要删除的节点为根结点时直接改变_root指针的指向，之后再将原根结点释放if (cur == _root){Node* Right = cur->right;delete cur;_root = Right;}else{//当要删除的节点cur是其父节点的左节点时if (cur == parentcur->left){parentcur->left = cur->right;delete cur;}//当要删除的节点cur是其父节点的右节点时else if (cur == parentcur->right){parentcur->right = cur->right;delete cur;}}return true;}//当要删除的节点右孩子节点为空else if (cur->right == nullptr){//当要删除的节点为根结点时直接改变_root指针的指向，之后再将原根结点释放if (cur == _root){Node* Left = cur->left;delete cur;_root = Left;}else{//当要删除的节点cur是其父节点的左节点时if (cur == parentcur->left){parentcur->left = cur->left;delete cur;}//当要删除的节点cur是其父节点的右节点时else if (cur == parentcur->right){parentcur->right = cur->left;delete cur;}}return true;}//当要删除的节点左右孩子节点都为空else{Node* minrightParent = cur;Node* minright = cur->right;//找出当前节点右子树中的最左节点while (minright->left){minrightParent = minright;minright = minright->left;}cur->_key = minright->_key;//当最左节点为其父节点的左节点时if (minrightParent->left == minright){minrightParent->left = minright->right;}//当最左节点为其父节点的右节点时else{minrightParent->right = minright->right;}delete minright;return true;}}}//当找不到要删除的节点就返回falsereturn false;}void Inorder(){_Inorder(_root);cout << endl;}private://头节点Node* _root = nullptr;void _Inorder(Node* root){if (root == nullptr){return;}_Inorder(root->left);cout << root->_key << ":" << root->_val << " ";_Inorder(root->right);}};

 

在以上我们了解实现的二叉搜索树其实是适用于key的场景，那么接下来就来看看那么场景是属于key的场景

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

场景1：简单中英互译字典，树的结构中(结点)存储key(文)和vlaue(中文)，搜索时输⼊英文，则同时查找到了英文对应的中文。
场景3：统计⼀篇文章中单词出现的次数，读取⼀个单词，查找单词是否存在，不存在这个说明第⼀次出现，（单词，1），单词存在，则++单词对应的次数。

以下的两个简单的示例就是使用二叉搜索树的key/val来解决
 

#include"BSTree.h"int main()
{//示例1
//将以下英文单词和对应的中文翻译绑定到一起，当用户输入输入正确的单词就输出其中文意思，否则就输出单词拼写错误BSTree<string, string> dict;dict.Insert("insert", "插入");dict.Insert("erase", "删除");dict.Insert("left", "左边");dict.Insert("string", "字符串");string str;while (cin >> str){auto ret = dict.Find(str);if (ret){cout << str << ":" << ret->_val << endl;}else{cout << "单词拼写错误" << endl;}}//示例2
//统计字符串数组当中各个水果的出现次数string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };// 统计水果出现的次BSTree<string, int> countTree;for (auto str : strs){auto ret = countTree.Find(str);if (ret == NULL){countTree.Insert(str, 1);}else{ret->_val++;}}countTree.Inorder();return 0;
}

以上就是本篇的区别内容了，希望能得到你的点赞和收藏 ❤️