數(shù)據(jù)結(jié)構(gòu)中為了存儲和查找的方便靠闭，用各種樹結(jié)構(gòu)來存儲文件，此文就簡單總結(jié)一下各種樹的特點塞琼，使讀者對常見的樹有個基本的認(rèn)識菠净，針對不同樹的詳解有專門的文章描述。本章涉及的樹結(jié)構(gòu)包括：二叉查找樹（二叉排序樹）彪杉、平衡二叉樹（AVL樹）毅往、紅黑樹、B-樹派近、B+樹攀唯、B*樹、(字典樹（trie樹）渴丸、后綴樹侯嘀、廣義后綴樹，這些不做講解)曙强。

1式曲、二叉查找樹（二叉排序樹/BST樹）

（圖a）

二叉查找樹是一種動態(tài)查找表（圖a），具有這些性質(zhì)：

（1）所有非葉子結(jié)點至多擁有兩個兒子（Left和Right）

（2）所有結(jié)點存儲一個關(guān)鍵字

（3）若它的左子樹不為空收擦，則左子樹上的所有節(jié)點的值都小于它的根節(jié)點的值鼓拧；

（4）若它的右子樹不為空，則右子樹上所有節(jié)點的值都大于它的根節(jié)點的值娜扇；

（5）其他的左右子樹也分別為二叉查找樹错沃；

（6）二叉查找樹是動態(tài)查找表栅组，在查找的過程中可見添加和刪除相應(yīng)的元素，在這些操作中需要保持二叉查找樹的以上性質(zhì)枢析。

【說明】

????????如果BST樹的所有非葉子結(jié)點的左右子樹的結(jié)點數(shù)目均保持差不多（平衡）玉掸，那么B樹

的搜索性能逼近二分查找；但它比連續(xù)內(nèi)存空間的二分查找的優(yōu)點是醒叁，改變BST樹結(jié)構(gòu)

（插入與刪除結(jié)點）不需要移動大段的內(nèi)存數(shù)據(jù)司浪，甚至通常是常數(shù)開銷；

???????如：

???但BST樹在經(jīng)過多次插入與刪除后把沼，有可能導(dǎo)致不同的結(jié)構(gòu)：

右邊也是一個BST樹啊易，但它的搜索性能已經(jīng)是線性的了；同樣的關(guān)鍵字集合有可能導(dǎo)致不同的

樹結(jié)構(gòu)索引饮睬；所以租谈，使用BST樹還要考慮盡可能讓BST樹保持左圖的結(jié)構(gòu)，和避免右圖的結(jié)構(gòu)捆愁，也就

是所謂的“平衡”問題割去。

2、平衡二叉樹（AVL樹）

含有相同節(jié)點的二叉查找樹可以有不同的形態(tài)昼丑，而二叉查找樹的平均查找長度與樹的深度有關(guān)呻逆，所以需要找出一個查找平均長度最小的一棵，那就是平衡二叉樹（圖b）矾克，具有以下性質(zhì)：

（圖b）

（1）要么是棵空樹页慷，要么其根節(jié)點左右子樹的深度之差的絕對值不超過1；

（2）其左右子樹也都是平衡二叉樹胁附；

（3）二叉樹節(jié)點的平衡因子定義為該節(jié)點的左子樹的深度減去右子樹的深度酒繁。則平衡二叉樹的所有節(jié)點的平衡因子只可能是-1,0,1。

3控妻、紅黑樹

（圖c）

紅黑樹是一種自平衡二叉樹州袒，在平衡二叉樹的基礎(chǔ)上每個節(jié)點又增加了一個顏色的屬性，節(jié)點的顏色只能是紅色或黑色弓候。具有以下性質(zhì)：

（1）根節(jié)點只能是黑色郎哭；

（2）每個結(jié)點要么是紅的，要么是黑的菇存；

（3）每個葉結(jié)點夸研，即空結(jié)點（NIL）是黑的；

（4）對每個結(jié)點依鸥，從該結(jié)點到根結(jié)點的所有路徑上包含相同數(shù)目的黑結(jié)點亥至。

4、B-樹

??如：（M=3）

（圖d）

B-樹是一種平衡多路查找樹，它在文件系統(tǒng)中很有用姐扮。一棵M階B-樹（圖d為3階B-樹）絮供，具有下列性質(zhì)：

（1）樹中每個節(jié)點至多有M棵子樹；

（2）若根節(jié)點不是葉子節(jié)點茶敏，則子樹個數(shù)的范圍為[2, M]壤靶；

（3）除根結(jié)點以外的非葉子結(jié)點的子樹個數(shù)的范圍為[M/2, M]；

