今天是：  | 网站首页 | 名校推荐 | 小学试卷 | 初中试卷 | 高中试卷 | 免费课件 | 免费教案 | 如何获点 | 
  | 教育教学 | 免费论文 | 网站留言 | 
您现在的位置： 名校试卷网 >> 工商管理 >> 市场营销 >> 正文 用户登录 新用户注册
AVL树算法的动态演示的设计与实现           ★★★ 【字体：小 大】
AVL树算法的动态演示的设计与实现
作者：佚名    论文来源：本站原创    点击数：    更新时间：2008-10-7    
摘  要　《数据结构》是计算机学科中一门十分重要的核心课程，对算法的深入理解是学好该课程的关键。为了使学生更好地理解算法，作为对课堂教学的有益补充，我们设计开发了《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)；
         rotate(super.snapshot， b)；
}
}
…

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

    平衡二叉树的删除主要是如何找到失去平衡的最小子树的根结点a，我们设计了如下算法：
    (1)通过周游计算各结点的平衡因子。
    (2)从根结点开始按如下方法扫描。
部分代码如下：
if (balanced==false)
{
   super.panel.caption("删除结点导致二叉排序树不平衡，准备进行调整.")；
  briefPause()；
   super.panel.caption("先判断平衡旋转类型.")；
  briefPause()；
    if(a.bf==2)
   {
     d=1；
     b=a.left；
    }
  else if (a.bf==-2){
  d=-1；
  b=a.right；
  }
   if((d==1)&(b.bf!=-1))  //LL型平衡旋转
    {
         super.panel.caption("LL型平衡旋转")；
         rotate(super.snapshot， b)；
    }
   else if((d==1)&(b.bf==-1))  //LR型平衡旋转
    {
         super.panel.caption("LR型平衡旋转")；
         rotate(super.snapshot， b.right)；
          briefPause()；
         rotate(super.snapshot， a.left)；
    }
   else if((d==-1)&(b.bf!=1)) //RR型平衡旋转
   {
         super.panel.caption("RR型平衡旋转")；
         rotate(super.snapshot， b)；
    }
   else if((d==-1)&(b.bf==1))  //RL型平衡旋转
    {
         super.panel.caption("RL型平衡旋转")；
          rotate(super.snapshot， b.left)；
          briefPause()；
          rotate(super.snapshot， a.right)；
}
  }
}

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

    由于平衡二叉树的查找操作不会使其“失去平衡”，故其查找算法与二叉排序树的查找算法完全相同，在此不再赘述。
论文录入：guoxingxing    责任编辑：guoxingxing 
  • 上一篇论文：

  • 下一篇论文：
    • 【发表评论】【加入收藏】【告诉好友】【打印此文】【关闭窗口】
    　　网友评论：（只显示最新10条。评论内容只代表网友观点，与本站立场无关！）
    Copyright © 2003-2009 www.51shijuan.com All Rights Reserved.
    名校试卷网　版权所有 武汉明思教育咨询有限公司 公司注册号：420111000026640
    客服热线：13554027304 客服QQ:595216475 912259353 Email:51shijuan@163.com
    公司地址：武汉市洪山区珞瑜路1号鹏程国际 鄂ICP备07013297号
    建议浏览分辨率：1024*768