平衡二叉树和二叉排序树的关系 平衡二叉树和二叉排序树并没有直接的关系，但是二叉排序树的查找效率与二叉树的形态有关，所有当我们希望二叉排序树的形态是均匀的时候，这样的二叉树就被称为平衡二叉树。 
1. 二叉排序树 二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。 二叉排序树定义： 二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： 若左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若右子树不空，则右子树上所有节点的值均大于它的根节点的值； 左、右子树也分别为二叉排序树。 如图下图所示就是一棵二叉排序树： 
对二叉排序树进行中序遍历，便可得到一个按关键字排序的序列，如对上图进行一次中序遍历可得到一个有序序列：10，42，45，55，58，63，67，70，83，90，98 二叉排序树的查找分析 就查找的平均时间性能而言，二叉排序树上的查找与折半查找类似，但就维护表的有序性而言，二叉排序树更高效，因为它无需移动节点，只需修改指针即可完成二叉排序树的插入和删除操作。 二叉排序树查找在在最坏的情况下，需要的查找时间取决于树的深度： 当二叉排序树接近于满二叉树时，其深度为log2nlog_2nlog2n ,因此最坏情况下的查找时间为O(log2nlog_2nlog2n)，与折半查找是同数量级的。 当二叉树如下图所示形成单枝树时，其深度为n，最坏情况下查找时间为O(n)，与顺序查找属于同一数量级。 
所以为了保证二叉排序树查找有较高的查找速度，希望该二叉树接近于满二叉树，或者二叉树的每一个节点的左、右子树深度尽量相等 2. 平衡二叉树 通过上面的分析可知，二叉排序树的查找效率与二叉树的形态有关，我们希望二叉排序树的形态是均匀的，这样的二叉树称为平衡二叉树。 平衡二叉树定义 平衡二叉树（Balanced Binary Tree），它是一棵空树，或者是具有以下性质： 它的左右两个子树的深度差的绝对值不超过1； 它的左右两个子树也分别是平衡二叉树。 将二叉树节点的左子树的深度减去它的右子树的深度称为平衡因子BF，则平衡二叉树上所有节点的平衡因子只可能是-1、0和1，如下图左边的为平衡二叉树，右边的为非平衡二叉树。 
因为平衡二叉树上任何节点的左、右子树的深度之差都不会超过1，可以证明它的深度和n个节点的完全二叉树的深度⌊log2n⌋lfloor log_2n floor⌊log2n⌋+1是同数量级的。因此，它的平均查找次数也是和⌊log2n⌋lfloor log_2n floor⌊log2n⌋+1同数量级的。 要构造一棵平衡二叉树，Georgii M. Adelson-Velskii 和 Evgenii M. Landis 提出了一种动态保持二叉平衡树的方法，其基本思想是：在构造二叉排序树的时候，每当插入一个节点时，先检查是否因插入节点而破坏了树的平衡性，如果是，则找出其中最小不平衡子树，在保持排序树的前提下，调整最小不平衡子树中各节点之间的连接关系，以达到新的平衡，所以这样的平衡二叉树简称AVL树。其中最小平衡子树是指：离插入节点最近，且平衡因子绝对值大于1的节点作为根节点的子树。 调整最小不平衡子树一般有四种情况： 单向右旋(LL型)： 插入位置为左子树的左子树，以左子树为轴心，进行单次向右旋转，如下图所示。节点旁边的数字为该节点的平衡因子，I节点为当前插入节点(如果I节点处于正中，则表示I节点既可以是左孩子也可以是右孩子。 注意LL型，以中间节点为轴心进行旋转。为什么这里I为BL左孩子不能将B-BL-I作为LL型，是因为A节点才是离I节点最近的平衡因子绝对值>1的子树，其余节点的平衡因子绝对值都没有超过1；同理当I为BL右孩子，也不能将B-BL-I作为LR型。 
2. 单向左旋(RR型)： 插入位置为右子树的右子树，右子树为轴心，进行单次向左旋转 注意RR型，以中间节点为轴心进行旋转。这里I为左右子树并不影响其实RR型，原理同上。 
3. 双向旋转先左后右(LR型)：插入位置为左子树的右子树，要进行两次旋转，先向左旋转，再向右旋转。 插入节点为左孩子：注意为什么不能B-C-I作为子树将其定为RL型，原理同RR型中的解释，对于LR型，，是以R端或者L靠近插入节点端作为旋转轴心（如下图相当于先旋转以B为根的子树后，成为了LL型，再旋转以A为根的子树）。 
插入节点为右孩子： 
4. 双向旋转先右后左(RL型)：插入位置为右子树的左子树，进行两次调整，先右旋转再左旋转；处理情况与LR类似。 插入节点为左孩子： 
插入节点为右孩子： 
经过上面的我们可以发现，平衡因子与类型有很大的关系，需要以离插入节点最近且平衡因子绝对值>1的节点作为根节点的子树进行判定是哪种类型。 练习 如下图所示，先插入节点2后，成为LL型，然后整体右旋处理后平衡。 
再依次插入8和6之后，节点5的平衡因子绝对值>1，成为RL型，所以先以5为根节点，将其子树8-6右旋（成为RR型），然后将5为根节点的整棵树再左旋。 
继续插入节点9后，节点4的平衡因子>1，成为RR型，所以以4为根节点，将整体左旋。 
以上就是平衡二叉树和二叉排序树的关系的详细内容，更多请激活谷其它相关文章！
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/75892.html
