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

《avl树算法的动态演示的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、从本学科出发，应着重选对国民经济具有一定实用价值和理论意义的课题。课题具有先进性，便于研究生提出新见解，特别是博士生必须有创新性的成果AVL树算法的动态演示的设计与实现摘要　《数据结构》是计算机学科中一门十分重要的核心课程，对算法的深入理解是学好该课程的关键。为了使学生更好地理解算法，作为对课堂教学的有益补充，我们设计开发了《AVL树算法的动态演示》课件，以帮助学生理解数据结构算法。本文通过对这种交互式动态演示的设计实现过程的详细描述，着重讨论了AVL树动态演示的算法实现。关键字　AVL树；动态演示；JavaApplet《数据结构》是计算机学科中

2、一门十分重要的核心课程，而对于算法的深入理解则是学好该课程的关键。本文讨论的AVL树算法的动态演示除了考虑怎样实现在网上传输外，更重要的是要考虑如何将抽象的算法形象生动的再现给学生，帮助他们更加透彻的理解算法的来龙去脉。现成的教学课件大多数是用Authorware、PowerPoint等工具开发的，它们具有开发简单、界面友好等优点，但由于占用存储空间很大，不适合在网上传输。而用Java语言编写的小应用程序(JavaApplet)不仅可以具有很强的交互性，还可以嵌入Web页中，在网上传输，从而实现真正的网络课件。平衡二叉树(balancedbina

3、rytree或hEight-balancedtree)又称AVL树。它或者是一棵空树，或者是一棵具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。课题份量和难易程度要恰当，博士生能在二年内作出结果，硕士生能在一年内作出结果，特别是对实验条件等要有恰当的估计。从本学科出发，应着重选对国民经济具有一定实用价值和理论意义的课题。课题具有先进性，便于研究生提出新见解，特别是博士生必须有创新性的成果为了研究平衡二叉树的特点，我们假设二叉排序树总是由于插入或删除结点才“失去平衡”的，现在我们只需研究在一个平衡

4、二叉树中插入或删除一个结点后的变化情况，以及如果这种变化引起二叉排序树“不平衡”，怎样进行调整，使其成为平衡二叉树。由上述分析，我们只要对二叉排序树的插入和删除算法做一些修改，即可实现平衡二叉树的插入和删除。在设计该算法的动态演示的过程中，我们得到了如下的定理：定理：在平衡树上插入和删除一个结点后，可能会导致二叉排序树不平衡，通过计算结点的平衡因子，如果判断出二叉排序树已经失去平衡，此时，总能找到这样一个惟一的结点a，它满足：(1)它是失去平衡的最小子树的根结点。(2)将以它为根的子树调整平衡后，整棵树即是平衡树。我们知道，一般情况下，假设由于在

5、二叉排序树上插入结点而失去平衡的最小子树的根结点指针为a(即a是离插入结点最近，且平衡因子绝对值超过1的祖先结点)，则失去平衡后进行调整的规律可归纳为四种情况：①LL型平衡旋转；②RR型平衡旋转；③LR型平衡旋转；④RL型平衡旋转。由于我们已经有了二叉排序树的插入算法，为了得到平衡二叉树的插入算法，我们可以在这个算法的基础上做以下三点修改：(1)判别插入结点之后是否产生不平衡。(2)找到失去平衡的最小子树。(3)判别旋转类型并作相应处理。部分代码如下：if(((LabelledPoint)(node)).value课题份量和难易程度要恰当，博士生

6、能在二年内作出结果，硕士生能在一年内作出结果，特别是对实验条件等要有恰当的估计。从本学科出发，应着重选对国民经济具有一定实用价值和理论意义的课题。课题具有先进性，便于研究生提出新见解，特别是博士生必须有创新性的成果{d=1；b=；}else{d=-1；b=；}if((d==1)&(!=-1))//LL型平衡旋转{("LL型平衡旋转")；rotate(，b)；}elseif((d==1)&(==-1))//LR型平衡旋转{("LR型平衡旋转")；rotate(，)；briefPause()；rotate(，)；}elseif((d==-1)&(!=

7、1))//RR型平衡旋转{("RR型平衡旋转")；rotate(，b)；}elseif((d==-1)&(==1))//RL型平衡旋转{("RL型平衡旋转")；rotate(，)；briefPause()；rotate(，)；}}}由于平衡二叉树的查找操作不会使其“失去平衡”，故其查找算法与二叉排序树的查找算法完全相同，在此不再赘述。课题份量和难易程度要恰当，博士生能在二年内作出结果，硕士生能在一年内作出结果，特别是对实验条件等要有恰当的估计。