搜索二叉树

搜索二叉树的概念

二叉搜索树又称之为二叉排序树，它或是一个空树，或是一个具备以下特点的二叉树：

简单来说：就是左比根的值小，右比根的值大。一直这样延续下去。

1.若它的左子树不为空，那么它的左子树上所有的值都是小于等于根节点的值；

2.若它的右子树不为空，那么它的右子树上所有的值都是大于等于根节点的值；

3.它的左右子树也是一个二叉搜索树；

4.二叉搜索树既支持插入相同的值（允许冗余），又支持插入不同的值（不允许冗余，这根据使用的场景来决定，我们后面学习的map/multimap/set/multiset等系列容器就是以二叉搜索树为底层实现的，其中map/set是不支持插入相同的值的，multimap/multiset是支持插入相同的值的。

1.1 主要功能：查找

搜索二叉树的主要功能是：查找某个值。它搜索的比较快，只需要查找部分结构，不需要将整个都搜索。（怎么查找呢？想搜索x，从根结点开始，若x大于根结点的值，往右继续遍历；若x小于根结点的值，往左遍历…循环往复，最终找到x值/到最后一个值也没找到）

与二分查找的功能比较相似，但是比二分查找更好一点。

二分查找的缺点：1. 要求数组中的所有元素都必须是有序的（这样才可以进行二分查找）
2. 底层结构必须是数组，但这样会使得在头部/中部插入数据效率很低(需要移动数据)。（二分查找是通过下标去查找的，不断缩小区间）

1.2 功能：排序

它又叫做：二叉排序树，它还有排升序的功能。从它的结构可以看出

如果想排升序，那也就是小中大，也就是中序遍历了。对搜索二叉树进行中序遍历，即可得到升序的有序序列

1.3 时间复杂度

时间复杂度需要看它的最优时间复杂度以及最差时间复杂度。当二叉搜索树是类似一个完全二叉树时，在学习数据结构的时候说过，完全二叉树搜索查找某个值的时间复杂度(和层数有关)是O(log2N)；当二叉搜索树是一个单支树时，我们在里面查找某个值的时间复杂度(和个数有关，因为是单只树)就是O（N）。综合来看，它增删查的时间复杂度是O(N)。虽说不是特别的好，但是它也不差。

之后学习的AVL树和红黑树这两棵树均是由搜索二叉树变形而来的。

二、搜索二叉树的各种实现

2.1 基本框架

我们需要一点一点实现：二叉树我们使用struct结构体实现。二叉树是由一个一个的结点由指针链接起来的，我们先创建结点的结构体。再把结点使用在二叉树的结构体里面。

结点结构体：

1. 在创建结构体的时候，基本都会使用类模板，因为我们无法确定数据的类型
2. 在创建的时候，可以将结点的构造函数也实现，这样以后在实现二叉搜索树时，直接可以new一个树结点了（调用结点类的构造函数）
3. 为什么需要我们自己写构造函数，却不需要自己写析构呢
   如果不显式地将 _left 和 _right 设为 nullptr，那么这两个指针可能保留垃圾值，进而引发不可预料的行为

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

搜索二叉树终究也是一个容器，我们暂时不得知元素类型，所以也是用模板

template<class K>
struct BSTree
{typedef BSNode<K> Node;
private:
//成员变量一般私有Node* _root=nullptr;//vs里面编译器默认生成的构造函数，对于指针类型并不会初始化为空，需要我们显示进行初始化
};

2.2 插入

我们将那些二叉搜索树的基本接口定义实现在其public公有成员中

1. 如果根结点为空，代表整棵二叉树都是空的，那直接new一个新结点，赋值给根结点即可
2. 如果不为空：则按照逻辑，值比根大，往右走，小的话往左走
3. 在最后一步：不仅要将这个值放在合适的位置，还需要和父结点有链接（即：你是人家的左还是右，需要进行判断）

插入的原则：找到一个合适的空位置，将值放在那里

以插入5为例：

