二叉搜索树_数据结构二叉检索法查找关键码

map和set特性需要先铺垫二叉搜索树，而二叉搜索树也是一种树形结构。

1. 二叉搜索树概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

2. 二叉搜索树查找

二叉搜索树的查找：
1. 从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
2. 最多查找高度次，走到到空，还没找到，这个值不存在。
如果我们想找7，那么只需要找4次。

那么这个查找的时间复杂度是多少呢？
答案是：O(N)，不是O(logN)

这就是属于最坏的情况。

3. 二叉搜索树的实现

首先，我们把二叉搜索树的结点写出来：

第一步，我们需要对二叉搜索树进行插入。

3.1 二叉搜索树插入和查找

1. 树为空，则直接新增节点，赋值给root指针
2. 树不空，按二叉搜索树性质查找插入位置，插入新节点

在这里我们需要定义一个prev来记录当前结点的父结点。这样当我们去链接父子结点时就可以轻松链接了。然后我们这里是不允许插入相等的值，后面会讲允许插入相等的值。

这里我们的返回值需要带上const，防止结点的值被修改破坏二叉搜索树的性质。

3.2 中序遍历

我们知道中序遍历是左子树，根，右子树。而二叉搜索树左子树<根<右子树。所以我们中序遍历就会得到从小到大的值。

在这里我们需要注意：当别人使用时不能传根，因为根是私有的。我们可以写一个GetRoot函数或者再封装一层。

3.3 二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面几种情况：
1. 没有孩子或者是只有一个孩子–直接删除
2. 两个孩子的结点无法直接删除，需要找其它结点代替。规则：可以找该结点左子树里的最大值或者是右子树里的最小值–替换法删除

else里面就是找到了，如果没有找到cur就是空，直接返回false。现在先完成直接删除。我们可以按照14来举例：我们要删除14，它有左孩子，没有右孩子。它的父亲10有右孩子，没有左孩子。那么我们删除14，那么10的右边应该指向14的左边。
结论：
删除的结点只有左(右)孩子，且在父亲左边。父亲左边指向删除结点的左(右)边。
删除的结点只有左(右)孩子，且在父亲右边。父亲右边指向删除结点的左(右)边。

叶子结点也同样适用，因为它会走第一个if，然后父结点直接指向空。但是这里有一个bug。原因是：如果root只有一个孩子。且删除的就是根，那么prev是空指针，就会报错。

在这里，我们加上了一个判断。如果cur等于根，我们就让根指向它孩子结点。
下面我们写一下两个孩子删除的情况：

我们以删除3和8为例子来说明。根据替换法规则：左边找最大值，右边为最小值。我们写一下左边最大值的例子：
假设我们要删除3，那么我们就要找3左边的最大值。3左边最大值就是1，我们需要将1替换到3的位置上去。然后删除1，我们还需要让我们的父节点(3)的左边指向孩子结点(1)的左孩子。因为1是最大，它可能有左孩子，但不会有右孩子。

这样我们就让leftmax指向了1，leftmax_parent指向了3。现在我们需要让父节点(3)的左边指向孩子结点(1)的左边。

我们再来看一下删除8是什么情况：
前面的就不多说了，leftmax指向7，leftmax_parent指向了6。我们需要让父结点(6)的右边指向孩子结点(7)的左边。

大家也可以自己写一下按右边最小值的方案来写，思路是一致的。

3.4 析构和拷贝构造和赋值

析构我们可以封装一层私有的。

二叉搜索树的拷贝构造如何深拷贝？
比较好的办法是：用前序遍历来递归。

但是如果你现在构造一个树，你会发现下面的错误：

没有合适的默认构造函数。原因是：我们写的拷贝构造函数也算是构造函数。而当我们自己写了拷贝构造函数，那么编译器就不会去调用自己默认的构造函数了。我们可以自己写一个构造函数，或者是这样：

这是C++11的新特性。强制编译器自己生成构造。

