數(shù)據(jù)結(jié)構(gòu)中為了存儲和查找的方便，用各種樹結(jié)構(gòu)來存儲文件，此文就簡單總結(jié)一下各種樹的特點(diǎn)，使讀者對常見的樹有個基本的認(rèn)識，針對不同樹的詳解有專門的文章描述。本章涉及的樹結(jié)構(gòu)包括：二叉查找樹（二叉排序樹）、平衡二叉樹（AVL樹）、紅黑樹、B-樹、B+樹、B*樹、(字典樹（trie樹）、后綴樹、廣義后綴樹，這些不做講解)。
1、二叉查找樹（二叉排序樹/BST樹）
二叉查找樹是一種動態(tài)查找表（圖a），具有這些性質(zhì)：
（1）所有非葉子結(jié)點(diǎn)至多擁有兩個兒子（Left和Right）
（2）所有結(jié)點(diǎn)存儲一個關(guān)鍵字
（3）若它的左子樹不為空，則左子樹上的所有節(jié)點(diǎn)的值都小于它的根節(jié)點(diǎn)的值；
（4）若它的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值都大于它的根節(jié)點(diǎn)的值；
（5）其他的左右子樹也分別為二叉查找樹；
（6）二叉查找樹是動態(tài)查找表，在查找的過程中可見添加和刪除相應(yīng)的元素，在這些操作中需要保持二叉查找樹的以上性質(zhì)。
【說明】
????????如果BST樹的所有非葉子結(jié)點(diǎn)的左右子樹的結(jié)點(diǎn)數(shù)目均保持差不多（平衡），那么B樹
的搜索性能逼近二分查找；但它比連續(xù)內(nèi)存空間的二分查找的優(yōu)點(diǎn)是，改變BST樹結(jié)構(gòu)
（插入與刪除結(jié)點(diǎn)）不需要移動大段的內(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é)點(diǎn)的二叉查找樹可以有不同的形態(tài)，而二叉查找樹的平均查找長度與樹的深度有關(guān)，所以需要找出一個查找平均長度最小的一棵，那就是平衡二叉樹（圖b），具有以下性質(zhì)：
（1）要么是棵空樹，要么其根節(jié)點(diǎn)左右子樹的深度之差的絕對值不超過1；
（2）其左右子樹也都是平衡二叉樹；
（3）二叉樹節(jié)點(diǎn)的平衡因子定義為該節(jié)點(diǎn)的左子樹的深度減去右子樹的深度。則平衡二叉樹的所有節(jié)點(diǎn)的平衡因子只可能是-1,0,1。
3、紅黑樹
紅黑樹是一種自平衡二叉樹，在平衡二叉樹的基礎(chǔ)上每個節(jié)點(diǎn)又增加了一個顏色的屬性，節(jié)點(diǎn)的顏色只能是紅色或黑色。具有以下性質(zhì)：
（1）根節(jié)點(diǎn)只能是黑色；
（2）每個結(jié)點(diǎn)要么是紅的，要么是黑的；
（3）每個葉結(jié)點(diǎn)，即空結(jié)點(diǎn)（NIL）是黑的；
（4）對每個結(jié)點(diǎn)，從該結(jié)點(diǎn)到根結(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑結(jié)點(diǎn)。
4、B-樹
??如：（M=3）
B-樹是一種平衡多路查找樹，它在文件系統(tǒng)中很有用。一棵M階B-樹（圖d為3階B-樹），具有下列性質(zhì)：
（1）樹中每個節(jié)點(diǎn)至多有M棵子樹；
（2）若根節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，則子樹個數(shù)的范圍為[2, M]；
（3）除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)的子樹個數(shù)的范圍為[M/2, M]；
（4）每個結(jié)點(diǎn)存放至少M(fèi)/2-1（取上整）和至多M-1個關(guān)鍵字，（至少2個關(guān)鍵字）；
（5）所有的葉子節(jié)點(diǎn)都出現(xiàn)在同一層次上，且不帶任何信息，也是為了保持算法的一致性。
5、B+樹
????如：（M=3）
B+數(shù)是B-樹的一種變形，它與B-樹的差別在于（圖e為3階B+樹）：
（1）有n棵子樹的節(jié)點(diǎn)含有n個關(guān)鍵字；
（2）所有的葉子節(jié)點(diǎn)包含了全部關(guān)鍵字的信息，及指向這些關(guān)鍵字記錄的指針，且葉子節(jié)點(diǎn)本身按關(guān)鍵字大小自小到大順序鏈接；
（3）所有非終端節(jié)點(diǎn)可以看成是索引部分，節(jié)點(diǎn)中僅含有其子樹（根節(jié)點(diǎn)）中最大（或最?。╆P(guān)鍵字，所有B+樹更像一個索引順序表；
（4）對B+樹進(jìn)行查找運(yùn)算，一是從最小關(guān)鍵字起進(jìn)行順序查找，二是從根節(jié)點(diǎn)開始，進(jìn)行隨機(jī)查找。
【說明】
更適合文件索引系統(tǒng)；比如對已經(jīng)建立索引的數(shù)據(jù)庫記錄，查找10<=id<=20，那么只要通過根節(jié)點(diǎn)搜索到id=10的葉節(jié)點(diǎn)，之后只要根據(jù)葉節(jié)點(diǎn)的鏈表找到第一個大于20的就行了，比B-樹在查找10到20內(nèi)的每一個是每次都從根節(jié)點(diǎn)出發(fā)查找提高了不少效率。
6、B*樹
是B+樹的變體，在B+樹的非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針：
（1）B*樹定義了非葉子結(jié)點(diǎn)關(guān)鍵字個數(shù)至少為(2/3)*M，即塊的最低使用率為2/3
（代替B+樹的1/2）；
（2）B+樹的分裂：當(dāng)一個結(jié)點(diǎn)滿時(shí)，分配一個新的結(jié)點(diǎn)，并將原結(jié)點(diǎn)中1/2的數(shù)據(jù)復(fù)制到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)中增加新結(jié)點(diǎn)的指針；B+樹的分裂只影響原結(jié)點(diǎn)和父結(jié)點(diǎn)，而不會影響兄弟結(jié)點(diǎn)，所以它不需要指向兄弟的指針；
B*樹的分裂：當(dāng)一個結(jié)點(diǎn)滿時(shí)，如果它的下一個兄弟結(jié)點(diǎn)未滿，那么將一部分?jǐn)?shù)據(jù)移到兄弟結(jié)點(diǎn)中，再在原結(jié)點(diǎn)插入關(guān)鍵字，最后修改父結(jié)點(diǎn)中兄弟結(jié)點(diǎn)的關(guān)鍵字（因?yàn)樾值芙Y(jié)點(diǎn)的關(guān)鍵字范圍改變了）；如果兄弟也滿了，則在原結(jié)點(diǎn)與兄弟結(jié)點(diǎn)之間增加新結(jié)點(diǎn)，并各復(fù)制1/3的數(shù)據(jù)到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)增加新結(jié)點(diǎn)的指針；
所以，B*樹分配新結(jié)點(diǎn)的概率比B+樹要低，空間使用率更高；
【B樹相關(guān)的小結(jié)】
?????? B樹：二叉樹，每個結(jié)點(diǎn)只存儲一個關(guān)鍵字，等于則命中，小于走左結(jié)點(diǎn)，大于走右結(jié)點(diǎn)；
?????? B-樹：多路搜索樹，每個結(jié)點(diǎn)存儲M/2到M個關(guān)鍵字，非葉子結(jié)點(diǎn)存儲指向關(guān)鍵字范圍的子結(jié)點(diǎn)；所有關(guān)鍵字在整顆樹中出現(xiàn)，且只出現(xiàn)一次，非葉子結(jié)點(diǎn)可以命中；
?????? B+樹：在B-樹基礎(chǔ)上，為葉子結(jié)點(diǎn)增加鏈表指針，所有關(guān)鍵字都在葉子結(jié)點(diǎn)中出現(xiàn)，非葉子結(jié)點(diǎn)作為葉子結(jié)點(diǎn)的索引；B+樹總是到葉子結(jié)點(diǎn)才命中；
?????? B*樹：在B+樹基礎(chǔ)上，為非葉子結(jié)點(diǎn)也增加鏈表指針，將結(jié)點(diǎn)的最低利用率從1/2提高到2/3；
