樹型結構的應用與平衡查找樹的研究.pdf

1、在網(wǎng)絡和數(shù)據(jù)庫飛速發(fā)展的今天，數(shù)據(jù)的查找愈來愈頻繁，數(shù)據(jù)量亦愈來愈大，采用一種有效的結構來處理這些數(shù)據(jù)也就顯得非常的迫切。在數(shù)據(jù)表示方面，樹型結構因具有分支性和層次性，它成為數(shù)據(jù)表示及信息組織的基礎和有力的工具。而在數(shù)據(jù)查詢方面，雖然各種排序樹在插入、刪除和查找操作的平均時間上比較理想，但是在最壞的情況下，排序樹退化成了一個具有單個分支的樹，此時樹的高度最高，這將使這些操作的時間急劇增加。為了避免這種情況的發(fā)生，人們引進了“平衡樹”的概

2、念。這種樹在保持好的操作性質的同時，又使樹的高度盡可能的低，由于這種良好的性能，平衡樹已經(jīng)廣泛的應用于各個領域。
　　 本文把平衡樹系統(tǒng)分成兩個大類來進行研究，一類是平衡二叉樹，另一類是非二叉的平衡多路樹。如果平衡樹同時具備排序樹的有序性質，它就是平衡查找樹，此時可以把他們分成平衡二叉查找樹（包含AVL樹、豐滿樹、完全二叉樹、滿二叉樹等）和平衡多路查找樹（包含B-樹、B+樹、B*樹、2-3-4樹等），它們通過在不斷的刪除或插入操

3、作中維持樹的平衡性，來保證動態(tài)數(shù)據(jù)集合上的基本操作在最壞情況下的時間代價仍然為O(logn)。這些較好的操作性質使它們迅速成為處理數(shù)學問題、數(shù)據(jù)庫查找問題、文件檢索等問題的一種有效結構。
　　 本文在對各種平衡樹進行詳細的介紹、歸類，對它們的各種操作和算法進行比較和總結之后，重點研究了樹及平衡樹的應用，首次提出了求解迷宮問題和數(shù)學集合問題的新思路，采用樹結構不僅較好的解決了這些問題，而且比傳統(tǒng)算法更高效。在文章的最后還給出了平衡