二叉排序树可以是空树吗_最佳二叉排序树

JAVA面试汇总（七）数据结构与算法（二）　　终于到了数据结构与算法部分了，这里我将会手写代码实现一些基础的数据结构与算法，这部分实际才是咱们编程中的核心，很多时候大家使用SpringBoot各种框架，咱们很多能力实际上已经退化了，底层究竟如何实现的，具体哪些算法，实际咱们并不理解，重新学习并记录下来。希望大家喜欢吧，不过我估计看的人不会太多，因为这部分比较晦涩难懂。　　数据结构与算法第二篇，写着挺费劲的，一边自学一边写出来。　　目前我的所有面试题都在小程序中，大家可以扫码，以便持续新的面试题。

　　另外有啥不对的，大家欢迎指出来，我一准儿就改。　　6. 树-二叉排序树　　二叉排序树，任意结点左子树的所有结点的值都小于该节点的值且该结点右子树的值都大于该节点的值。以下两个图都是二叉排序树

　　7. 树-平衡树　　（1）二叉排序树的定义，某结点左子树的所有结点的值都小于该节点的值且该结点右子树的值都大于该节点的值。（2）平衡二叉树是特殊的二叉排序树。（4）每个节点都有一个平衡因子，也就是该节点的左子树高度－右子树高度。（4）平衡二叉树必须满足以下两个条件：必须是二叉排序树；平衡因子的绝对值小于等于1。（5）代码实现有些复杂，写一下基本逻辑吧，其实只有四种情况（6）LL型平衡旋转法，由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1增至2而失去平衡。例如下图，新增加了2节点，导致失去平衡。分别标出了各个节点的负载因子，其中5节点，负载因子是2（左子树高度2，右子树高度0），3节点，负载因子1（左子树高度1，右子树高度0），直接右旋（向右旋转），3变成根节点，2和5变为叶子结点。

　　（7）RR型平衡旋转法，由于在A的右孩子C 的右子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。例如下图，新增加了5节点，导致失去平衡。分别标出了各个节点的负载因子，其中2节点，负载因子是-2（左子树高度0，右子树高度2），3节点，负载因子-1（左子树高度0，右子树高度1），直接左旋（向左旋转），3变成根节点，2和5变为叶子结点。

　　（8）LR型平衡旋转法，由于在A的左孩子B的右子数上插入结点F，使A的平衡因子由1增至2而失去平衡。例如下图，新增了4节点，导致失去平衡。分别标出了各个节点的负载因子，其中5节点，负载因子是2（左子树高度2，右子树高度0），3节点，负载因子-1（左子树高度0，右子树高度1），这个调整略复杂，需进行两次旋转操作（先右旋，后左旋）。先将3节点和4节点右旋，变成LL型，在按照LL型右旋即可。

　　（9）RL型平衡旋转法，由于在A的右孩子C的左子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。例如下图，新增了4节点，导致失去平衡。分别标出了各个节点的负载因子，其中3节点，负载因子是-2（左子树高度0，右子树高度2），5节点，负载因子1（左子树高度1，右子树高度0），这个调整略复杂，需进行两次旋转操作（先左旋，后右旋）。先将4节点和5节点左旋，变成RR型，在按照RR型左旋即可。

