二叉搜索樹，平衡樹，B，b-，b+,b*,紅黑樹

二叉搜索樹

? 1.所有非葉子結(jié)點(diǎn)至多擁有兩個兒子（Left和Right）；

? 2.所有結(jié)點(diǎn)存儲一個關(guān)鍵字；

? 3.非葉子結(jié)點(diǎn)的左指針指向小于其關(guān)鍵字的子樹，右指針指向大于其關(guān)鍵字的子樹；

? 如：

?

img

? 二叉樹的搜索，從根結(jié)點(diǎn)開始，如果查詢的關(guān)鍵字與結(jié)點(diǎn)的關(guān)鍵字相等，那么就命中；

否則，如果查詢關(guān)鍵字比結(jié)點(diǎn)關(guān)鍵字小，就進(jìn)入左兒子；如果比結(jié)點(diǎn)關(guān)鍵字大，就進(jìn)入

右兒子；如果左兒子或右兒子的指針為空，則報(bào)告找不到相應(yīng)的關(guān)鍵字；

? 如果二叉樹的所有非葉子結(jié)點(diǎn)的左右子樹的結(jié)點(diǎn)數(shù)目均保持差不多（平衡），那么二叉樹

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

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

? 如：

?

img

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

img

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

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

是所謂的“平衡”問題；

? 實(shí)際使用的二叉樹都是在原二叉樹的基礎(chǔ)上加上平衡算法，即“平衡二叉樹”；如何保持二叉樹

結(jié)點(diǎn)分布均勻的平衡算法是平衡二叉樹的關(guān)鍵；

平衡二叉樹

AVL-自平衡二叉查找樹

平衡二叉搜索樹：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。常用算法有紅黑樹、AVL、Treap、伸展樹等。在平衡二叉搜索樹中，我們可以看到，其高度一般都良好地維持在O（log2n），大大降低了操作的時間復(fù)雜度。

調(diào)整平衡的基本思想：
當(dāng)在二叉排序樹中插入一個節(jié)點(diǎn)時，首先檢查是否因插入而破壞了平衡，若破壞，則找出其中的最小不平衡二叉樹，在保持二叉排序樹特性的情況下，調(diào)整最小不平衡子樹中節(jié)點(diǎn)之間的關(guān)系，以達(dá)到新的平衡。
所謂最小不平衡子樹，指離插入節(jié)點(diǎn)最近且以平衡因子的絕對值大于1的節(jié)點(diǎn)作為根的子樹。

先插入指定節(jié)點(diǎn)，記錄下當(dāng)前節(jié)點(diǎn)的信息，LH，EH或者RH。
\1. 若左子樹高LH，查看其左子樹根節(jié)點(diǎn)的信息，若是LH，則一次右旋；若是RH，則一次左旋+一次右旋
\2. 若右子樹高RH，查看右子樹根節(jié)點(diǎn)的信息，若是RH，則一次左旋；若是LH，則一次右旋+一次左旋
\3. 調(diào)整改變的節(jié)點(diǎn)信息

追求絕對的高度平衡，隨著樹的高度的增加，動態(tài)插入和刪除的代價也隨之增加。

具體旋轉(zhuǎn)策略見http://blog.csdn.net/liyong199012/article/details/29219261

B樹

1、根結(jié)點(diǎn)至少有兩個子女；
2、每個非根節(jié)點(diǎn)所包含的關(guān)鍵字個數(shù) j 滿足：m/2 - 1 <= j <= m - 1；
3、除根結(jié)點(diǎn)以外的所有結(jié)點(diǎn)（不包括葉子結(jié)點(diǎn)）的度數(shù)正好是關(guān)鍵字總數(shù)加1，故內(nèi)部子樹個數(shù) k 滿足：m/2<= k <= m ；
4、所有的葉子結(jié)點(diǎn)都位于同一層。

這里寫圖片描述

B-樹

B-樹

這里寫圖片描述

