查找樹分析

對于規模為n的資料序列的操作取決于三個因素，一是存儲方式（資料結構），二是操作方法，三是資料特性。我們來比較一下常用的資料結構下的情況：

其它的諸如隊列，棧等資料結構的目的一般不是為了查找，是以這裡就不列出對比了。

從上面的分析我們知道，如果純粹從查找的角度來說，有序數組方式要比查找樹好，有序數組的問題就在于其插入和删除操作性能太差（如果資料太大，這種平移需要外部進行時候性能就更低了，需要很多額外的IO操作），另外如果資料太大的時候，因為有序數組的查找是根據數組索引和邊界來進行，如果不能一次加載，就需要額外的維護目前加載和索引邊界，其結果就會形成2層高度的樹，是以有序數組的方式隻對于小規模n比較合适。而由于查找樹的操作一般是路徑操作，每次所需要的資料都比較小，對記憶體的要求就比較低，便于大規模資料的處理。（另外，有序數組在樹中也是可以用的，對于m階樹來說，節點内部的查找就可以用）

      從上面的表格我們可以看出，查找樹的操作性能彈性比較大，取決于其高度H,降低高度H至少有兩個好處，1是可以提高查找性能，2是在資料規模比較大的情況下，減少IO次數(所需IO次數與樹的高度H有關）。而對于樹來說，有幾個比較重要的參數:節點數n,階m,高度H,寬度W。他們之間有如下關系：m^0+m^1+...m^(H-1) < (m^H-1)/(m-1);W<m^(H-1);min(H)>logm(n)+1;

從這些關系，我們可以看出，如果要降低樹的高度，有兩個辦法，1是增加m,2是樹盡量平衡，對于m階滿樹而言，在同樣高度的情況下，其能表達的節點n最大.對于m而言，如果m等于1或者m=n,那麼樹就退化成了連結清單（數組），那麼其優勢就沒有了。是以m應滿足:1<m<n,一般來講m不宜過大，過大的話,m部分變成了主角，就無法展現樹的優勢了。一般m都取小于10以内的數（現有的B樹,B+,AVL的m都小于等于5）。由于m一般來講是常數，m一旦确定，那麼能降低H的就隻有保持樹的平衡了.

      保持樹的平衡從理論上來講比較容易，但實際上卻比較難，樹的查找和更新問題不大，但插入和删除就有很多問題，在插入或者删除時，為了保持平衡，如果引起的節點變更很多（最壞的情況是重構樹)，那樹的優勢就沒了，是以如果算法能使得保持樹的平衡時的代價控制在可以接受的範圍内，就成了樹的平衡構造算法的關鍵，這也是B樹,AVL樹，紅黑樹等樹的算法目的根本所在。

      對于保持平衡來說，又有一個選擇，就是是保持高度平衡呢還是相對平衡，高度平衡的話，所引起的平衡操作會比較多比較頻繁，如果是相對平衡的話，這種平衡操作和頻率就會少一些。無論是保持高度平衡或者相對平衡，其實最簡單，最自然的方法就是實時計算樹的高度來進行平衡（為減少重複計算樹節點可以儲存這個高度值），即所謂的平衡因子法，AVL樹采用的就是這種方法，而且AVL是高度平衡的，其實這個方法對于m階（m>2)也是可行的.但在實踐中，平衡因子法一般都比較容易實作成高度平衡的。而對于相對平衡來說，控制的方法都是從m入手.我們知道，對于m階樹而言，

高度H與樹的節點子節點數(豐滿度)是有關的（min(H)>logm(n)+1），通過控制樹的豐滿程度也可以達到降低樹的高度H的目的。這其實就是B樹，2-3-4樹的根本思想。