bool Insert(const K& key)
{if (_root == nullptr){_root = new Node(k);return true;  //返回成功(函数的类型是bool)}Node* parent = nullptr;  //总是在cur的上一级，用于最后一步的链接Node* cur = _root;while (cur)  //用循环找到合适的位置{if (key < cur->k)   {parent = cur;  //确保parent在cur的上一层，最终可以找到父结点cur = cur->_left;}else if (key > cur->k)  //说明合适位置在以cur为根的这棵树的右侧。{parent = cur;cur = cur->_right;}else {return false;}}//出循环代表着已经找到合适的位置了，只差赋值以及链接cur = new Node(key);if (key < parent->k){parent->_left = cur;}elseparent->_right = cur;return true;
}

2.3 查找

2.3.1 中序遍历

递归：

（不冗余的情况）

void _InOrder(Node* root)
{if (root == nullptr)return;_InOrder(root->_left);cout << root->k << " ";_InOrder(root->right);
}

这个是搜索二叉树的中序遍历的代码，但是这个是有问题的。我们的成员变量Node* _root是私有的，它在类里面可以随意用，但是不可以在类外面用。我们现在写的这个函数，是放在类里面的，它可以传参_root，但是在外面调用这个函数的时候，如何传参呢，_root是私有的，在外面无法传递这个参数。

解决办法：在类里面封装一个InOrder，在这个函数里调用_InOrder(在类里面调用还可以成功传参)，并且在类外面使用这个函数的时候都不用传参，对使用者十分友好。
数里面写递归，一般都会封装（因为根是私有的）
（冗余的情况）
这个是，不影响中序遍历的结果（根据下面的例子自己进行中序遍历看看结果）（要保持逻辑一致性（开始就明确好，如果遇到相等的值就一直往左走或一直往右走，不要一会往左走一会往右走）。）

2.3.2 查找

1. 从根开始比较，查找x，若x比根的值大，则往右边走继续查找，若x比根值小，则往左边走继续查找。

2. 最多查找高度次，若走到空，还是没有找到的话，就说明这个值是不存在的。

3. 如果不支持插入相等的值的话（不允许冗余），找到x即可返回

4. 支持插入相同的值时，当插入值与当前结点的值相同时，我们可以向左走也可以向右走，找到空位置后插入新结点，但是我们要保持逻辑一致性（开始就明确好，如果遇到相等的值就一直往左走或一直往右走，不要一会往左走一会往右走）。

尽量：可以不适用递归，就不使用递归

bool Find(const K& key)
{Node* cur = _root;while (cur) //cur不为空的情况下{if (key > cur->k)cur = cur->_right;else if (key < cur->k)cur = cur->_left;else if (key == cur->k)return true;}return false;
}

2.4 删除（记得将删除的结点进行销毁）

情况比较繁多：如果直接删除的话，后续的结点怎么办？

1. 如果删除的结点没有孩子结点，直接将其删除，将该结点的parent指向空。

2. 如果删除的结点有一个孩子结点：将该结点删除，再将该结点的父亲指向孩子。
   可以将前两种情况合并，如果准备删除的结点的左孩子为空，那就将父亲指向删除节点的右孩子(如果是没有孩子结点的情况，那右也是nullptr，那父亲指向它即可；如果是一个结点的情况，那父亲指向右孩子即可)；如果左不为空，那就有可能准备删除结点的右孩子为空，那将父亲指向左孩子即可。还有可能左右都不为空，继续往下看。是父亲的左还是右指向它们呢？取决于当时的情况
   

3. 如果删除的结点有两个孩子结点：（该将它指向谁呢？）这个时候不适合将它指向其中一个，因为另一个孩子没办法处理。使用替换法：

从左子树/右子树中找到一个合适的值【哪个值算合适呢？就是替换（即将被删除的结点的值)，放在删除的位置，是符合二叉搜索树的性质的，就是左子树的每个值都小于(该子树的根结点的值)，或者，右子树的每个值都小于(该子树的根结点的值)】，（用左子树的max或者右子树的min）和删除结点进行交换，使被删除的结点处于，前面两个案例的位置，便于删除。