（4）每個結(jié)點存放至少M/2-1（取上整）和至多M-1個關(guān)鍵字惊搏，（至少2個關(guān)鍵字）贮乳；

（5）所有的葉子節(jié)點都出現(xiàn)在同一層次上，且不帶任何信息胀屿，也是為了保持算法的一致性塘揣。

5、B+樹

????如：（M=3）

（圖e）

B+數(shù)是B-樹的一種變形宿崭，它與B-樹的差別在于（圖e為3階B+樹）：

（1）有n棵子樹的節(jié)點含有n個關(guān)鍵字；

（2）所有的葉子節(jié)點包含了全部關(guān)鍵字的信息才写，及指向這些關(guān)鍵字記錄的指針葡兑，且葉子節(jié)點本身按關(guān)鍵字大小自小到大順序鏈接；

（3）所有非終端節(jié)點可以看成是索引部分赞草，節(jié)點中僅含有其子樹（根節(jié)點）中最大（或最卸锏獭）關(guān)鍵字，所有B+樹更像一個索引順序表厨疙；

（4）對B+樹進(jìn)行查找運算洲守，一是從最小關(guān)鍵字起進(jìn)行順序查找，二是從根節(jié)點開始沾凄，進(jìn)行隨機(jī)查找梗醇。

【說明】

更適合文件索引系統(tǒng)；比如對已經(jīng)建立索引的數(shù)據(jù)庫記錄撒蟀，查找10<=id<=20叙谨，那么只要通過根節(jié)點搜索到id=10的葉節(jié)點，之后只要根據(jù)葉節(jié)點的鏈表找到第一個大于20的就行了保屯，比B-樹在查找10到20內(nèi)的每一個是每次都從根節(jié)點出發(fā)查找提高了不少效率手负。

6、B*樹

是B+樹的變體姑尺，在B+樹的非根和非葉子結(jié)點再增加指向兄弟的指針：

（圖f）

（1）B*樹定義了非葉子結(jié)點關(guān)鍵字個數(shù)至少為(2/3)*M竟终，即塊的最低使用率為2/3

（代替B+樹的1/2）；

（2）B+樹的分裂：當(dāng)一個結(jié)點滿時切蟋，分配一個新的結(jié)點统捶，并將原結(jié)點中1/2的數(shù)據(jù)復(fù)制到新結(jié)點，最后在父結(jié)點中增加新結(jié)點的指針；B+樹的分裂只影響原結(jié)點和父結(jié)點瘾境，而不會影響兄弟結(jié)點歧杏，所以它不需要指向兄弟的指針；

B*樹的分裂：當(dāng)一個結(jié)點滿時迷守，如果它的下一個兄弟結(jié)點未滿犬绒，那么將一部分?jǐn)?shù)據(jù)移到兄弟結(jié)點中，再在原結(jié)點插入關(guān)鍵字兑凿，最后修改父結(jié)點中兄弟結(jié)點的關(guān)鍵字（因為兄弟結(jié)點的關(guān)鍵字范圍改變了）凯力；如果兄弟也滿了，則在原結(jié)點與兄弟結(jié)點之間增加新結(jié)點礼华，并各復(fù)制1/3的數(shù)據(jù)到新結(jié)點咐鹤，最后在父結(jié)點增加新結(jié)點的指針；

所以圣絮，B*樹分配新結(jié)點的概率比B+樹要低祈惶，空間使用率更高；

【B樹相關(guān)的小結(jié)】

?????? B樹：二叉樹扮匠，每個結(jié)點只存儲一個關(guān)鍵字捧请，等于則命中，小于走左結(jié)點棒搜，大于走右結(jié)點疹蛉；

?????? B-樹：多路搜索樹，每個結(jié)點存儲M/2到M個關(guān)鍵字力麸，非葉子結(jié)點存儲指向關(guān)鍵字范圍的子結(jié)點可款；所有關(guān)鍵字在整顆樹中出現(xiàn)，且只出現(xiàn)一次克蚂，非葉子結(jié)點可以命中闺鲸；

?????? B+樹：在B-樹基礎(chǔ)上，為葉子結(jié)點增加鏈表指針陨舱，所有關(guān)鍵字都在葉子結(jié)點中出現(xiàn)翠拣，非葉子結(jié)點作為葉子結(jié)點的索引；B+樹總是到葉子結(jié)點才命中游盲；

?????? B*樹：在B+樹基礎(chǔ)上误墓，為非葉子結(jié)點也增加鏈表指針，將結(jié)點的最低利用率從1/2提高到2/3益缎；