1. 樹中每個結(jié)點(diǎn)至多有m個孩子；
2. 除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，其它每個結(jié)點(diǎn)至少有[m/2]個孩子；
3. 若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有2個孩子；
4. 所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層，葉子結(jié)點(diǎn)不包含任何關(guān)鍵字信息(可以看做是外部接點(diǎn)或查詢失敗的接點(diǎn)，實(shí)際上這些結(jié)點(diǎn)不存在，指向這些結(jié)點(diǎn)的指針都為null)；
5. 每個非終端結(jié)點(diǎn)中包含有n個關(guān)鍵字信息： (n，A0，K1，A1，K2，A2，……，Kn，An)。其中，
   a) Ki (i=1…n)為關(guān)鍵字，且關(guān)鍵字按順序排序Ki < K(i-1)。
   b) Ai為指向子樹根的接點(diǎn)，且指針A(i-1)指向子樹種所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki，但都大于K(i-1)。
   c) 關(guān)鍵字的個數(shù)n必須滿足： [m/2]-1 <= n <= m-1
   建立
   由于B~樹結(jié)點(diǎn)中的關(guān)鍵字個數(shù)必須>=[m/2]-1。因此和平衡二叉樹不同，每一次插入一個關(guān)鍵字并不是在樹中添加一個結(jié)點(diǎn)，而是首先在最低層的某個非終端結(jié)點(diǎn)中添加一個關(guān)鍵字，若該結(jié)點(diǎn)的關(guān)鍵字個數(shù)不超過m-1，則插入完成。否則，要產(chǎn)生結(jié)點(diǎn)的”分裂” 。
   外存
   我們現(xiàn)在把整棵樹構(gòu)造在磁盤中，假如每個盤塊可以正好存放一個B~樹的結(jié)點(diǎn)（正好存放2個文件名）。那么一個BTNode結(jié)點(diǎn)就代表一個盤塊，而子樹指針就是存放另外一個盤塊 （詳細(xì)見《外部存儲器—磁盤 》）的地址。
   現(xiàn)在我們模擬查找文件29的過程：
   (1) 根據(jù)根結(jié)點(diǎn)指針找到文件目錄的根磁盤塊1，將其中的信息導(dǎo)入內(nèi)存。【磁盤IO操作1次】
   (2) 此時內(nèi)存中有兩個文件名17，35和三個存儲其他磁盤頁面地址的數(shù)據(jù)。根據(jù)算法我們發(fā)現(xiàn)17<29<35，因此我們找到指針p2。
   (3) 根據(jù)p2指針，我們定位到磁盤塊3，并將其中的信息導(dǎo)入內(nèi)存?！敬疟PIO操作2次】
   (4) 此時內(nèi)存中有兩個文件名26，30和三個存儲其他磁盤頁面地址的數(shù)據(jù)。根據(jù)算法我們發(fā)現(xiàn)26<29<30，因此我們找到指針p2。
   (5) 根據(jù)p2指針，我們定位到磁盤塊8，并將其中的信息導(dǎo)入內(nèi)存?！敬疟PIO操作3次】
   (6) 此時內(nèi)存中有兩個文件名28，29。根據(jù)算法我們查找到文件29，并定位了該文件內(nèi)存的磁盤地址。

  分析一下上面的過程，我們發(fā)現(xiàn)需要3次磁盤IO操作和3次內(nèi)存查找操作。關(guān)于內(nèi)存中的文件名查找，由于是一個有序表結(jié)構(gòu)，可以利用折半查找提高效率。至于3次磁盤IO操作時影響整個B~樹查找效率的決定因素。
  當(dāng)然，如果我們使用平衡二叉樹的磁盤存儲結(jié)構(gòu)來進(jìn)行查找，磁盤IO操作最少4次，最多5次。而且文件越多，B~樹比平衡二叉樹所用的磁盤IO操作次數(shù)將越少，效率也越高。

B+樹

