高度平衡的二叉搜索树的判定与调整
开篇：润墨网以专业的文秘视角，为您筛选了一篇高度平衡的二叉搜索树的判定与调整范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：建立高度平衡的二叉搜索树是为了提高二叉搜索树的效率，减少树的平均搜索长度。为此，向二叉搜索树中每插入一个新结点时要调整树的结构，使二叉搜索树保持平衡，从而使得其高度保持在O(log2n)，平均搜索长度也可保持在O(log2n)。
中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)14-20912-02
1 高度平衡的二叉搜索树及其平衡判定
高度平衡的二叉搜索树（又称AVL树）：一棵AVL树或者是空树，或者是具有下列性质的二叉搜索树：它的左子树和右子树都是AVL树，且左子树和右子树的高度之差的绝对值不超过1。
结点的平衡因子：结点右子树的高度减去左子树的高度所得的高度差。
根据AVL树的定义，任一结点的平衡因子只能取-1，0和1。如果一个结点的平衡因子的绝对值大于1，则这棵二叉搜索树就失去了平衡，不再是AVL树。
2 平衡的二叉搜索树的失衡与调整
如果在一棵平衡的二叉搜索树中插入一个新结点，造成了不平衡。此时必须调整树的结构，使之平衡化。
平衡化旋转有两类：单旋转(左旋和右旋)和双旋转(左平衡和右平衡)。
每插入一个新结点时，AVL树中相关结点的平衡状态会发生改变。因此，在插入一个新结点后，需要从插入位置沿通向根的路径回溯，检查各结点的平衡因子(左、右子树的高度差)。如果在某一结点发现高度不平衡，停止回溯。
从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。
如果这三个结点处于一条直线上，则采用单旋转进行平衡化。单旋转可按其方向分为左单旋转和右单旋转，其中一个是另一个的镜像，其方向与不平衡的形状相关。
如果这三个结点处于一条折线上，则采用双旋转进行平衡化。双旋转分为先左后右和先右后左两类。
2.1 左单旋转(RotateLeft)
在插入新结点之前AVL树的形状如图4(a)所示。图中大写字母用来指明结点，矩形框表示结点的子树，其中的字母h给出子树的高度。若h=-1，则B，C和D都是空指针；若h≥0，则这三个结点在树中实际存在，是平衡的二叉搜索树。如果在子树E中插入一个新结点，该子树高度增1导致结点A的平衡因子变成+2，出现不平衡。沿插入路径检查三个结点A、C和E。它们处于一条方向为“\”的直线上，需要做左单旋转。以结点C为旋转轴，让结点A反时针旋转。
2.2 右单旋转(RotateRight)
如果一棵AVL树如图5(a)所示，在左子树D上插入新结点使其高度增1，导致结点A的平衡因子增到-2，造成了不平衡。为使树恢复平衡，从A沿插入路径连续取3个结点A、B和D，它们处于一条方向为“/”的直线上，需要做右单旋转。以结点B为旋转轴，将结点A顺时针旋转。
2.3 先左后右双旋转(RotationLeftRight)
双旋转总是考虑三个结点。在图6(a)的子树的F或G中插入新结点，该子树的高度增1。结点A的平衡因子变为-2，发生了不平衡。从结点A起沿插入路径选取3个结点A、B和E，它们位于一条形如“á”的折线上，因此需要进行先左后右的双旋转。
首先以结点E为旋转轴，将结点B反时针旋转，以E代替原来B的位置，做左单旋转。再以结点E为旋转轴，将结点A顺时针旋转，做右单旋转。使之平衡化。
2.4 先右后左双旋转 (RotationRightLeft)
右左双旋转是左右双旋转的镜像。
在下图（a）的在子树F或G中插入新结点，该子树高度增1。结点A的平衡因子变为2，发生了不平衡。 从结点A起沿插入路径选取3个结点A、C和D，它们位于一条形如“〉”的折线上，需要进行先右后左的双旋转。
首先做右单旋转：以结点D为旋转轴，将结点C顺时针旋转，以D代替原来C的位置。再做左单旋转：以结点D为旋转轴，将结点A反时针旋转，恢复树的平衡。
3 结束语
二叉搜索树适合于组织在内存中的较小的索引（或目录）。对于存放在外存中较大的文件系统，用二叉搜索树来组织索引就不太合适了。若以结点这内外存交换的单位，则在搜索过程中为找到所需的关键码，需对外存进行log2n次访问，这是很费时的。因此在文件检索系统中大量使用的是用B树或B+树做文件索引。
参考文献：
[1] D E 克努特.管纪文,译.计算机程序设计技巧3[M].北京:国防工业出版社,1999:185-190.
[2] 许卓群.数据结构[M].北京:高等教育出版社,1993:103-108.
[3] 严蔚敏.数据结构[M].北京:清华大学出版社,2004:207-215.
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文