赋值我们可以使用现代写法了。比较简单我们直接看代码：

4. 递归版本的实现

4.1 查找

因为需要递归，我们要传参数，所以要封装一层。查找比较简单，就不多说了。

4.2 插入

插入前，我们需要找到插入的位置：

什么时候进行插入呢？但root为空时就可以插入了。

但是此时会有一个问题：

假设我们要插入9，那么它在10的左边。现在我们该如何将10和9链接起来？因为我们是递归，传下来的是临时拷贝，不会影响父亲。

我们可以这样做：

加个引用就可以了。这样我们插入9的时候，我们是从root->_left递归下来的，所以root就是root->_left的别名。所以我们改变root，就等于改变了root->_left。

这个引用有两个作用：
第一个：在首次插入时，root是_root的别名。创建的新结点直接赋值给了_root。
第二个：插入新结点时，root是父亲结点的left或者是right。改变root，就会直接改变left或者right。

4.3 删除

前面的还是一样的道理：

那么删除的规则还是一样的，分直接删除和替换法删除。

只有一个孩子的时候，我们只需要这样写就可以了。

假设我们想要删除10，当经过前面的查找，此时root里面存的是10结点的地址。并且root是8->_right的别名。当root->_left为空的时候，说明删除的结点的左子树为空，我们需要将父节点链接到我们右孩子。那么root->_right就是14，root也是8->_right。所以我们将14的地址赋值给了8->_right。

同样这样写也符合这种情况：删除的是根(根只有一个孩子)

root是8，也是_root的别名。root->_left是3结点的地址。我们将root->_left赋值给root，也就是赋值给了_root。所以解决了这种情况。

有二个孩子删除如下：

这样我们找到了最小的结点并且和删除的结点进行了值交换。注意：这里交换比直接赋值更好。下面再说。

假设我们这里删除的是3，以右子树最小为例。我们需要找的是4。替换之后如下：

我们需要让6指向rightmin的右子树，因为右子树中最小结点它的左子树一定是空的。那么我们现在该怎么指向呢？

我们可以转换成root->_right(3的右子树)中去删除key，这里删除一定会走左为空的情况。

我们递归到这棵树去删这个key。这也是为什么用swap好，原因是可以递归。如果直接赋值就不能递归了。

5. 二叉搜索树的应用

K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
比如：给一个单词word，判断该单词是否拼写正确。具体方式如下：
以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树。在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。
比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对。
再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。

5.1 改造二叉搜索树为KV结构

KV结构和K结构的区别是什么呢？

在每个结点中要加上一个value。在二叉搜索树中，我们需要改插入函数和查找函数，删除函数不需要动。


在插入的时候，把我们要插入的对应值也插入进去。


这里的返回值，可以让我们去修改结点里面的value值。

我们可以验证一下：

运行结果如下：

下面在举一个例子：统计出现word的次数


打印的时候我们把value带上。运行结果如下：

5.2 多组输入问题

下面我们再说一下划黄线的问题：

我们知道scanf的返回值是整数，那么cin的返回值怎么判断呢？
首先，它这里调用的是string里的>>重载：

它是这样输入的：operator>>(cin，str)。所以它的返回值就是cin。那么一个自定义类型(istream)是怎么判断的呢？

原因是在istream里它重载了这个：


这个函数可以把对象强制转换成void*(C++98)或者bool(C++11)。也就是说cin会去调用cin.operator bool()，然后会返回真或者假。这个函数是没有返回值的，但是还是可以判断。这点大家需要注意。

这个explicit是什么意思呢？
explicit是为了防止隐式类型转换的，之前隐式类型转换是让一个内置类型构造一个自定义类型，然后这个自定义类型去拷贝构造。而在编译器优化下是直接构造。这里的意思是为了防止自定义类型隐式类型转成内置类型。这里不是真正的强转，只是去调用这个函数，而这个函数返回bool类型。