B+ 樹是一種樹數(shù)據(jù)結(jié)構(gòu)，是一個n叉樹，每個節(jié)點(diǎn)通常有多個孩子，一顆B+樹包含根節(jié)點(diǎn)、內(nèi)部節(jié)點(diǎn)和葉子節(jié)點(diǎn)。根節(jié)點(diǎn)可能是一個葉子節(jié)點(diǎn)，也可能是一個包含兩個或兩個以上孩子節(jié)點(diǎn)的節(jié)點(diǎn)。
B+ 樹通常用于數(shù)據(jù)庫和操作系統(tǒng)的文件系統(tǒng)中。
NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和BFS等文件系統(tǒng)都在使用B+樹作為元數(shù)據(jù)索引。
B+ 樹的特點(diǎn)是能夠保持?jǐn)?shù)據(jù)穩(wěn)定有序，其插入與修改擁有較穩(wěn)定的對數(shù)時間復(fù)雜度。
B+ 樹元素自底向上插入。

這里寫圖片描述

所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向含有這些關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大的順序鏈接。(而B 樹的葉子節(jié)點(diǎn)并沒有包括全部需要查找的信息)
所有的非終端結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中僅含有其子樹根結(jié)點(diǎn)中最大（或最?。╆P(guān)鍵字。(而B 樹的非終節(jié)點(diǎn)也包含需要查找的有效信息)

1) 有n棵子樹的結(jié)點(diǎn)中含有n個關(guān)鍵字；  (B~樹是n棵子樹有n+1個關(guān)鍵字)
2) 所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向含有這些關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大的順序鏈接。 (B~樹的葉子節(jié)點(diǎn)并沒有包括全部需要查找的信息)
3) 所有的非終端結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中僅含有其子樹根結(jié)點(diǎn)中最大（或最?。╆P(guān)鍵字。 (B~樹的非終節(jié)點(diǎn)也包含需要查找的有效信息)

B+樹的有效內(nèi)容均在葉子節(jié)點(diǎn)，B-樹的有效內(nèi)容不全在葉子節(jié)點(diǎn)上
B+樹的頭指針有兩個，一個指向根節(jié)點(diǎn)，另一個指向關(guān)鍵字最小的元素，因此B+樹有兩種遍歷的方式：
1.從根節(jié)點(diǎn)開始隨機(jī)查詢
2.從最小關(guān)鍵詞順序查詢

B*樹

這里寫圖片描述

在非根節(jié)點(diǎn)和葉子節(jié)點(diǎn)，增加了指向兄弟節(jié)點(diǎn)的指針。

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

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

