在网络和数据库飞速发展的今天,数据的查找愈来愈频繁,数据量亦愈来愈大,采用一种有效的结构来处理这些数据也就显得非常的迫切。在数据表示方面,树型结构因具有分支性和层次性,它成为数据表示及信息组织的基础和有力的工具。而在数据查询方面,虽然各种排序树在插入、删除和查找操作的平均时间上比较理想,但是在最坏的情况下,排序树退化成了一个具有单个分支的树,此时树的高度最高,这将使这些操作的时间急剧增加。为了避免这种情况的发生,人们引进了“平衡树”的概念。这种树在保持好的操作性质的同时,又使树的高度尽可能的低,由于这种良好的性能,平衡树已经广泛的应用于各个领域。本文把平衡树系统分成两个大类来进行研究,一类是平衡二叉树,另一类是非二叉的平衡多路树。如果平衡树同时具备排序树的有序性质,它就是平衡查找树,此时可以把他们分成平衡二叉查找树(包含AVL树、丰满树、完全二叉树、满二叉树等)和平衡多路查找树(包含B-树、B+树、B*树、2-3-4树等),它们通过在不断的删除或插入操作中维持树的平衡性,来保证动态数据集合上的基本操作在最坏情况下的时间代价仍然为O(logn)。这些较好的操作性质使它们迅速成为处理数学问题、数据库查找问题、文件检索等问题的一种有效结构。本文在对各种平衡树进行详细的介绍、归类,对它们的各种操作和算法进行比较和总结之后,重点研究了树及平衡树的应用,首次提出了求解迷宫问题和数学集合问题的新思路,采用树结构不仅较好的解决了这些问题,而且比传统算法更高效。在文章的最后还给出了平衡树在路由表和数据库索引方面的应用,以此体现平衡树强大的查找效率。