从零开始的c++之旅——二叉搜索树

1、二叉搜索树概念

1. ⼆叉搜索树的概念

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

• 若它的左⼦树不为空，则左⼦树上所有结点的值都⼩于等于根结点的值

• 若它的右⼦树不为空，则右⼦树上所有结点的值都⼤于等于根结点的值

• 它的左右⼦树也分别为⼆叉搜索树

• ⼆叉搜索树中可以⽀持插⼊相等的值，也可以不⽀持插⼊相等的值，具体看使⽤场景定义，map/set/multimap/multiset系列容器底层就是⼆叉搜索树，其中map/set不⽀持插⼊相等值，multimap/multiset⽀持插⼊相等值

以下就是两颗二叉搜索树

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

最优情况下，⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树)，其⾼度为：O(log2 N)

最差情况下，⼆叉搜索树退化为单⽀树(或者类似单⽀)，其⾼度为：O( N/2 )

所以综合⽽⾔⼆叉搜索树增删查改时间复杂度为：O(N)

这样的效率显然是⽆法满⾜我们需求的，后续会讲解⼆叉搜索树的变形，平衡⼆叉搜索树AVL树和红⿊树，才能适⽤于我们在内存中存储和搜索数据。

⼆分查找也可以实现O( logN ) 级别的查找效率，但是⼆分查找有两⼤缺陷：

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

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

这⾥也就体现出了⼆叉搜索树的价值。

3. 二叉搜索树的实现

需要明确的一点是，我们此处实现的是不可插入相同值的二叉搜索树。

而搜索二叉树的本质还是使用递归来完成，因此与我们之前博客实现的二叉树逻辑大体相似，因此一些类似的操作我们简略描述。

3.1 定义二叉搜索树

3.1.2 定义二叉搜索树节点

这与之前实现的二叉树类似，只不过用上了模板跟构造函数，因为构造函数我们在后面需要用来生成节点。

template<class K>
struct BSTNode
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}
};

3.1.2 定义二叉搜索树结构

template<class K>
class BSTree
{//这里也能体现封装思想，不管我们如何实现的类此处我们只需定义成Node即可typedef BSTNode<K> Node; private:Node* _root = nullptr;//头节点
}

3.2 中序遍历

根据二叉搜索树的性质，中序遍历得到的应该是一个有序的升序列表。

中序搜索的逻辑与之前大差不差，我们只需记住：先遍历左子树，在打印当前根节点的值，而后遍历右子树，这就是“ 左根右”。

不要忘记了返回条件：遍历到空需要返回到上一级。

最后需要注意的一点是，我们遍历时需要传入头节点root，但是root是我们类的私有成员变量，在类外无法访问，那我们怎么办呢？对于这种问题有个统一的办法，我们可以将这个函数定义成类的私有成员，在写一个类的公有成员函数，去调用类的私有成员函数即可。

pubilc：void InOder(){_InOder(_root);cout << endl;}   private：void _InOder(Node* root){if (root == nullptr){return;}_InOder(root->_left);cout << root->_key << " ";_InOder(root->_right);}

3.3 插入

我们根据搜索二叉树的特点可以得出我们的插入逻辑：

1.若当前的树是一颗空树，那么我们只需新增节点赋给root节点即可。

