一篇文章讲透数据结构之二叉搜索树

前言

在前面的学习过程中，我们已经学习了二叉树的相关知识。在这里我们再使用C++来实现一些比较难的数据结构。
这篇文章用来实现二叉搜索树。

一.二叉搜索树

1.1二叉搜索树的定义

二叉搜索树（Binary Search Tree）是基于二叉树的一种升级版本，因为普通的二叉树没有实际应用的价值，无法进行插入、删除等操作，所以我们进行了升级，升级成了二叉搜索树。
二叉搜索树是一种特殊的二叉树，它对数据的存储有着极其严格的要求：左节点比根节点小，右节点比根节点大。
下面我们展示一下二叉树和搜索二叉树的区别：
![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/f53117d894b24058a8add35c30699293.png
下面，我们通过中序遍历来看一看遍历结果：

我们发现，我们构建出的树是有序的。
那么，如果我们通过中序遍历+二分查找的话，会发现查找的效率很高，为O（logN）。这也是二叉搜索树名字的由来。

1.2二叉搜索树的特点

二叉搜索树的特点就是：左小于根，右大于根。

• 若某个结点的左节点不为空，那么它一定小于它的父节点。
• 若某个结点的右节点不为空，那么它一定大于它的父节点。
• 中序遍历的结果是有序的，为升序。

下面我们就来实现一颗二叉搜索树

二.二叉搜索树的实现

2.1基本框架

和二叉树类似的是，我们在建立二叉搜索树时，需要两个结构体。

• 节点类:表示结点
• 树类：表示树，存储结点。

template <class K>
struct BinarySearchTreeNode
{BinarySearchTreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key){}BinarySearchTreeNode<K>* _left;BinarySearchTreeNode<K>* _right;K _key;
};
template <class K>
class BinarySearchTree
{typedef BinarySearchTreeNode Node;
private:Node* _root=nullptr;
};

这样，我们便完成了大体的框架。

2.2 查找

由于我们的二叉搜索树是有序的。
因此，查找的逻辑如下：

• 若为空树，则返回false
• 查找值大于节点值，往右走。
• 查找值小于节点值，往左走。
• 相等时，则找到了结点。

因此，其实现如下：

bool Empty()const
{return _root = nullptr;
}
bool Find(const K& key)
{//空树if (Empty()){return false;}Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}elsereturn true;}
}

为了能够更好的理解这段代码，我给出如下图解：

2.3 插入

下面，我们来实现一下插入的算法。
对于插入而言，其实就是创建一个结点，然后查找到合适的位置并进行链接。
因此，我们可以想到，插入的大体逻辑如下：

• 先找到合适的位置
• 创建一个结点
• 将结点与其父节点进行链接

对于我们而言，找到合适的位置其实就是之前写的find函数。
因此，我们只需要copy一下代码，然后将新建结点并连接即可。

bool Insert(const K& key)
{//空的处理if (_root = nullptr){_root = new node(key);return true;}//查找//由于我们需要记录父结点，因此我们需要将parent记录出来。Node* parent = nullptr;Node* cur = _root;while (cur){//key大，往右走if (cur->_key < key){parent = cur;cur = cur->_right;}//key小，往左走else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}//新建结点cur = new Node(key);//判断是父的左子节点or右子节点，连接。if (parent->_key > key)parent->_left = cur;elseparent->_right = cur;return true;
}

需要一提的是，我们现在做的二叉树是不允许冗余的，当两个数相同时，就寄！
看一段插入逻辑：

下面，我们看一段冗余的逻辑：

这时，就出现了冗余的情况，插入失败了。

2.4 删除

删除是搜索二叉树的重点内容，它需要我们考虑非常多的情况。
下面，我们介绍一下具体的删除逻辑：

• 先依照查找的逻辑，判断目标值存不存在
• 如果存在，则进行删除
• 如果不存在，则寄！

