数据结构：二叉搜索树（排序树）

1.二叉搜索树的定义

二叉搜索树要么是空树，要么是满足以下特性的树

（1）左子树不为空，那么左子树左右节点的值都小于根节点的值

（2）右子树不为空，那么右子树左右节点的值都大于根节点的值

（3）其所有子树也满足二叉搜索树性质

（4）二叉搜索树有两种形态，一种是支持插入冗余值，一种是不支持的（一般默认不支持冗余）

简单来说就是左边节点值 < 根节点值 < 右边节点值

二叉搜索树又叫二叉排序树，这是因为如果对他进行中序遍历，将会得到一组升序排序的数据

2.二叉搜索树的性能

二叉搜索树的搜索次数是等于树的高度的

最优情况：对于类似完全二叉树的树结构，时间复杂度可以达到O(logn)

最差情况：对于几乎所有数据都单侧分布的情况，时间复杂度会到O(n)

为了使他保持最优的性能，我们后续会引入平衡的概念，使他保持左右子树高度差小于等于1

3.部分实现非冗余二叉搜索树

节点基本结构搭建：

对于bstree的搭建：只需要加一个private的根节点指针即可

3.1插入

（1）若树为空，则直接新建节点，然后把新节点的地址给bs树的根节点，返回true，表示插入成功

（2）若树不为空，则判断key和当前节点的值的大小

若key小于当前节点的值：往左边搜索

若大于当前节点的值：往右边搜索

若等于当前节点值：直接返回false

如果我只用一个cur指针，是不能完成节点的链接的，因为链接节点的是cur的直接根节点，也就是prvcur节点，所以这里我们才创建一个prvnode指针，就是用于把新节点和bs树进行连接的。

（3）找到之后判断key于待链接节点的值的大小决定插入在左侧还是右侧

---

接下来进入测试阶段，不过在测试之前我们需要写一个中序遍历的方法，以便更直观的检查逻辑是否正确

我们利用递归的方式实现，结束条件是节点为空。

由于二叉搜索树左子树 < 根节点 < 右子树的性质，我们使用中序遍历可以实现升序输出

不过这里有个问题，我们需要传递bstree的private变量，可以使用友元，实现get函数等方法去获取m_root，现在我们介绍一个新的方式

                                                         封装进类中

我们在_inorder中实现具体功能，然后封装到inorder中，inorder主要用于调用m_root给_inorder传递参数

3.2查找

由于我们在插入部分已经进行过查找数据，所以我们只需要对insert的代码稍微改一下即可

下面我们进行调试

对1的查找成功，对11的查找失败，符合预期

3.3删除

对于删除，总共有四种情况

情况1：delete节点为叶子节点

解决方法：找到该节点后让他的父节点指向nullptr，并释放该节点空间

情况2：delete节点只有左节点

解决方法：让他的父节点指向他的那一侧指向delete的左节点

情况3：delete节点只有右节点

解决方法：让他的父节点指向他的那一侧指向delete的右节点

情况4：delete节点左右节点均有

解决方法：寻找delete左子树的最大节点，或者delete右子树的最小节点，然后交换delete位置的值与replace节点的值，让replace的父节点空余的一侧指向replace节点的左侧（从左子树找时），或者右侧（从右子树找时）。最后释放replace位置的空间

疑问一：为什么是寻找delete左子树的最大节点，或者delete右子树的最小节点？

答：

因为我们需要保持二叉搜索树的排序结构，只能从左树找一个最大数据（保证替换后根大于左树，且由于是从左树找的数据，必然也是小于右树的数据的），或者从右数找一个最小数据（和左树同理）

疑问二：寻找到的replace节点为什么可以直接让其父节点接入另一侧？

答：

因为replace已经是最左或者最右节点，所以不可能两侧都有节点，最多只有另一侧有节点。

特殊情况分析：

（1）对于delete节点有左右节点，且replace的节点就是左子树根节点，或右子树根节点

我们需要把replace的父节点设置为cur，而不是空，否则会有空指针访问。

并且replace父节点的指向侧也不是确定的，这种情况下和会更新replace父节点的情况，父节点的指向侧是相反的

（2）对于delete节点只有右节点或左节点，且delete节点为搜索树的根节点

由于这种基于情况1,2,3的情况下，我们需要释放delete节点的空间，所以根节点需要删除就涉及根节点的指针指向变更。

我们对cur==m_root的情况用if语句单独处理，让m_root指向cur->left或cur->right

---

代码实现：

(1)大框架搭建：我们使用insert的代码作为查找大框架

我们的代码写在找到delete节点cur的位置

（2）对情况1-3进行处理，并把特殊情况1纳入考虑

由于右侧为空/左侧为空的情况可以兼容两侧为空的情况，所以我们不用单独处理两侧为空的情况

（1）cur左为空

对于cur左为空且cur为根节点：更改m_root,指向cur有节点的一侧，也就是右侧

对于cur非根节点的情况：让父节点指向cur的那一侧指向cur有节点的一侧

（2）cur右为空

（3）cur左右非空

我们实现的是从左子树中查找最大节点，也可以换成从右子树查找最小节点

第一步：

查找replace节点：循环更改replace与replaceprv指针，直到replace指向的节点右侧为空

第二步：

交换delete与replace节点的值

第三步：让replace父节点指向replace节点的左侧

注意:

若replace父节点就是cur，说明节点就在cur的左侧，用父节点左侧指向replace节点左侧。

若replace父节点不为cur，说明进入了循环，而replace父节点就是上一次的replace，replace一直在往右走，所以其父节点一定是右侧指向replace节点