? B+樹的分裂：當(dāng)一個結(jié)點(diǎn)滿時，分配一個新的結(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)滿時，如果它的下一個兄弟結(jié)點(diǎ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+樹要低，空間使用率更高；

紅黑樹

紅黑樹（Red Black Tree） 是一種自平衡二叉查找樹
紅黑樹和AVL樹類似，都是在進(jìn)行插入和刪除操作時通過特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能。
二叉平衡樹的嚴(yán)格平衡策略以犧牲建立查找結(jié)構(gòu)(插入，刪除操作)的代價，換來了穩(wěn)定的O(logN) 的查找時間復(fù)雜度
它雖然是復(fù)雜的，但它的最壞情況運(yùn)行時間也是非常良好的，并且在實(shí)踐中是高效的： 它可以在O(log n)時間內(nèi)做查找，插入和刪除，這里的n 是樹中元素的數(shù)目。

(1) 每個節(jié)點(diǎn)或者是黑色，或者是紅色。
(2) 根節(jié)點(diǎn)是黑色。
(3) 每個葉子節(jié)點(diǎn)是黑色。 [注意：這里葉子節(jié)點(diǎn)，是指為空的葉子節(jié)點(diǎn)！]
(4) 如果一個節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的。
(5) 從一個節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。12345

RBT 的操作代價分析：
(1) 查找代價：由于紅黑樹的性質(zhì)(最長路徑長度不超過最短路徑長度的2倍)，可以說明紅黑樹雖然不像AVL一樣是嚴(yán)格平衡的，但平衡性能還是要比BST要好。其查找代價基本維持在O(logN)左右，但在最差情況下(最長路徑是最短路徑的2倍少1)，比AVL要略遜色一點(diǎn)。
(2) 插入代價：RBT插入結(jié)點(diǎn)時，需要旋轉(zhuǎn)操作和變色操作。但由于只需要保證RBT基本平衡就可以了。因此插入結(jié)點(diǎn)最多只需要2次旋轉(zhuǎn)，這一點(diǎn)和AVL的插入操作一樣。雖然變色操作需要O(logN)，但是變色操作十分簡單，代價很小。
(3) 刪除代價：RBT的刪除操作代價要比AVL要好的多，刪除一個結(jié)點(diǎn)最多只需要3次旋轉(zhuǎn)操作。
RBT 效率總結(jié) : 查找 效率最好情況下時間復(fù)雜度為O(logN)，但在最壞情況下比AVL要差一些，但也遠(yuǎn)遠(yuǎn)好于BST。
插入和刪除操作改變樹的平衡性的概率要遠(yuǎn)遠(yuǎn)小于AVL（RBT不是高度平衡的）。因此需要的旋轉(zhuǎn)操作的可能性要小，而且一旦需要旋轉(zhuǎn)，插入一個結(jié)點(diǎn)最多只需要旋轉(zhuǎn)2次，刪除最多只需要旋轉(zhuǎn)3次(小于AVL的刪除操作所需要的旋轉(zhuǎn)次數(shù))。雖然變色操作的時間復(fù)雜度在O(logN)，但是實(shí)際上，這種操作由于簡單所需要的代價很小。

紅黑樹能夠以O(shè)(log2(N))的時間復(fù)雜度進(jìn)行搜索、插入、刪除操作。此外,任何不平衡都會在3次旋轉(zhuǎn)之內(nèi)解決。這一點(diǎn)是AVL所不具備的。

插入操作：
1.插入根節(jié)點(diǎn)（不需要操作）
2.父節(jié)點(diǎn)為黑色(不需要操作)
3.父節(jié)點(diǎn)和兄弟節(jié)點(diǎn)為紅色，祖父節(jié)點(diǎn)為黑色，只需要變色，將祖父節(jié)點(diǎn)遞歸檢查（原本檢查自己）
4.父節(jié)點(diǎn)為紅色，兄弟節(jié)點(diǎn)為黑色，祖父節(jié)點(diǎn)為紅色，先兩次旋轉(zhuǎn)再調(diào)整顏色（左旋+右旋）12345
刪除操作：
1.刪除只有一個新的根節(jié)點(diǎn)（直接刪除）
2.父節(jié)點(diǎn)為黑色，兄弟節(jié)點(diǎn)為紅色（先旋轉(zhuǎn)成左左，再刪除）
3.父節(jié)點(diǎn)為黑色，兄弟節(jié)點(diǎn)為黑色（先將兄弟節(jié)點(diǎn)換成紅色，變成情況2）
4.父節(jié)點(diǎn)為紅色，自己和兄弟節(jié)點(diǎn)為黑色（將父節(jié)點(diǎn)變成黑色，兄弟節(jié)點(diǎn)變成紅色，變成情況2）
5.兄弟節(jié)點(diǎn)為黑色，兄弟節(jié)點(diǎn)左子樹根節(jié)點(diǎn)為紅色（交換顏色，旋轉(zhuǎn)成為左左）
6.情況2和情況5，調(diào)整性質(zhì)5（將N刪掉，用子節(jié)點(diǎn)頂替，若子節(jié)點(diǎn)為紅色，則重繪為黑色）1234567

這里寫圖片描述

實(shí)現(xiàn)：http://www.cnblogs.com/skywang12345/p/3624343.html

應(yīng)用

AVL樹：平衡二叉樹，一般是用平衡因子差值決定并通過旋轉(zhuǎn)來實(shí)現(xiàn)，左右子樹樹高差不超過1，那么和紅黑樹比較它是嚴(yán)格的平衡二叉樹，平衡條件非常嚴(yán)格（樹高差只有1），只要插入或刪除不滿足上面的條件就要通過旋轉(zhuǎn)來保持平衡。由于旋轉(zhuǎn)是非常耗費(fèi)時間的。我們可以推出AVL樹適合用于插入刪除次數(shù)比較少，但查找多的情況。

應(yīng)用相對其他數(shù)據(jù)結(jié)構(gòu)比較少。windows對進(jìn)程地址空間的管理用到了AVL樹。

? 紅黑樹：平衡二叉樹，通過對任何一條從根到葉子的簡單路徑上各個節(jié)點(diǎn)的顏色進(jìn)行約束，確保沒有一條路徑會比其他路徑長2倍，因而是近似平衡的。所以相對于嚴(yán)格要求平衡的AVL樹來說，它的旋轉(zhuǎn)保持平衡次數(shù)較少。用于搜索時，插入刪除次數(shù)多的情況下我們就用紅黑樹來取代AVL。

紅黑樹應(yīng)用比較廣泛：

· 廣泛用在C++的STL中。map和set都是用紅黑樹實(shí)現(xiàn)的。

· 著名的linux進(jìn)程調(diào)度Completely Fair Scheduler,用紅黑樹管理進(jìn)程控制塊。

· epoll在內(nèi)核中的實(shí)現(xiàn)，用紅黑樹管理事件塊

· nginx中，用紅黑樹管理timer等

· Java的TreeMap實(shí)現(xiàn)

? B樹，B+樹：它們特點(diǎn)是一樣的，是多路查找樹，一般用于數(shù)據(jù)庫中做索引，因?yàn)樗鼈兎种Ф鄬訑?shù)少，因?yàn)榇疟PIO是非常耗時的，而像大量數(shù)據(jù)存儲在磁盤中所以我們要有效的減少磁盤IO次數(shù)避免磁盤頻繁的查找。
B+樹是B樹的變種樹，有n棵子樹的節(jié)點(diǎn)中含有n個關(guān)鍵字，每個關(guān)鍵字不保存數(shù)據(jù)，只用來索引，數(shù)據(jù)都保存在葉子節(jié)點(diǎn)。是為文件系統(tǒng)而生的。