说起来是非常简单的，但是实际的删除逻辑是极其复杂的，因为情况有非常多种。
首先，我们先把第一步查找的逻辑复现出来，然后我们再对删除的情况进行具体的分析。

	bool Erase(){//空的处理if (_root = nullptr){_root = new node(key);return true;}//查找//由于我们需要记录父结点，因此我们需要将parent记录出来。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{//具体的删除逻辑。}}}

下面，我们来思考删除逻辑的具体处理方式。

2.4.1右子树为空

我们对右子树为空的情况的处理：我们需要估计到其的子节点，因此我们需要将其父节点与其左子节点相连。

2.4.2左子树为空

对于左子树都为空而言，我们需要的的则是将其父节点与其右子节点相连。

2.4.3 左右子树都为空

删除的具体逻辑看图片

到现在为止，我们总结了三种情况，可以得出如下代码:

//具体的删除逻辑if (cur->_left == nullptr){if (parent->_left == cur) //是父的左{parent->_left = cur->_right;}else//是父的右parent->_right = cur->_right;}else if (cur->_right == nullptr){if (parent->_left == cur)//是父的左parent->_left = cur->_left;else//是父的右parent->_right = cur->_left;}

下面，我们来考虑一下左右子节点都为空的情况：

在左右子树都不为空的时候，因为cur有两个子节点，因此我们没有办法通过父节点与其子节点的链接解决问题了，这时我们应该怎么做呢？
我们这时的处理方式：
在不影响树的基本规则的情况下，找一个结点替代cur。
那么，现在问题就转化成为了如何找到那个能够取代cur的结点。
能够取代cur，那么就一定要满足二叉搜索树的限制关系。

我们假设在右子树，那么，这个结点一定要比父节点大，比左子节点大，比右子节点小。
这时，我们发现，cur的右子树的最左结点能够满足这点，也就是右子树的最小值。
代入上图：我们将3和6互换位置，得出如下结果：

同理，如果是左子树的话，就需要找到其最左结点，也就是左子树的最大值。
左子树的最大值和右子树的最小值我们选一个即可。
下面，我们来写写代码：

else//两个结点的情况
{Node* RrightMinParent == null;//下一段代码要修改这里Node* RightMin = cur->_right;while (leftMax->_left){RrightMinParent = RightMin;RightMin = RightMin->_left;}swap(cur->_key, RightMin->key);if (RrightMinParent->_left == RightMin){RrightMinParent->_left = RightMin->_left;//此时转换成为了删除没有子树的情况，等于左还是右都无所谓的}elseRrightMinParent->_right = RightMin->_left;
}

现在，我们已经完成了全部的逻辑，下面只需要我们进行一些边界处理即可以及删除掉结点即可。

请看代码注释：

	bool Erase(){//空的处理if (_root = nullptr){_root = new node(key);return true;}//查找//由于我们需要记录父结点，因此我们需要将parent记录出来。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{//具体的删除逻辑//判断是父的左还是右if (cur->_left == nullptr){//如果是根节点，则找不到parent，等于右结点即可。if (cur == _root){_root = _root->_right;}else{if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;}}else if (cur->_right == nullptr){//如果是根节点，则找不到parent，等于左结点即可。if (cur == _root){_root = _root->_left;}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}}else//两个结点的情况{RrightMinParent == cur;//下面的while循环可能进不去，此时若parent为空，寄！因此需初始化为curNode* RightMin = cur->_right;while (leftMax->_left){RrightMinParent = RightMin;RightMin = RightMin->_left;}swap(cur->_key, RightMin->key);if (RrightMinParent->_left == RightMin){RrightMinParent->_left = RightMin->_left;//此时转换成为了删除没有子树的情况，等于左还是右都无所谓的}elseRrightMinParent->_right = RightMin->_left;cur=RightMin;}delete cur;return true;}}return false;}

三.二叉搜索树的遍历

二叉搜索树的遍历和二叉树的遍历一模一样，在这里，我们只需要用到中序遍历
直接写在这里：
中序遍历：根->左->右
在使用CPP实现的二叉树中，我们有以下问题：

• 二叉树的根是私有属性，外界无法直接获取。

我们有如下的解决方案：

1. 公有化（不安全）
2. 通过函数获取(有点别扭，不爱写那么多)
3. 封装封装再封装！劳资再来一层！（好用爱用）
   我们采取解决方案3，解决方案3为：我们在private中实现中序遍历，然后在public里调用。
   如下：

public:void InOrder(){return _Inorder(_root);}
private:void _Inorder(Node* root){if (_root = nullptr){return;}_Inorder(root->_left)cout<<root->_key<<endl;_Inorder(root->_right)}Node* _root=nullptr;
};

四.递归实现

4.1查找

有关查找的逻辑，我们也可以使用递归实现。
实现逻辑如下：

• 如果当前根小于key，则递归到右树查找
• 如果当前根大于key，则递归到左树查找
• 如果当前树为空，则返回false
• 若以上条件都不符合，则是找到了，返回true

public:bool FindR(){return _FindR()}
private:void _FindR(Node* root,const K& key){if (root == nullptr){return false;}if (root->_key > key){return _FindR( root->_left,key);}else if (root->_key < key){return _FindR(root->_right, key);}return true;}

4.2插入

使用递归查找的话很简单，找到地方了之后直接把值放进去即可。

public:bool _InsertR(const K& key){return _Insert(root, key);}
private:void _InsertR(Node*& root, const K& key)//&不是取地址，而是引用{if (root = nullptr){root = new Node(key);//因为传递了指针的引用，因此我们可以在这里new一个nodereturn true;}if (root->_key < key)return _Insert(root->_right，key);else if (root->_key > key)return _Insert(root->_left，key);elsereturn false;}

4.3递归删除

删除的递归逻辑也需要使用引用
使用引用的目的是，在不同的函数栈帧中可以删除掉同一个节点，而不是临时变量。
另外，我们在这里使用的删除逻辑还是非递归版的删除逻辑，只不过找到key的方式变为递归了，如下：

bool _EraseR(Node*& root, const K& key)
{if (root == nullptr)  // 基本情况：当前结点为空，表示未找到key，删除失败。{return false;}if (root->_key < key)_EraseR(root->_right, key);  // 在右子树中递归查找并删除，不需要返回值。else if (root->_key > key)_EraseR(root->_left, key);   // 在左子树中递归查找并删除，不需要返回值。else  // 找到了要删除的结点{Node* del = root;  // 暂存当前结点，准备删除if (root->_left == nullptr)root = root->_right;  // 当前结点左子树为空，用右子树替换它。else if (root->_right == nullptr)root = root->_left;  // 当前结点右子树为空，用左子树替换它。else{Node* leftMax = root->_left;  // 查找左子树中的最大结点while (leftMax->_right){leftMax = leftMax->_right;}swap(root->_key, leftMax->_key);  // 交换当前结点和左子树最大结点的值return _EraseR(root->_left, key);  // 递归删除左子树中的最大结点}delete del;  // 删除当前结点return true;  // 删除成功}
}

五.其他实现

5.1 销毁

我们通过后序遍历的思想来销毁,先递归左子树销毁，再递归右子树销毁。最后销毁根节点。

	public:~BinarySearchTree(){Destory(_root);}
private:void Destory(Node*& root){if (root = nullptr)return;Destory(root->_left);Destory(root->_right);delete root;root = nullptr;}

5.2拷贝构造以及赋值重载

现在我们实现下拷贝构造来避免浅拷贝问题。

public:BinarySearchTree = default();BinarySearchTree(const BinarySearchTree<K>& a){_root = Copy(a._root);}BinarySearchTree<K>& operator=(BinarySearchTree<K> a){swap(_root, a._root);return *this;}
private:Node* Copy(Node* root){if (root = nullptr)return nullptr;Node* copyroot = new Node(root->_key);copyroot->_left = Copy(root->_left);copyroot->_right = Copy(root->_right);return copyroot;}