基于拆分旋转法的平衡二叉树的构建

杨金龙 李昕昕 龚勋

摘要：平衡二叉树就是对二叉排序树的一种改进，是对二叉排序树的平衡化之后的数据结构。平衡二叉树可以有效提高查找运算的速度。但是传统平衡二叉树的构建过程相对繁琐，且对于某些特定问题无法解决。因此，该文提出了一种新的平衡二叉树构建方法——拆分旋转法。实验证明，该方法切实可行，且针对有限序列的平衡二叉树构建过程明显优于传统平衡二叉树的构建。

关键词：拆分旋转法；平衡因子；二叉排序树；平衡二叉树

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）29-0003-03

1 平衡二叉树

1.1平衡二叉树的特性

在计算机科学中，二叉树（Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构，常用于高效率的搜索和排序。平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），它除了具备二叉查找树的基本特征之外，还具有一个非常重要的特点：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值（平衡因子 ） 不超过1。[1]平衡二叉查找树可用于表示有序的线性数据结构，如优先队列、关联数组、键-值的映射等。

1.2传统的构建平衡二叉树的方法

传统的构建平衡二叉树的方法是在规定一个插入序列之后，通过序列构建一棵平衡二叉树时，其中有LL型，RR型，LR型以及RL型的调整操作方法。[2]

整个实现过程是通过在一棵平衡二叉树中依次按照二叉排序树的方式插入元素，若二叉树出现不平衡状态，则根据新插入的结点与平衡因子大于1的结点的位置关系进行相应的调整。其调整方法可分为LL型、RR型、LR型和RL型4种简单调整，具体构建过程如下：

1.2.1LL型调整

由于在A的左孩子（L）的左子树（L）上插入新的结点C，使原来平衡二叉树变为不平衡状态，此时A的平衡因子由1增加至2。下面圖1是LL型的最简单调整形式。将A的左孩子B向右上方旋转，使其代替A的位置成为根结点，再将A结点向右下方旋转成为B的右子树的根结点，C则成为B结点的左子树的根结点。

1.2.2RR型调整

由于在A的右孩子（R）的左子树（R）上插入新的结点C，使原来平衡二叉树变为不平衡状态，此时A的平衡因子由-1变为-2。下面图12是RR型的最简单调整形式。将A的右孩子B向左上方旋转，使其代替A的位置成为根结点，再将A结点向左下方旋转成为B的左子树的根结点，C则成为B结点的右子树的根结点。

1.2.3LR型调整

由于在A的左孩子（L）的右子树（R）上插入新的结点C，使原来平衡二叉树变为不平衡状态，此时A的平衡因子由1增加至2。下面图3是LR型的最简单调整形式。此时的则需要进行两次旋转，先左旋转后再进行右旋转。先将A的左孩子B的右子树的根结点C向左上方旋转提升到B结点原来的位置，此时C成为A结点的左子树的根结点，B则成为C的左子树的根结点。第一次旋转之后的状态也是LL型旋转时的不平衡状，再进行一次LL型调整则变为平衡状态。

1.2.4RL型调整

由于在A的右孩子（R）的左子树（L）上插入新的结点C，使原来平衡二叉树变为不平衡状态，此时A的平衡因子由-1变为-2。下面图4是RL型的最简单调整形式。此时的则需要进行两次旋转，先右旋转后再进行左旋转。先将A的右孩子B的左子树的根结点C向右上方旋转提升到B结点原来的位置，此时C成为A结点的右子树的根结点，B则成为C的右子树的根结点。第一次旋转之后的状态也是RR型旋转时的不平衡状态，再进行一次RR型调整则变为平衡状态。

2 拆分旋转方法

2.1拆分旋转法的特点

研究发现，上述方法对于二叉树非根节点的平衡因子不平衡的状态调整适用，但对于插入结点只造成根节点的平衡因子不平衡的情况和插入结点过多的情况不适用。例如，对序列{1，2，3，4，5，6，7}构建平衡二叉树时，插入数字6时，只造成了根节点的平衡因子不平衡，而上述四种旋转方法都无法高效的进行解决。因此，本文提出了一种新的构建平衡二叉树的方法——拆分旋转法。该方法的特点是：在调整的同时，一部分结点不会参与平衡化，只有其中造成不平衡的相关结点会进行调整，并且相关结点调整方法可以直接采用递归方法进行平衡化，这种方法使用时，参与调整的结点会比传统调整方法中参与的结点更少，算法实现起来更加简单，这样的调整方法使算法的时间复杂度也相应减小。