2.若树不为空我们只需根据二叉搜索树的性质，定义一个指针cur遍历二叉搜索树，若cur指向的节点值大于我们要插入的值va，则cur往右子树走，反之则往左子树走，知道cur的下一节点为空时，用val初始化一个节点并根据cur和val的值比较，判断插入到左子树还是右子树

	bool Insert(const K& val){if (_root == nullptr){_root = new Node(val);return true;}Node* parent = _root;Node* cur = _root;while (cur){if ( val < cur->_key ){parent = cur;cur = cur->_left;}else if ( val > cur->_key ){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(val);if (val > parent->_key){parent->_right = cur;}else{parent->_left= cur ;}return true;}

3.4 查找

从根开始⽐较，查找x，x⽐根的值⼤则往右边⾛查找，x⽐根值⼩则往左边⾛查找。⾛到到空，还没找到，这个值不存在，返回false。找到则返回true。

	bool Find(const K& val){Node* cur = _root;while (cur){if (val > cur->_key){cur = cur->_right;}else if (val < cur->_key){cur = cur->_left;}else{return true;}}return false;}

3.5 删除

二叉搜索树的插入时整个步骤中最复杂的，因为在插入数据时我们需要对二叉搜索树的部分结构进行适当的调整，使其保持原有的性质。

我们以下图的删除二叉数为例

在删除之前，我们还需要明确一点，我们删除节点释放完资源之后，还需使其对应的父亲节点指向nullptr，避免产生野指针的问题，因此我们我们要一个指针cur来搜寻要删除的节点，还需要一个指针parent来记录cur的前一节点。

在删除的过程中，分为了好几种情况。，我们需要分别讨论

1. 删除的位置为叶子节点
这时候只需要cur搜索到对应的节点，再删除即可。

2. 删除的位置只有一个孩子节点。
若cur为parent的左节点，则使 parent->left 指向cur的非空节点
反之则使 parent->right 指向cur的非空节点

3.删除位置有两个孩子节点
这是最后一种也是最复杂的一种情况。有两个孩子意味着删除了该节点后我们需要对搜索二叉树部分结构进行适当的调整。

这里我没有两种方法：我们定义一个指针MaxLeft，使其找到要删除节点cur左子树的最大值，或者定义一个指针MinRight，使其找到cur右子树的最小节点，将其与cur的值进行交换，在删除LeftMax或者MinRight指向的节点即可
为什么可以选择这两个节点的其中一个呢，因为只有选择这两个节点才会保证二叉搜索树的性质不变。
我们以交换右子树最小节点为例，下列图我们可以看出，MidRight指针与cur交换完之后二叉搜索树的性质依然符合。

但是我们还需要注意的是，和前面的两点一样，我们删除掉MidRight节点之后，不要文件将其父节点对应的指针指向nullptr，因此我们还需要定义一个指针PMidRight，防止释放完MidRight之后找不到其对应父节点。

以下是实现的代码

	bool Erase(const K& val){if (_root == nullptr){_root = new Node(val);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (val < cur->_key){parent = cur;cur = cur->_left;}else if (val > cur->_key){parent = cur;cur = cur->_right;}else{if (cur->_left == nullptr){//让父亲指向我的右if (cur==parent->_right){parent->_right=cur->_right;}else{parent->_left = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){if (cur == parent->_right){parent->_right = cur->_left;}else{parent->_left = cur->_left;}delete cur;return true;}else{Node* rightMin = cur->_right;Node* rightMinP = cur;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMinP->_left == rightMin)rightMinP->_left = rightMin->_right;elserightMinP->_right = rightMin->_right;delete rightMin;return true;}}}return false;}

4.源代码

#pragma once
#include<iostream>
#include<vector>
using namespace std;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:bool Insert(const K& val){if (_root == nullptr){_root = new Node(val);return true;}Node* parent = _root;Node* cur = _root;while (cur){if ( val < cur->_key ){parent = cur;cur = cur->_left;}else if ( val > cur->_key ){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(val);if (val > parent->_key){parent->_right = cur;}else{parent->_left= cur ;}return true;}bool Find(const K& val){Node* cur = _root;while (cur){if (val > cur->_key){cur = cur->_right;}else if (val < cur->_key){cur = cur->_left;}else{return true;}}return false;}void InOder(){_InOder(_root);cout << endl;}bool Erase(const K& val){if (_root == nullptr){_root = new Node(val);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (val < cur->_key){parent = cur;cur = cur->_left;}else if (val > cur->_key){parent = cur;cur = cur->_right;}else{if (cur->_left == nullptr){//让父亲指向我的右if (cur==parent->_right){parent->_right=cur->_right;}else{parent->_left = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){if (cur == parent->_right){parent->_right = cur->_left;}else{parent->_left = cur->_left;}delete cur;return true;}else{Node* rightMin = cur->_right;Node* rightMinP = cur;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMinP->_left == rightMin)rightMinP->_left = rightMin->_right;elserightMinP->_right = rightMin->_right;delete rightMin;return true;}}}return false;}private:Node* _root = nullptr;void _InOder(Node* root){if (root == nullptr){return;}_InOder(root->_left);cout << root->_key << " ";_InOder(root->_right);}
};