平衡二叉树及调整

平衡二叉树
1.平衡二叉树定义

平衡二叉树或者是一棵空树，或者是具有下列性质的二叉排序树：它的左子树和右子树都是平衡二叉树，且左子树和右子树高度之差的绝对值不超过 1。

2.平衡二叉树的四种调整方式

在平衡二叉树上插入或删除结点后，可能使树失去平衡，因此，需要对失去平衡的树进行平衡化调整。设 a 结点为失去平衡的最小子树根结点，对该子树进行平衡化调整归纳起来
有以下四种情况：

（1）左单调整

图(a)为插入前的子树。其中，B 为结点 a 的左子树，D、E 分别为结点 c 的左右子树，B、D、E 三棵子树的高均为 h。图(a)所示的子树是平衡二叉树。
在图(a)所示的树上插入结点 x，如图(b)所示。结点 x 插入在结点 c 的右子树 E 上，导致结点 a 的平衡因子绝对值大于 1，以结点 a 为根的子树失去平衡。
调整策略：调整后的子树除了各结点的平衡因子绝对值不超过 1，还必须是二叉排序树。
由于结点 c 的左子树 D 可作为结点 a 的右子树，将结点 a 为根的子树调整为左子树是 B，右子树是 D，再将结点 a 为根的子树调整为结点 c 的左子树，结点 c 为新的根结点，如图(c)。
平衡化调整操作判定：沿插入路径检查三个点 a、c、E，若它们处于“\”直线上的同一个
方向，则要作左单旋转，即以结点 c 为轴逆时针旋转。
（2）右单调整
右单旋转与左单旋转类似，沿插入路径检查三个点 a、c、E，若它们处于“/”直线上的同一个方向，则要作右单旋转，即以结点 c 为轴顺时针旋转，如图所示。

（3）先左后右双向旋转

第一图为插入前的子树，根结点 a 的左子树比右子树高度高 1，待插入结点 x 将插入到结点 b 的右子树上，并使结点 b 的右子树高度增 1，从而使结点 a 的平衡因子的绝对值大于 1，导致结点 a 为根的子树平衡被破坏，如图所示。

沿插入路径检查三个点 a、b、c，若它们呈“<”字形，需要进行先左后右双向旋转：
①首先，对结点 b 为根的子树，以结点 c 为轴，向左逆时针旋转，结点 c 成为该子树的新根，如图(b、e)；
②由于旋转后，待插入结点 x 相当于插入到结点 b 为根的子树上，这样 a、c、b 三点处于“/”直线上的同一个方向，则要作右单旋转，即以结点 c 为轴顺时针旋转，如图(c、f)。
（4）先右后左双向旋转
先右后左双向旋转和先左后右双向旋转对称，在此不再赘述。
3.平衡树的查找分析
在平衡树上进行查找的过程和二叉排序树相同，因此，在查找过程中和给定值进行比较
的关键码个数不超过树的深度。在平衡树上进行查找的时间复杂度为 O(logn)。