平衡二叉树调整教学探讨

张标汉

文章编号：1672-5913(2009)10-0051-02

摘要：平衡二叉树教学中传统的旋转方法不太容易被学生理解，针对这一问题，本文通过分析二叉排序树的基本原理，摸索出一种在教学实践中更加容易被学生理解的平衡二叉树调整方法。

关键词：二叉排序树 平衡二叉树 教学探讨

中图分类号：G642

文献标识码：B

在“数据结构与算法”课程教学中，许多教科书在介绍平衡二叉树调整这部分内容时，采用的都是旋转的方法，将不平衡二叉树用左右、顺逆时针旋转的方法使失去平衡的二叉排序树调整为平衡二叉树。但是在实际教学过程中，笔者发现这样的方法不太容易被学生理解，许多学生尤其是专科学生搞不清楚怎么旋转、围绕谁旋转。针对这一问题，笔者通过不断的教学实践摸索出一种更容易被学生接受和理解的平衡二叉树调整方法——填空法，这种方法充分利用了二叉排序树的特点，采用填空的方式对失衡的二叉排序树进行调整使之保持平衡。

1基本原理

我們知道，二叉排序树具有这样一个特点：左子树上所有结点的值均小于它的根结点的值，右子树上所有结点的值均大于它的根结点的值。即有这样一个关系：左<根<右。利用这个特点，当我们在插入结点使得原平衡二叉树失去平衡而需要进行调整时，首先寻找最小不平衡子树。最小不平衡子树的寻找方法是：从插入的结点出发，依次计算其祖先的平衡因子，发现的第一个平衡因子的绝对值大于1的结点就是最小不平衡子树的根结点，则以它为根结点的子树就是最小不平衡子树。先考虑最简单的情况，这棵最小不平衡子树仅由三个结点构成。此时最小不平衡子树可以分为四种基本类型，分别是：LL型、LR型、RL型和RR型。如图1所示：

在教科书中，这四种情况是分别讨论的：对LL型做一次顺时针旋转，对LR型先逆时针旋转后顺时针旋转，对RL型先顺时针旋转后逆时针旋转，对RR型做一次逆时针旋转。但应用填空法，这四种基本情况的调整可以统一在一起：

可以知道，要使得由三个结点构成的二叉排序树平衡，其基本结构必定是一个结点作为根结点，一个作为左孩子结点，一个作为右孩子结点。如图2所示：

根据二叉排序树的特点(左<根<右)，我们只要把上述每种基本情况中的三个结点按值从小到大排列，将最小的一个填在左孩子结点位置，最大的一个填在右孩子结点位置，中间的填在根结点位置。很容易地就可以将上述四种最小不平衡子树调整为平衡二叉树，如图3所示：

进一步考虑更为复杂的情况，假定上述结点各自还有左右子树，我们仍然可以使用我们的填空法轻松的加以调整。这四种复杂情况如图4所示：

假定都在CL中插入一个结点使得A的平衡因子的绝对值变为2从而使得原平衡二叉树失去平衡，此时以A为根结点的子树就是最小不平衡子树，这棵最小不平衡子树可以分为7个部分。沿着从根结点A到插入结点位置CL的路径方向依次取三个结点，假设为A、B、C，它们和剩下的AL、AR、BL、BR、CL、CR中的4个构成的二叉排序树要成为平衡二叉树，则由这7个部分组成的平衡二叉树的基本结构一定是如图5所示情形：

其中，A、B、C三者中值最小的为左子树的根结点，值最大的为右子树的根结点，中间的为整个最小不平衡子树的根结点。其余的AL、AR、BL、BR、CL、CR等按从小到大的顺序排列，将它们从左到右依次填在树的第三层即可，完成后的二叉树一定是平衡二叉树。对上述四种复杂情形，平衡后如图6所示：

2示例

例：已知长度为12的表：{Jan,Feb,Mar,Apr,May,June, July,Aug,Sep,Oct,Nov,Dec}，按照表中元素顺序构造一棵平衡二叉排序树。

解：构造过程如图7、图8所示。

教学实践证明，本文采用的填空法要比传统的旋转法更容易被学生接受和理解。

参考文献：

[1] 严蔚敏,吴伟民. 数据结构(C语言版)[M]. 北京:清华大学出版社,1997.

[2] 马秋菊. 数据结构(C语言描述)[M]. 北京:中国水利水电出版社,2006.

Discussion on Teaching of Balancing the Binary Tree

ZHANG Biao-han

(The Department of Maths & Computer Science, Sanming College, Sanming 365004, China)

Abstract:The rotation method for balanced binary tree is not easy to understand by the students, This paper introduced a new method using the characteristics of the binary sort tree that is easier to understand by the students.

Key words:binary sort tree; balanced binary tree; teaching discussion