? B+樹相對B樹磁盤讀寫代價更低：因?yàn)锽+樹非葉子結(jié)點(diǎn)只存儲鍵值，單個節(jié)點(diǎn)占空間小，索引塊能夠存儲更多的節(jié)點(diǎn)，從磁盤讀索引時所需的索引塊更少，所以索引查找時I/O次數(shù)較B-Tree索引少，效率更高。而且B+Tree在葉子節(jié)點(diǎn)存放的記錄以鏈表的形式鏈接，范圍查找或遍歷效率更高。Mysql InnoDB用的就是B+Tree索引。

Trie樹：
? 又名單詞查找樹，一種樹形結(jié)構(gòu)，常用來操作字符串。它是不同字符串的相同前綴只保存一份。
相對直接保存字符串肯定是節(jié)省空間的，但是它保存大量字符串時會很耗費(fèi)內(nèi)存（是內(nèi)存）。
類似的有：前綴樹(prefix tree)，后綴樹(suffix tree)，radix tree(patricia tree, compactprefix tree)，crit-bit tree（解決耗費(fèi)內(nèi)存問題），以及前面說的double array trie。
前綴樹：字符串快速檢索，字符串排序，最長公共前綴，自動匹配前綴顯示后綴。
后綴樹：查找字符串s1在s2中，字符串s1在s2中出現(xiàn)的次數(shù)，字符串s1,s2最長公共部分，最長回文串。

trie 樹的一個典型應(yīng)用是前綴匹配，比如下面這個很常見的場景，在我們輸入時，搜索引擎會給予提示。

img

還有比如IP選路，也是前綴匹配，一定程度會用到trie。