树型结构的应用平衡查找树的研究.pdf

了 沁 摘 要 在网络和数据库飞速发展的今天，数据的查找愈来愈频繁，数据量亦愈来愈 大，采用一种有效的结构来处理这些数据也就显得非常的迫切。在数据表示方面， 树型结构因具有分支性和层次性，它成为数据表示及信息组织的基础和有力的工 具。而在数据查询方面，虽然各种排序树在插入、删除和查找操作的平均时间上 比较理想，但是在最坏的情况下，排序树退化成了一个具有单个分支的树，此时 树的高度最高，这将使这些操作的时间急剧增加。为了避免这种情况的发生，人 们引进了“平衡树”的概念。这种树在保持好的操作性质的同时，又使树的高度 尽可能的低，由于这种良好的性能，平衡树已经广泛的应用于各个领域。 本文把平衡树系统分成两个大类来进行研究，一类是平衡二叉树，另一类是 非二叉的平衡多路树。如果平衡树同时具备排序树的有序性质，它就是平衡查找 树，此时可以把他们分成平衡二叉查找树(包含AVL树、丰满树、完全二叉树、 满二叉树等)和平衡多路查找树(包含B．树、B+树、B木树、2．3—4树等)，它们 通过在不断的删除或插入操作中维持树的平衡性，来保证动态数据集合上的基本 操作在最坏情况下的时间代价仍然为0009n)。这些较好的操作性质使它们迅速 成为处理数学问题、数据库查找问题、文件检索等问题的一种有效结构。 本文在对各种平衡树进行详细的介绍、归类，对它们的各种操作和算法进行 比较和总结之后，重点研究了树及平衡树的应用，首次提出了求解迷宫问题和数 学集合问题的新思路，采用树结构不仅较好的解决了这些问题，而且比传统算法 更高效。在文章的最后还给出了平衡树在路由表和数据库索引方面的应用，以此 体现平衡树强大的查找效率。 关键词：树型结构；平衡；迷宫求解；集合；索引 IIf 《逮 Abstract anddatabaseare atfull searchis speed．Data Nowadays，network developing moreandmore andthedataamountisalso and becoming frequent bigger is todealwimthedata aneffective extremely byusing bigger．Therefore，iturgent fieldofdata tree咖ctI聪becomesthebasisand structure．Inthe expression,the forceful ofthedata andinformation foritsbranch implement expression organization and thefieldofdata timeis arrangement．In search,v撕ousorderingtrees’average in andsearch theworst idealinsertion，deletion condition