这幅图呢就是一个基本的二叉搜索树，可以看出，每一棵树都是一个二叉搜索树。为什么叫二叉搜索树呢？

我们根据上面二叉搜索树的特点可以发现这个特殊的树非常适合搜索某个数据，比如：我们要查找10这个数，大家可以查查需要几次就可以找到。

并且大家可以用中序遍历的方法打印出二叉搜索树的值就会发现是有序的，这是基于二叉搜索树的特征来实现的。

二叉搜索树的特征就决定它查找数据效率很高，下面我们就来探讨一下二叉搜索树的性能。

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

以上面这幅图为例，我们如果要查找10，经过查找就可以发现只需要查找树的高度次也就是：log2N，但现实每次效率都能做到这么高吗？ 答案显然不是的，就比如：

就比如这样的单支树，我现在要找1这个数，我们发现查找次数是其高度次：N。

所以二叉搜索树的搜索效率也是根据树的类型而定，我们总结一下： 最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其高度为:log2 N

最差情况下，二叉搜索树退化为单支树(或者类似单支)，其高度为:N所以综合而言二叉搜索树增删查改时间复杂度为:0(N) 那么这样的效率显然是无法满足我们需求的，所以在二叉搜索树的基础上发展出平衡二叉搜索树，也就是后面要讲的AVL树和红黑树。

为什么叫平衡二叉搜索树呢？

就是它会自动平衡左右子树结点的数量，让其左右子树的结点数量尽可能相等。我们设想一下，经过平衡操作后，是不是就可以保证效率就是log2N。

有人可能对时间复杂度log2N没什么概念，比如：在1000000个数据中查找某个值，最多才查找20次，在10亿个数据中查找某个值，最多也才查找30次，这个效率是很高的。 另外需要说明的是，二分查找也可以实现0(log2N)级别的查找效率，但是二分查找有两大缺陷: 1.需要存储在支持下标随机访问的结构中，并且有序。 2.插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。 这里也就体现出了平衡二叉搜索树的价值。

3.二叉搜索树的实现

这里我实现的二叉搜索树是不支持插入相同的值的。

并且以这个二叉搜索树为例来进行下面的操作。

3.1二叉搜索树的初始化

相信看到这个初始化的基本模型，大家就能猜到我要用链表来实现二叉搜索树，这个模型和之前我们实现的list很相似，不过要比list简单许多。并且二叉树的结构在二叉树的章节已经讲过，所以这里就不过多赘述了。

这里没有写构造函数是因为此时默认的构造函数就够我们使用了，后面会有不得不写构造函数的情况，这里先暂时不写。

3.1二叉搜索树的插入

插入的思路很简单，根据二叉搜索树的特征，我们先跟根结点中的值进行比较，如果比它大，就走右边，比它小就走左边，然后更新cur的位置，直至找到空的位置。

那么我们又要思考一个问题：cur找到了相应的位置，并创建结点，那么怎么让其和树连接起来呢？

显然，我们要定义一个变量parent来记录cur上一个走的位置。找到以后判断cur和parent值的大小，这里其实就是判断cur是在parent的左边还是右边。

经过上述操作我们就能把一个值按照二叉搜索树的特征插入到树中。

注意：

1.这里把插入的返回值设置成bool类型，和之前不同的原因是我们要创建的不含重复值的二叉搜索树，所以要判断是否插入成功。当然不一定非要设置成这样，如果你不想得到这样的反馈，也可以设置为void类型，根据不同的需求做出不同的选择即可。

2.要先判断此时的树是否是空树，也就是判断根节点是否为空，如果为空就要先创建一个结点作为根结点，如果不是再执行下面的操作。

3.2二叉搜索树的查找

查找的逻辑就更为简单，直接把插入中间那一段拿下来即可。这里就不需要parent了，直接通过cur来找，判断是否存在即可，存在就返回true，不存在就返回false。

3.3二叉搜索树的删除

二叉搜索树的删除就是其中最难的地方了，大家设想一下，我能直接删除其中的某个结点吗？

显然是不能的，如果是叶子结点还好，如果是中间的结点呢？直接删的话它的左右子树怎么办呢？

所以在删除这里要分情况讨论： 首先查找元素是否在二叉搜索树中，如果不存在，则返回false。 如果查找元素存在则分以下四种情况分别处理:(假设要删除的结点为N) 1.要删除结点N左右孩子均为空 2.要删除的结点N左孩子位空，右孩子结点不为空 3.要删除的结点N右孩子位空，左孩子结点不为空 要删除的结点N左右孩子结点均不为空对应以上四种情况的解决方案: 1.把N结点的父亲对应孩子指针指向空，直接删除N结点 2.把N结点的父亲对应孩子指针指向N的右孩子，直接删除N结点 3.把N结点的父亲对应孩子指针指向N的左孩子，直接删除N结点 4.无法直接删除N结点，因为N的两个孩子无处安放，只能用替换法删除。找N左子树的值最大结点 R(最右结点)或者N右子树的值最小结点R(最左结点)替代N，因为这两个结点中任意一个，放到N的位置，都满足二叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换，转而变成删除R结点。这里大家一定要自己画一下图来检验一下上述的解决方案，就像没有左子树，可能没有右子树也可能有；没有右子树，可能有左子树也可能没有，所以才会有这种解决方案，能完美解决这种问题。