樹型查找

在前面我們?cè)��?jīng)寫過一個(gè)BSTree類，這個(gè)類大致上能滿足我們的要求。而為了在不同的輸入情況下，使得樹的高度盡可能的小，平衡樹的概念被提出來了，例如前面的AVLTree類。所謂的平衡，現(xiàn)在更多意義上是指和完全m叉樹高度的比值是小于某個(gè)常數(shù)的樹，也就是高度≤klogmn的樹，k為一個(gè)定常數(shù)。注意到AVL樹的定義實(shí)際上太苛刻，就很容易理解為什么要放寬要求。而實(shí)際能應(yīng)用的平衡樹，都是為了滿足這個(gè)要求而自己定一套規(guī)則，比如B－樹，這個(gè)后面會(huì)講到。

有些字典會(huì)提供一個(gè)目錄，大部分情況是這樣的A……xx；B……xx；……。這樣就能迅速翻到開頭字母對(duì)應(yīng)的頁數(shù)（實(shí)際上也知道了開頭字母結(jié)束的地方），并且每個(gè)頁的左右上角的單詞也說明了本頁的單詞范圍（可以判斷所查單詞在不在此頁）。這些就是索引。

使用索引能夠快速的定位查找范圍，從我們查字典的經(jīng)驗(yàn)看來，這也應(yīng)該是能提高查找效率的方法。注意到目錄的作用，它使得我們所需的字典空間分布，在一頁（或者幾頁）的空間上迅速的被我們得到——類比來看，如果數(shù)據(jù)太多以至內(nèi)存裝不下，我們也可以弄個(gè)“目錄”，使得可以將數(shù)據(jù)分塊的讀入內(nèi)存查找。

當(dāng)數(shù)據(jù)膨脹到一個(gè)可怕的程度時(shí)，連索引都不能被全部裝入內(nèi)存——見過印刷版的EI檢索都有這個(gè)感覺，光一個(gè)檢索目錄都比我們用的字典厚。我們的辦法就是索引再索引，顯而易見的，每個(gè)索引塊都應(yīng)該盡可能的大，以幫助我們獲得盡可能多的信息，而避免再次的查索引（此時(shí)一般都會(huì)涉及外存的存取）。AVL樹此時(shí)便力不從心了，我們需要一種新的結(jié)構(gòu)。

相信每個(gè)學(xué)到這里的人都對(duì)B－樹的定義深惡痛絕，這個(gè)的責(zé)任應(yīng)該由寫書的人來負(fù)，雖然定義、概念是人認(rèn)知的重要工具和途徑，但在這里是適得其反的。原因就是B－樹根本不存在概念意義上的“概念”，它只是一個(gè)描述型的“概念”，是B－樹能夠運(yùn)行從而表現(xiàn)出來的一種現(xiàn)象。不管怎么說，先看一下現(xiàn)有的書上的定義（省略了“或者為空樹”這句話）：

嚴(yán)蔚敏、吳偉民《數(shù)據(jù)結(jié)構(gòu)（C語言版）》

1.         每個(gè)節(jié)點(diǎn)至多有m棵子樹

2.         若根不是葉子節(jié)點(diǎn)，至少有兩棵子樹

3.         除根以外的所有非終端節(jié)點(diǎn)至少有ém/2ù棵子樹

4.         所有非終端節(jié)點(diǎn)包含下列信息數(shù)據(jù)（n，A0，K1，A1，K2，A2……，Kn，An），其中，Ki為關(guān)鍵字，且Ki<Ki+1（i＝1，2，……，n－1）；Ai（i＝0，……，n）為指向子樹根節(jié)點(diǎn)的指針，且指針Ai-1所指子樹中所有節(jié)點(diǎn)的關(guān)鍵字均小于Ki（i＝1，……，n），An所指子樹中所有的節(jié)點(diǎn)的關(guān)鍵字均大于Kn，n（ém/2ù-1￡ n ￡ m-1）為關(guān)鍵字的個(gè)數(shù)（或n+1為子樹個(gè)數(shù)）。

5.         所有的葉子節(jié)點(diǎn)都出現(xiàn)在同一層次上，并不帶信息（可以看作是外部節(jié)點(diǎn)或查找失敗的節(jié)點(diǎn)，實(shí)際上這些節(jié)點(diǎn)不存在，指向這些節(jié)點(diǎn)的指針為空）。