　　8. 树-红黑树　　（1）为什么会产生红黑树呢？从二叉排序开始，二叉排序树的性质会导致他出现极端偏向一方的情况，不平衡，因此产生了二叉平衡树，这种树分布十分平均，查询效率非常高，但是几乎每一次插入都会导致再平衡，因此根据二叉平衡树的一些性质，修改了二叉平衡树的一些性质，增加了红黑节点，造了一棵不严格平衡的二叉平衡树，也就是上面说的，大体上平衡的红黑树。不平衡在哪里呢？（2）红黑树不平衡在哪里呢？新增加的节点默认是红色，主要是因为插入黑色可能节点会影响黑色高度，对红黑树的影响更大，而红色的节点在红黑树中不计算高度，也就是说，去掉所有红节点后，剩余的黑节点就是一个二叉平衡树，所以默认新增都是红色节点。那么如果算上红节点，整棵树就不是一个二叉平衡树。接下来看下性质（3）节点不是黑色，就是红色（非黑即红）（4）根节点为黑色（5）叶节点为黑色（6）一个节点为红色，则其两个子节点必须是黑色的（根到叶子的所有路径，不可能存在两个连续的红色节点）（7）每个节点到叶子节点的所有路径，都包含相同数目的黑色节点（相同的黑色高度）（8）以上都是红黑树的性质，其实咱们需要了解红黑树实际上是一棵不严格的平衡二叉树，大体上符合平衡二叉树，但是通过红黑节点变色的性质后，可以不严格满足平衡因子绝对值小于等于1的性质（9）这些性质十分繁琐，可以先背过来。　　9. 树-B树　　（1）为什么会产生B树呢？由于红黑树，和平衡二叉树，整体存储的数量不多，对于像数据库这种，存储大量数据，几十万几百万甚至上千万数据的情况，使用二叉树，效率也是极低的。这种结构会造成当数据量非常大时，二叉查找树的高度非常大，搜索算法从根节点向下搜索时，需要访问的节点数会变多，如果这些节点信息存储在外存储器（磁盘）中，每访问一个节点，就相当于进行了一次I/O操作，而频繁的I/O操作会降低查询的效率。要想提高效率，就要减少磁盘I/O的次数，所以我们要在磁盘页面上多存储一些信息，所以B树就是扩展每个节点的信息，降低树的高度，增加了效率。（2）B树的阶，节点的最多子节点个数。比如2-3树的阶是3，2-3-4树的阶是4。（3）在B树上，关键字集合分布在整棵树中，即叶子节点和非叶子节点都存放数据。搜索有可能在非叶子节点结束。（4）一棵m阶B树每个节点至多有m棵子树（5）除根节点外，其他分支节点至少有（ /2）棵子树；根节点至少有两棵子树（除非B树只包含一个节点），例如5阶B树，根节点可以有2个节点，但是下面的节点，最少有5/2=2.5，向上取整为3，所以其他节点至少有3个子节点（6）有个孩子节点的非叶节点有 −1个关键字，关键字按非降序排列，关键字实际就是存入的值（7）所有叶子节点具有相同的深度，这也说明B树是平衡的，B-tree的名字也是这样来的（8）在搜索B树时，访问节点（即读取磁盘）的次数与树的高度呈正比，而B树与二叉查找树相比，虽然高度都是对数级的，但是显然B树中底数比2大。因此，和二叉树相比，极大地减少了磁盘读取的次数。说人话就是，每次向下一层查找都要读取一次磁盘，而B树的层级明显比平衡二叉树要少的，因此向下查找，查询磁盘的次数肯定要小。　　10. 图论-深度优先搜索　　（1）深度优先搜索（DFS），是一种在图、搜索树和遍历中非常经典且常用的算法。其思路为用递归的方式首先延一条路线搜索到底，如果到底了还没搜索到对象，就回溯到上一层并按另一条路线再走到底，如此重复直到找到对象或者遍历完整个集合为止。（2）具体搜索路径可以如下图：

　　（3）实际也就是我写的树的前序中序后序遍历算法实际就是深度优先搜索。　　谢各位的阅读，谢谢您动动手指下
${\color{red}{赞同/喜欢}}$ ，万分感谢各位。另外以下是我之前写过的文章，感兴趣的可以点进去继续阅读。　　另外如果觉得不错，可以扫码进入我的小程序来持续新的面试题。

　　历史文章　　JAVA面试汇总（七）数据结构与算法（一）　　JAVA面试汇总（七）数据结构与算法（二）　　JAVA面试汇总（七）数据结构与算法（三）　　JAVA面试汇总（七）数据结构与算法（四）　　JAVA面试汇总（七）数据结构与算法（五）　　JAVA面试汇总（七）数据结构与算法（六）　　JAVA面试汇总（七）数据结构与算法（七）　　JAVA面试汇总（六）Spring（一）　　JAVA面试汇总（五）数据库（一）　　JAVA面试汇总（四）JVM（一）　　JAVA面试汇总（三）集合（一）　　JAVA面试汇总（二）多线程（一）　　JAVA面试汇总（一）Java基础知识（一）

二叉排序树可以是空树吗_最佳二叉排序树

相关推荐