尉世强
(青岛广播电视大学，山东青岛266012)
摘要《数据结构》是
计算机学科中一门十分重要的核心
课程，对算法的深入理解是学好该课程的关键。为了使学
生更好地理解算法，作为对课堂教学的有益补充，我们
设计开发了《AVL树算法的动态
演示》
课件，以帮助学生理解数据结
构算法。本文通过对这种交互式动态演示的设计实现过程的详细描述，着重讨论了AVL树动态演示的算法实现。
关键字AVL树；动态演示；
Java Applet
1引言
《数据结构》是计算机学科中一门十分重要的核心课程，
而对于算法的深入理解则是学好该课程的关键。本文讨论的
AVL树算法的动态演示除了考虑怎样实现在网上传输外，更
重要的是要考虑如何将抽象的算法形象生动的再现给学生，
帮助他们更加透彻的理解算法的来龙去脉。
现成的教学课件大多数是用Authorware、PowerPoint等
工具开发的，它们具有开发简单、界面友好等优点，但由于
占用存储空间很大，不适合在网上传输。而用Java语言编写
的小应用
程序(Java Applet)不仅可以具有很强的交互性，还
可以嵌入Web页中，在网上传输，从而实现真正的
网络课件。
2设计与实现
平衡二叉树(balanced binary tree或height-balanced tree
又称AVL树。它或者是一棵空树，或者是一棵具有下列性质
的二叉树：它的左子树和右子树都是平衡二叉树，且左子树
和右子树的深度之差的绝对值不超过1。
为了研究平衡二叉树的特点，我们假设二叉排序树总是
由于插入或删除结点才“失去平衡”的，现在我们只需研究
在一个平衡二叉树中插入或删除一个结点后的变化情况，以
及如果这种变化引起二叉排序树“不平衡”，怎样进行调整，
使其成为平衡二叉树。
由上述分析，我们只要对二叉排序树的插入和删除算法
做一些修改，即可实现平衡二叉树的插入和删除。
在设计该算法的动态演示的过程中，我们得到了如下的
定理：
定理：在平衡树上插入和删除一个结点后，可能会导致
二叉排序树不平衡，通过计算结点的平衡因子，如果判断出
二叉排序树已经失去平衡，此时，总能找到这样一个惟一的
结点a，它满足：
(1)它是失去平衡的最小子树的根结点。
(2)将以它为根的子树调整平衡后，整棵树即是平衡树。
3平衡二叉树的插入算法的实现
我们知道，一般情况下，假设由于在二叉排序树上插入
结点而失去平衡的最小子树的根结点指针为a(即a是离插入
结点最近，且平衡因子绝对值超过1的祖先结点)，则失去平
衡后进行调整的规律可归纳为四种情况：①LL型平衡旋转；
②RR型平衡旋转；③LR型平衡旋转；④RL型平衡旋转。
由于我们已经有了二叉排序树的插入算法，为了得到平
衡二叉树的插入算法，我们可以在这个算法的基础上做以下
三点修改：
(1)判别插入结点之后是否产生不平衡。
(2)找到失去平衡的最小子树。
(3)判别旋转类型并作相应处理。
部分代码如下：
if(((LabelledPoint)(node)).value<((LabelledPoint)(a)).value)
{
d=1；
b=a.left；
}
else
{
d=-1；
b=a.right；
}
if((a.bf>1)||(a.bf<-1))
balanced=false；
if(balanced==false)
{
if((d==1)&(b.bf==1))//LL型平衡旋转
{
rotate(super.snapshot，b)；
}
else if((d==1)&(b.bf==-1))//LR型平衡旋转
{
rotate(super.snapshot，b.Left)；
rotate(super.snapshot，b)；
}
a)else if((d==-1)&(b.bf==-1))//RR型平衡旋
转
{
rotate(super.snapshot，b)；
}
else if((d==-1)&(b.bf==1))//RL型平衡旋转
{
rotate(super.snapshot，b.Left)；
相关热词：AVL 算法 动态 演示 设计 实现
相关文章
2008-11-2