殷人昆等《數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++描述）》

1.         m路搜索樹（實(shí)際上是上面第1、4條的內(nèi)容）

2.         根節(jié)點(diǎn)至少有兩個(gè)子女

3.         除根節(jié)點(diǎn)以外的所有節(jié)點(diǎn)（不包括失敗節(jié)點(diǎn)）至少有ém/2ù個(gè)子女

4.         所有的失敗節(jié)點(diǎn)都位于同一層。事實(shí)上，這些節(jié)點(diǎn)都是作為外部節(jié)點(diǎn)存在，不是樹上的節(jié)點(diǎn)。

非常莫名其妙的定義——憑什么根至少有兩個(gè)子女，而其他的至少ém/2ù個(gè)子女？跟AVL樹的定義比較一下就能看出這個(gè)定義的不合理處——AVL樹只是給出了平衡的定義“左右子樹高度差不超過1”，至于什么平衡因子、旋轉(zhuǎn)，根本就沒有提及，那只是為了保證平衡的手段。顯然，現(xiàn)在的B－樹的定義，把為了保證平衡而采取措施的結(jié)果包括在定義之中了，而這必將導(dǎo)致人的認(rèn)知上的迷惑，因此這樣的定義是不合格的�；蛟S，一個(gè)不和現(xiàn)在定義矛盾的合理的定義應(yīng)該是這樣：采用如下辦法達(dá)到“平衡”的m路搜索樹……，當(dāng)然，我們首先要解決什么叫“平衡”，而這個(gè)直覺上的定義前面已經(jīng)提到了。

接下來，讓我們看看保持平衡的“如下辦法”是什么�；貞浺幌翧VL樹，那時(shí)的旋轉(zhuǎn)確實(shí)是很精妙的方法——保持中序有序的情況下改變子樹高度差，我也耗費(fèi)了不少腦細(xì)胞把AVL樹的講解從書上的莫名其妙變成了按部就班，這是本人到目前為止最為得意的一件事情，到大家能看到這篇文字的時(shí)候，應(yīng)該也能看見我寫的AVL樹的講解了。

兩個(gè)叉的AVL樹能旋轉(zhuǎn)，m個(gè)叉的樹怎么轉(zhuǎn)？看來得換個(gè)思路，前人已經(jīng)為我們做到了，就是節(jié)點(diǎn)的分裂和合并。

Ø         分裂

節(jié)點(diǎn)裝不下的時(shí)候就分裂，也就是說對(duì)于一個(gè)節(jié)點(diǎn)，當(dāng)?shù)趍個(gè)元素進(jìn)來的時(shí)候，就要分裂。怎么分裂？以中間元素為軸，左右兩部分各形成一個(gè)節(jié)點(diǎn)，作為中間元素的左右孩子——這里還是借用了二叉樹的概念，而事實(shí)上，m叉搜索樹就是多個(gè)二叉搜索樹拼合的產(chǎn)物——這樣還是中序有序的（或許不該說“中序”，大家結(jié)合二叉樹自己理解吧），中間元素帶著這兩個(gè)孩子插入到原來節(jié)點(diǎn)的父節(jié)點(diǎn)，當(dāng)然，父節(jié)點(diǎn)滿的時(shí)候同樣要分裂，這樣一層層直到根節(jié)點(diǎn)（或者不用分裂）。

縱觀分裂的過程，我們才能明白前面的定義是怎么回事。如果采用如上的分裂方法，對(duì)于根節(jié)點(diǎn)來說，要么沒有子女，要么一分裂就兩個(gè)子女。而對(duì)于非根節(jié)點(diǎn)，只有當(dāng)節(jié)點(diǎn)滿的時(shí)候才會(huì)分裂，那自然最少有ém/2ù個(gè)子女。

而“所有的失敗節(jié)點(diǎn)都位于同一層”是B－樹的“平衡準(zhǔn)則”，很容易就能看出這樣的樹是“平衡”的。

所以，關(guān)于B－樹的定義實(shí)際上是B－樹維持平衡的外在表現(xiàn)，它不應(yīng)該作為B－樹的定義，而只能是一種描述。

