二叉搜索树

一. 二叉搜索树

1.1 二叉搜索树的概念

二叉搜索树是在普通的二叉树上进阶的，所以咱们今天的内容也可以说是，数据结构二叉树的进阶。二叉搜索树可谓是起到了承上启下的作用，向前承接了数据结构的二叉树，向后对于map和set的模拟实现也起到了启示作用。

那什么是二叉搜索树呢？

我们对于具有以下特征的二叉树为二叉搜索树：

1. 若左子树不为空，则左子树所有节点的值比根节点的值小
2. 若右子树不为空，则右子树所有节点的值比根节点的值大
3. 左右子树都是二叉搜索树

1.2 二叉搜索树的常用操作以及实现

1.2.1 二叉搜索树的查找操作

查找操作要求我们从跟开始找，如果要找的值小于根节点的值，则走左子树，反之走右子树。

那么我们的实现就可以分为非递归写法和递归写法：

（1）非递归写法：

（2）递归写法：

1.2.2 二叉搜索树的插入操作：

如果树为空的话，只需要新增一个节点，赋值给根节点，如果不为空，则先找到该插入的位置，再插入。

（1）非递归写法：

（2）递归写法：

此处对于形参root指针的引用可谓是妙到了极点。在我们递归过程中，当找到了该插入的位置时，令root等于新插入的节点，而我们上一层递归加引用则表示上一层递归根节点的左子树或者右子树等于新插入的节点，就不用再去考虑插入的节点与父辈节点之间的连接。

1.2.3 二叉搜索树的删除操作：

首先应该查找要删除的节点在不在，若在则可分为下面四种情况：

1. 无左右子树
2. 只有左子树
3. 只有右子树
4. 左右子树均存在

那我们来看看该如何实现这几种情况，其实第一种情况可以跟第二和第三种情况合并，那么就剩下三种情况：

对于只有左子树或只有右子树这两种情况，只需删除该节点，再根据删除的节点与父节点之间的连接关系来连接父节点与子节点的关系。

而对于左右子树都有的情况：我们则需要找到右子树中的最小节点，用来替换删除的该节点。

（1）非递归写法：

（2）递归写法：

二. 二叉搜索树的应用

2.1 K模型

K模型即只存储关键码Key，根据关键码就能找到节点。上面的操作都是K模型下的操作。

我们整体看一下K模型的代码：

2.2 KV模型

KV模型就是需要存储一个键值对<Key，Value>，对于每一个Key，都有对应的Value。

我们同样也来看一下KV模型的整体代码：

三. 二叉搜索树的性能分析

对于比较完美的搜索树，比如下图左边这种情况：

这种时间复杂度是O(logN)的。

而对于右边的这种极端情况，时间复杂度是O(N)的。

总结

好了，到这里今天的知识就讲完了，大家有错误一点要在评论指出，我怕我一人搁这瞎bb，没人告诉我错误就寄了。

祝大家越来越好，不用关注我（疯狂暗示）