AVL树算法的动态演示的设计与实现

　  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=; }

　　else { d=-1; b=; } if((>1)||(<-1)) balanced=false;

　　if (balanced==false)

　　{ if((d==1)&(==1)) //ll型平衡旋转 { rotate(ot， b); }

　　else if((d==1)&(==-1)) //lr型平衡旋转 { rotate(ot， );

　　rotate(ot， b); }

　　a) else if((d==-1)&(==-1)) //rr型平衡旋转

　　{ rotate(ot， b); } else if((d==-1)&(==1)) //rl型平衡旋转

　　{ rotate(ot， );

　　rotate(ot， b); } } …

　　4　平衡二叉树的删除算法的实现

　　平衡二叉树的删除主要是如何找到失去平衡的最小子树的根结点a，我们设计了如下算法：

　　(1)通过周游计算各结点的平衡因子。

　　(2)从根结点开始按如下方法扫描。 部分代码如下：

　　if (balanced==false) { n("删除结点导致二叉排序树不平衡，准备进行调整.");

　　briefpause(); n("先判断平衡旋转类型.");

　　briefpause();

　　if(==2) { d=1; b=; } else if (==-2) { d=-1; b=; }

　　if((d==1)&(!=-1)) //ll型平衡旋转 { n("ll型平衡旋转");

　　rotate(ot， b); }

　　else if((d==1)&(==-1)) //lr型平衡旋转 { n("lr型平衡旋转");

　　rotate(ot， );

　　briefpause(); rotate(ot， ); }

　　else if((d==-1)&(!=1)) //rr型平衡旋转 { n("rr型平衡旋转");

　　rotate(ot， b);

　　}

　　else if((d==-1)&(==1)) //rl型平衡旋转

　　{ n("rl型平衡旋转");

　　rotate(ot， );
        briefpause(); rotate(ot， ); } } }

　　5　平衡二叉树的查找算法的实现

　　由于平衡二叉树的查找操作不会使其“失去平衡”，故其查找算法与二叉排序树的查找算法完全相同，在此不再赘述。

　　参考文献

　　[1] 许卓群 张乃孝 杨冬青 唐世渭 数据结构 1987年

　　[2] 严蔚敏 吴伟民 数据结构 1992年

　　[3] 印旻 java语言与面向对象程序设计 2000年

　　[4] david java 2图形设计(卷ⅰ awt) 2000年

　　[5] david java 2图形设计(卷ⅱ swing) 2000年

　　[6] clayton walnum 看实例学java 1997年 [7] d.m.吉瑞 a.l.麦克莱伦 java图形设计 1997年

本文链接：http://www.qk112.com/lwfw/jsjlw/jisuanjiyingyong/245568.html