樹型結(jié)構(gòu)的應(yīng)用與平衡查找樹的研究.pdf

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

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

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