Ø         合并

和二叉搜索樹一樣，刪除都?xì)w結(jié)成在葉子節(jié)點(diǎn)的刪除，如果不在葉子節(jié)點(diǎn)，就拿葉子節(jié)點(diǎn)中的覆蓋掉，轉(zhuǎn)化成在葉子節(jié)點(diǎn)的刪除。同樣的，當(dāng)不平衡出現(xiàn)時(shí)（即不滿足上面B－樹的描述），需要平衡化。

我們看到，父節(jié)點(diǎn)中的元素和左右兩個(gè)孩子原來可能是一個(gè)節(jié)點(diǎn)的，或者可以說他們可以合并成一個(gè)節(jié)點(diǎn)。這樣一來，如果他們的元素總和大于m－1，那么就從多的向少的撥一個(gè)元素——想想電視里老和尚手里的念珠，元素的移動(dòng)過程是這樣的：元素多的節(jié)點(diǎn)——父節(jié)點(diǎn)（手里的珠子）——元素少的節(jié)點(diǎn)。如果他們的元素總和小于等于m－1，那么就把他們合并成一個(gè)節(jié)點(diǎn)，這樣一來，父節(jié)點(diǎn)就會(huì)少一個(gè)元素，如果也出現(xiàn)了不平衡，也同樣處理。

觀看分裂合并的過程，就會(huì)發(fā)現(xiàn)插入刪除的起點(diǎn)都在葉子節(jié)點(diǎn)，出現(xiàn)不平衡后，無論分裂還是合并，都會(huì)把多了（或者少了）一個(gè)元素的變化傳遞到父節(jié)點(diǎn)，從而導(dǎo)致對(duì)父節(jié)點(diǎn)的再度平衡化。和AVL樹的調(diào)整簡(jiǎn)直是如出一轍，不同的是，AVL樹不可能分裂合并，因此采取的是旋轉(zhuǎn)的辦法；或者可以說B－樹不能旋轉(zhuǎn)，因此采取了分裂合并。而兩種調(diào)整方法都是在保持有序的情況下，使樹高（差）發(fā)生了變化。

當(dāng)樹的叉多起來的時(shí)候，操作起來都會(huì)覺得不便，因此B－樹更應(yīng)該是為了減少內(nèi)外存交換開銷而提出來的，和外排一樣，對(duì)一般的應(yīng)用意義不大，不做系統(tǒng)級(jí)別的應(yīng)用（或者是為了考試）很少會(huì)用到，就不再具體講解了。

而如果僅是在內(nèi)存中，叉的數(shù)目少一點(diǎn)會(huì)比較好，比如3叉（因?yàn)檫@樣的樹每個(gè)節(jié)點(diǎn)有2或3個(gè)叉，又叫2－3樹），而實(shí)際上，AVL樹（或者紅黑樹）已經(jīng)做得很好了，沒必要費(fèi)心在多叉搜索樹上。

想想人們還真煩，B－樹都有人認(rèn)為是Binary樹了，又來一個(gè)B＋樹，看來老外還真是該打，Binary和Balance縮寫也不多保留幾個(gè)字母，都是B。

B＋樹更是為了外存而提出來的，同樣的，一般用途不大，一般人不必費(fèi)心了（考試的例外）。注意的是和B－樹的幾點(diǎn)差別：B＋樹的非葉子節(jié)點(diǎn)都是索引，因此當(dāng)刪除關(guān)鍵碼的時(shí)候，有些情況不必改動(dòng)索引，查到了關(guān)鍵字也要一直走到葉子節(jié)點(diǎn)；另外所有的葉子節(jié)點(diǎn)都是鏈接在一起的，從頭到尾可以順序遍歷——和線索二叉樹很像不是嗎？

嚴(yán)版的和殷版的在B＋樹的定義（更準(zhǔn)確的說是描述）上有一個(gè)很大的分歧（節(jié)點(diǎn)中幾個(gè)元素幾個(gè)子樹），從教學(xué)的目的上，我同意殷版的描述，因?yàn)檫@樣的描述能更直接的表達(dá)B＋樹是如何從B－樹演化來的，嚴(yán)版的引入了額外的區(qū)分，分散了讀者的注意力。

