⼆叉排序树和平衡⼆叉树
1. ⼆叉排序树
⼆叉排序树（Binary Sort Tree），⼜称⼆叉查树（Binary Search Tree），亦称⼆叉搜索树。
⼆叉排序树定义：
⼆叉排序树或者是⼀棵空树，或者是具有下列性质的⼆叉树：
二叉树定义1. 若左⼦树不空，则左⼦树上所有节点的值均⼩于它的根节点的值；
2. 若右⼦树不空，则右⼦树上所有节点的值均⼤于它的根节点的值；
3. 左、右⼦树也分别为⼆叉排序树。
如图下图所⽰就是⼀棵⼆叉排序树：
对⼆叉排序树进⾏中序遍历，便可得到⼀个按关键字排序的序列，如对上图进⾏⼀次中序遍历可得到⼀个有序序列：
10，42，45，55，58，63，67，70，83，90，98
⼆叉排序树的查分析
就查的平均时间性能⽽⾔，⼆叉排序树上的查与折半查类似，但就维护表的有序性⽽⾔，⼆叉排序树更⾼效，因为它⽆需移动节点，只需修改指针即可完成⼆叉排序树的插⼊和删除操作。
⼆叉排序树查在在最坏的情况下，需要的查时间取决于树的深度：
1. 当⼆叉排序树接近于满⼆叉树时，其深度为 ，因此最坏情况下的查时间为O()，与折半查是同数量级的。
2.
当⼆叉树如下图所⽰形成单枝树时，其深度为n，最坏情况下查时间为O(n)，与顺序查属于同⼀数量级。
所以为了保证⼆叉排序树查有较⾼的查速度，希望该⼆叉树接近于满⼆叉树，或者⼆叉树的每⼀个节点的左、右⼦树深度尽量相等
2. 平衡⼆叉树通过上⾯的分析可知，⼆叉排序树的查效率与⼆叉树的形态有关，我们希望⼆叉排序树的形态是均匀的，这样的⼆叉树称为平衡⼆叉树。
平衡⼆叉树定义
平衡⼆叉树（Balanced Binary Tree），它是⼀棵空树，或者是具有以下性质：
1. 它的左右两个⼦树的深度差的绝对值不超过1；
2. 它的左右两个⼦树也分别是平衡⼆叉树。
log n 2log n 2
将⼆叉树节点的左⼦树的深度减去它的右⼦树的深度称为平衡因⼦BF，则平衡⼆叉树上所有节点的平衡因⼦只可能是-1、0和1，如下图左
边的为平衡⼆叉树，右边的为⾮平衡⼆叉树。
因为平衡⼆叉树上任何节点的左、右⼦树的深度之差都不会超过1，可以证明它的深度和n个节点的完全⼆叉树的深度+1是同数量级的。因此，它的平均查次数也是和+1同数量级的。
要构造⼀棵平衡⼆叉树，Georgii M. Adelson-Velskii 和 Evgenii M. Landis 提出了⼀种动态保持⼆叉平衡树的⽅法，其基本思想是：在构造⼆叉排序树的时候，每当插⼊⼀个节点时，先检查是否因插⼊节点⽽破坏了树的平衡性，如果是，则出其中最⼩不平衡⼦树，在保持排序树的前提下，调整最⼩不平衡⼦
树中各节点之间的连接关系，以达到新的平衡，所以这样的平衡⼆叉树简称AVL树。其中最⼩平衡⼦树是指：离插⼊节点最近，且平衡因⼦绝对值⼤于1的节点作为根节点的⼦树。
调整最⼩不平衡⼦树⼀般有四种情况：
1. 单向右旋(LL型)： 插⼊位置为左⼦树的左⼦树，以左⼦树为轴⼼，进⾏单次向右旋转，如下图所⽰。节点旁边的数字为该节点的平衡
因⼦，I节点为当前插⼊节点(如果I节点处于正中，则表⽰I节点既可以是左孩⼦也可以是右孩⼦。
注意LL型，以中间节点为轴⼼进⾏旋转。为什么这⾥I为BL左孩⼦不能将B-BL-I作为LL型，是因为A节点才是离I节点最近的平衡因⼦绝对值
>1的⼦树，其余节点的平衡因⼦绝对值都没有超过1；同理当I为BL右孩⼦，也不能将B-BL-I作为LR型。
2. 单向左旋(RR型)： 插⼊位置为右⼦树的右⼦树，右⼦树为轴⼼，进⾏单次向左旋转
⌊log n ⌋2⌊log n ⌋2
注意RR型，以中间节点为轴⼼进⾏旋转。这⾥I为左右⼦树并不影响其实RR型，原理同上。
3. 双向旋转先左后右(LR型)：插⼊位置为左⼦树的右⼦树，要进⾏两次旋转，先向左旋转，再向右旋转。
插⼊节点为左孩⼦：注意为什么不能B-C-I作为⼦树将其定为RL型，原理同RR型中的解释，对于LR型，，是以R端或者L靠近插⼊节点端作为旋转轴⼼（如下图相当于先旋转以B为根的⼦树后，成为了LL型，再旋转以A为根的⼦树）。
插⼊节点为右孩⼦：
4. 双向旋转先右后左(RL型)：插⼊位置为右⼦树的左⼦树，进⾏两次调整，先右旋转再左旋转；处理情况与LR类似。
插⼊节点为左孩⼦：
插⼊节点为右孩⼦：
经过上⾯的我们可以发现，平衡因⼦与类型有很⼤的关系，需要以离插⼊节点最近且平衡因⼦绝对值>1的节点作为根节点的⼦树进⾏判定是哪种类型。
练习
如下图所⽰，先插⼊节点2后，成为LL型，然后整体右旋处理后平衡。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。