基于旋转的平衡二叉排序树上插入的实现

曾祥师 王悦 雷甜甜

摘要：创建平衡二叉排序树可采用不少种方法。对于教材中采用的旋转法，在实际教学中常常引起初学者的疑惑。为了解决这个问题，该文提出了一种更为简单的平衡二叉排序树方法，与教材中的旋转法相比，本算法简单易被理解，有较大的推广和应用价值。

关键词：平衡二叉排序树;平衡因子;二叉树的平衡化

中图分类号：TP3        文献标识码：A

文章编号：1009-3044（2019）17-0003-02

开放科学（资源服务）标识码（OSID）：

Abstract： There are many methods for balanced binary tree sorting. For the teaching materials used in the rotation method， in practical teaching often caused confusion for beginners. In order to solve this problem， this paper proposes a more simple balanced binary sort tree method. Compared with the rotation method in the textbook， this algorithm is simple and easy to understand， and has great promotion and application value.

Key words： balanced binary sort tree; equilibrium factor; equilibrium of binary trees

現行的数据结构教材中，创建平衡二叉排序树方法是通过顺时针、逆时针的旋转把原非平衡的二叉树变为平衡二叉树。此种方法旋转次数，旋转方向因不同的问题而不同，虽然在理论上严谨，但对初学者来说理解起来颇为困难。针对这一问题，本文提出了一种更为简单的平衡二叉排序树方法，这种方法不需要进行旋转平衡，更容易理解。不仅对于初学者，还是作为教学中的一种尝试，都有着积极的意义。

1 基本原理

1.1 基本概念

1.1.1  平衡二叉排序树

平衡二叉排序树的左、右子树高度之差的绝对值不超过 1，并且左、右子树都是平衡二叉排序树。空树也是平衡二叉排序树。

1.1.2  平衡因子

平衡因子是左子树的高度减去右子树的高度差也即深度差。因此，所有结点的均衡因子是-1，0，1的二叉树，是平衡二叉排序树。

1.1.3  最小不平衡子树

最小不平衡子树是指具有以下属性作为根的节点的子树：最接近插入节点的祖先节点，并且平衡因子不是-1，0，1。

1.2 平衡调整算法

1.2.1 算法的基本思想

重新插入结点向根算平衡因子，将离新插入结点最近的不平衡结点标为A，顺向新插入结点方向标注B，C调整，分以下4种情况（新插入结点相对于不平衡结点A的位置）

1.2.3 算法的正确性

调整为平衡二叉树后，中序遍历对关键字进行了有序排列，它可以维持二叉排序树原有的性质。与此同时，不管任何一种情况，在调整后，都能确保根的新子树与原来的相同。因此，当平衡的二叉排序树引入新的结点而失去平衡时，只需要平衡最小不平衡子树。

1.2.4 算法的复杂度

假设平衡二叉数有n个结点，平衡二叉排序树的n个结点的深度为[log2n]，插入结点时的数量级为n的对数阶，故其时间复杂度为 O（[log2n]）。在寻找新结点的插入位置时，就能选择寻找最小的不平衡子树，故查找最小不平衡子树的时间复杂度与插入结点的时间复杂度相等也为O（[log2n]）。

2 实例及其调整图示

3结束语

该算法的源代码程序已在Visual C++ 6.0运行成功。算法条理清晰，深受同学们喜爱，因此取得了较好的学习效果。二叉排序树平衡化可采用的方法中，本方法有一定的优势。对它的准确掌握可以对后续的学习起到非常好的推动作用。由实践可以表明，本文采用的简单调整平衡算法要比教材中的旋转法更易被接受。

参考文献：

[1] 严蔚敏，李冬梅，吴伟民. 数据结构（C语言版第2版）[M].北京：人民邮电出版社，2014.

[2] 张标汉.平衡二叉树调整教学探讨[J].教育与教学研究，2009.

[3] 张冰川.平衡二叉排序树的平衡调整简单算法[J].科技广场，2007.

【通联编辑：代影】