我更覺得哈希表是因?yàn)槟壳暗膬?chǔ)存結(jié)構(gòu)而誕生的。想想我們的儲(chǔ)存器（RAM），每個(gè)單元對(duì)應(yīng)一個(gè)地址，對(duì)于數(shù)組來說，當(dāng)知道首地址后，可以馬上計(jì)算出第N個(gè)元素的地址，因此可以馬上讀取。反過來說，卻不能由內(nèi)容來確定元素的地址，想知道含某個(gè)內(nèi)容的單元的地址，就必須挨個(gè)查看，或者在有序的情況下折半查找。

而當(dāng)我們的儲(chǔ)存器能夠支持按內(nèi)容存取的話，那我們前面介紹的一切查找方法都會(huì)變得黯淡無光——想找15，馬上就能定位到15的位置，這樣O(1)的方法簡(jiǎn)直是人們夢(mèng)寐以求的。不知是幸運(yùn)（前面查找的方法還是大有用武之地）還是不幸（直接的O(1)查找不可能容易的實(shí)現(xiàn)），我們想要的那種類型的儲(chǔ)存器（相聯(lián)存儲(chǔ)器）貴的要命（也可能容量根本做不大）。

既然硬件不支持，就從軟件下手吧，前面費(fèi)了點(diǎn)口舌，是為了使大家明白現(xiàn)有的方法是建立在現(xiàn)有的結(jié)構(gòu)上的，而當(dāng)現(xiàn)有體系發(fā)生改變的時(shí)候，方法也會(huì)跟著改變。

顯然，只要我們能在內(nèi)容和序號(hào)之間建立一種函數(shù)關(guān)系，在現(xiàn)有儲(chǔ)存結(jié)構(gòu)上就能實(shí)現(xiàn)按內(nèi)容存取了——內(nèi)容→函數(shù)變換→序號(hào)。

實(shí)際上，任何可列的內(nèi)容都是可以和整數(shù)一一對(duì)應(yīng)的（我們總能找到這樣的法則），但是，一一對(duì)應(yīng)的代價(jià)很可能是整數(shù)的范圍很廣，結(jié)果使得空間的浪費(fèi)很大。打個(gè)比方，一張1901～2000年事件索引表，只需要一個(gè)100大小的數(shù)組，0元素代表1901，99元素代表2000——這里也回答了很多人疑惑的問題，2000年究竟是不是21世紀(jì)，這么一對(duì)照就會(huì)發(fā)現(xiàn)這是個(gè)歷史遺留問題，公元元年是公元1年而不是公元0年才會(huì)導(dǎo)致這樣的問題，歷法幾千年來修訂了好幾回，我們也不要對(duì)這個(gè)問題太較真了，一句話，隨大流。然而我們?nèi)绻�做一個(gè)人類歷史的索引表，上下五千年（把古代人算上就是多少萬年了），但卻不是每年都有事發(fā)生（應(yīng)該說是值得我們注意的事），更有甚者是確切的年份都不知道，顯然前面的做法就不太合理了，絕大多數(shù)空間都是空閑的。

因此，實(shí)際上采用的函數(shù)變換都是帶有壓縮性質(zhì)的，即輸出的值域都是有限的一個(gè)范圍，典型的就是0～表長。就像我們的日常經(jīng)驗(yàn)一樣，一壓縮，就會(huì)有些元素被擠到一起，“你我不分”了。因此，還必須有合理處理“沖突”的辦法。函數(shù)變換加上“沖突”處理方法，就構(gòu)成了散列這種查找方法。

具體的散列函數(shù)和沖突處理，請(qǐng)閱讀教科書，我不再詳細(xì)說明了。

這其實(shí)都是建立在散列的思想上的，在他們身上，很容易就能發(fā)現(xiàn)鏈散列的影子，而Trie樹更像是靜態(tài)的基數(shù)排序。Trie樹用來組織內(nèi)存中的數(shù)據(jù)也是很好用的，并非是只適用于外存。那么一本厚書也僅僅是一兩頁，我這幾十頁的有這么一段也差不多了，^_^。具體請(qǐng)閱讀教科書，一般讀者可跳過。