左子树的max：位于左子树的最右边（因为大的值总是方右边）
右子树的min：位于右子树的最左边（因为小的值总是放左边）

那什么是合适的值呢？

在考虑删除之前，需要先‘根据值’‘找到它的位置’(利用循环)

	bool Erase(const K& key){BSNode<int>* parent = nullptr;BSNode<int>* cur = _root;while (cur){if (key > cur->k){parent = cur;cur = cur->_right;}else if (key < cur->k){parent = cur;cur = cur->_left;}else{//进入这个循环，则说明已经找到值为x的位置if (cur->_left == nullptr) //cur的左为空，要么cur的两个孩子都为空，要么左空，右不空{if (parent->_left == cur)parent->_left = cur->_right;else if (parent->_right == cur)parent->_right = cur->_right;delete cur;}else if (cur->_right == nullptr)  //到这里说明左不为空，所以进入这个if说明左不空，右空{//到这里说明cur的左不为空,但右为空if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;delete cur;}else{//到这里说明cur的左右孩子都不为空(开始找替换)//用循环找到合适的值，但不能让cur进入循环，否则就找不到删除的值了，所以用新的值进入循环BSNode<int>* recur = cur; BSNode<int>* reparent = parent;//以（寻找左子树的max）为例while (recur->_right){reparent = recur;recur = recur->_right;}//将cur的值替换cur->k = recur->k;//删除recurif (reparent->_left == recur)reparent->_left = recur->_left;elsereparent->_right = recur->_left;//再将recur释放delete recur;}return true;}}return false;}

但是有一个bug，如果删除的结点是根结点，以上代码是可以完成的。但是，如果是单支树(这里假设根结点没有左子树，只有单支的右子树)，我们删除根结点的话

进行修改：

bool Erase(const K& key)
{BSNode<int>* parent = nullptr;BSNode<int>* cur = _root;while (cur){if (key > cur->k){parent = cur;cur = cur->_right;}else if (key < cur->k){parent = cur;cur = cur->_left;}else{//进入这个循环，则说明已经找到值为x的位置if (cur->_left == nullptr) //cur的左为空，要么cur的两个孩子都为空，要么左空，右不空{//还需要注意：单支树(只有右)if (cur == _root){_root = cur->_right;}else{if (parent->_left == cur)parent->_left = cur->_right;else if (parent->_right == cur)parent->_right = cur->_right;}delete cur;}else if (cur->_right == nullptr)  //到这里说明左不为空，所以进入这个if说明左不空，右空{//到这里说明cur的左不为空,但右为空//同样需要注意单支树(只有左)if (cur == _root){_root = cur->_left;}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;}else{//到这里说明cur的左右孩子都不为空(开始找替换)//用循环找到合适的值，但不能让cur进入循环，否则就找不到删除的值了，所以用新的值进入循环BSNode<int>* recur = cur; BSNode<int>* reparent = parent;//以（寻找左子树的max）为例while (recur->_right){reparent = recur;recur = recur->_right;}//将cur的值替换cur->k = recur->k;//删除recurif (reparent->_left == recur)reparent->_left = recur->_left;elsereparent->_right = recur->_left;//再将recur释放delete recur;}return true;}}return false;
}

三、key的搜索场景

1. 搜索场景只需要判断key在不在。key的搜索场景实现的二叉树搜索树支持增删查，但是不支持修改，修改key破坏搜索树结构了。
2. 检查篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，不在则波浪线标红提示
3. 小区无人值守车库，小区车库买了车位的业主才能进入小区，那么业主会把买了车位的车主的车牌号录入后台系统，车辆进入时会扫描车牌在不在系统内，在则抬杆，不在的话就会提示非本小区车辆
   无法进入。

四、key/value搜索场景

一个key对应一个value

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

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

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

4. set --------key

5. map ---------key/value