2.2拆分旋转法的设计思路

当插入结点过多时，一般认为插入结点后二叉树深度大于等于4时，插入结点引起了二叉树的不平衡，则把插入结点到平衡因子绝对值大于等于2的结点（M结点）的路径与其他结点拆分为多个部分，再选择平衡因子绝对值大于等于2的结点到插入结点路径上的前三个结点（M，B，C），其它与这三个结点拆分开的每个部分都分别当做一个整体（E1、E2、E3......）。这三个结点必然形成LL型、RR型、LR型或者RL型的不平衡状态，然后对这三个结点进行平衡化，再把拆分开的结点整体部分（E1、E2、E3......）按照二叉排序树的插入方法插入到M，B，C三个结点平衡化之后的结构上，最终形成一棵平衡二叉树。

2.3 拆分旋转法的算法实现

3 拆分旋转法的应用

下面将通过使用拆分旋转法对关键字序列{1，2，3，4，5，6，7，8，9，10，11，12}进行二叉树构建的过程为例来对拆分旋转法的应用进行具体阐述：

（1）插入1，为根节点，平衡；插入2为1的右孩子，平衡；插入3为2的右孩子，此时不平衡，采用RR型调整方法后的二叉树为：

（2）插入4，为3的右孩子，平衡，插入5为4的右孩子，不平衡，由于插入5之后导致3的平衡因子为-2，同样属于RR型，所以采用RR型调整方法后的二叉树为：

（3）插入6，为5的右孩子，不平衡，导致根节点2的平衡因子为-2，此时采用拆分旋转方法。选取2，4，5为RR型，1，3，6为其他三个整体部分；2，4，5调整为层次遍历4，2，5；再把其他三个整体部分按照二叉排序树的方法插入即可，此时二叉树为：

（4）插入7，为6的右孩子，不平衡，此时造成5的平衡因子为-2，所以只需采用RR型调整方法此时二叉树为：

（5）插入8，为7的右孩子，平衡；插入9为8的右孩子，不平衡，与（4）的情况一致，采用同样方法调整为6的右子树的层次遍历为8，7，9，平衡；此时二叉树为：

（6）插入10，为9的右孩子，不平衡，此时导致结点关键字为6的平衡因为为-2，情况同（3），也采用拆分旋转方法对二叉树平衡化，得到平衡二叉树后插入11，为10的右孩子，不平衡，此时同（4）的情况一致，采用同样方法调整为8的右子树根节点为10，10的左孩子为9，右孩子为11，平衡。此时二叉树为：

（7）插入12，位11的右孩子，不平衡，此時二叉树根节点4的平衡因子为-2，采用拆分旋转方法，把4，8，10三个结点看作RR型部分，4的左子树看作一个部分（E1），8的左子树看作一个部分（E2），10的左子树看作一个部分（E3），10的右子树看作一个部分（E4），此时RR型部分旋转调整为根为8，左孩子为4，右孩子为10的二叉树，再把E1、E2、E3、E4四个部分按照二叉排序树的方法插入到RR型部分调整后的二叉树上，此时平衡二叉树为：

4 结论

本文针对传统的平衡二叉树构建过程中存在的对于插入结点只造成根节点的平衡因子不平衡而无法构建的问题和插入结点过多而无法构建的问题进行了详细讨论，并给出了解决方案，即平衡二叉树的拆分旋转构建法。实验证明，该方法对于有限序列甚至一些特殊序列构建平衡二叉树非常适用。

参考文献：

[1]朱洪浩. 数据结构中平衡二叉树的教学探讨与研究[J]. 赤峰学院学报（自然科学版），2012，28（5）：19-21.

[2]严蔚敏， 吴伟民. 数据结构（C 语言版）[M]. 北京：清华大学出版社， 1997.233-238.

[3]朱宇， 张红彬. 平衡二叉树的选择调整算法.中国科学院研究生院，2006， 23（4）：527-533

[4]William Ford， William Topt. Data Structures with C++.Beijing：Tsinghua University Press，1997.721-728

[5]Clifford A，Shaffer. A Practical Introduction to Data Structures and Algorithm Analysis （C++ Edition）（2nd ed.）.Beijing ：Publishing House ofElectroni cs Industry， 2002.280.

【通联编辑：王力】