樹是許多成熟的項(xiàng)目所使用的基本數(shù)據(jù)結(jié)構(gòu)，也是面試?？肌⒊绦騿T必備的重中之重。

1 底層基礎(chǔ)概念

1.1 平衡樹

所謂平衡樹的平衡，就是樹上某節(jié)點(diǎn)的所有子樹的高度差的絕對(duì)值不超過1，該規(guī)律應(yīng)用在樹中所有節(jié)點(diǎn)上。如果該樹是二叉樹，則該樹是常見的是平衡二叉樹。

1.2 平衡二叉樹

滿足平衡樹概念的二叉樹，常見實(shí)現(xiàn)有：

• 紅黑樹
• AVL樹（平衡二叉樹）
• 替罪羊樹
• Treap（樹堆）
• 伸展樹

最小二叉平衡樹的節(jié)點(diǎn)的公式如下 F(n)=F(n-1)+F(n-2)+1 這個(gè)類似于一個(gè)遞歸的數(shù)列，可以參考Fibonacci數(shù)列，1是根節(jié)點(diǎn)，F(xiàn)(n-1)是左子樹的節(jié)點(diǎn)數(shù)量，F(xiàn)(n-2)是右子樹的節(jié)點(diǎn)數(shù)量。

1.2.1 二叉樹的平衡方法

• 二叉左旋

  一棵二叉平衡樹的子樹，根是Root，左子樹是x，右子樹的根為RootR，右子樹的兩個(gè)孩子樹分別為RLeftChild和RRightChild。則左旋后，該子樹的根為RootR，右子樹為RRightChild，左子樹的根為Root，Root的兩個(gè)孩子樹分別為x（左）和RLeftChild（右）。

• 二叉右旋

  一棵二叉平衡樹的子樹，根是Root，右子樹是x，左子樹的根為RootL，左子樹的兩個(gè)孩子樹分別為LLeftChild和LRightChild。則右旋后，該子樹的根為RootL，左子樹為LLeftChild，右子樹的根為Root，Root的兩個(gè)孩子樹分別為LRightChild（左）和x（右）。

1.3 查找樹（搜索樹）

《算法導(dǎo)論》的定義：

查找樹是一種數(shù)據(jù)結(jié)構(gòu)，既可以用作字典，也可以用作優(yōu)先隊(duì)列。

查找樹支持多種動(dòng)態(tài)集合操作：SEARCH、MINIMUM、MAXIMUM、PREDECESSOR（前）、SUCCESSOR（后）、INSERT以及DELETE。

查找樹是有序的，具體表現(xiàn)為：樹上某節(jié)點(diǎn)的左邊所有子樹的值<該節(jié)點(diǎn)的值<該節(jié)點(diǎn)的右邊所有子樹的值。該規(guī)律應(yīng)用在樹中所有節(jié)點(diǎn)上。如果該樹是二叉樹，則該樹是常見的是二叉查找（搜索）樹。

1.4 二叉查找（搜索、排序）樹(BINARY SEARCH/SORT TREE)

在二叉查找樹上執(zhí)行上述基本操作的時(shí)間與樹的高度成正比。下圖所示是二叉查找樹：

binary-search-tree

用鏈表表示的話，每個(gè)節(jié)點(diǎn)都是一個(gè)對(duì)象，節(jié)點(diǎn)中的data稱之為Key關(guān)鍵字。

2 常見數(shù)據(jù)結(jié)構(gòu)

2.1 紅黑樹

2.1.1 《算法導(dǎo)論（第2版）》的定義：

紅黑樹（Red Black Tree） 是一種自平衡二叉查找樹。在每個(gè)節(jié)點(diǎn)上增加一個(gè)存儲(chǔ)位表示節(jié)點(diǎn)的顏色，可以是紅或者黑。通過對(duì)任何一條從根到葉子的路徑上各個(gè)節(jié)點(diǎn)著色方式的限制，紅黑樹確保沒有任何一條路徑會(huì)比其他路徑長出兩倍。

上圖二叉查找樹中，一個(gè)節(jié)點(diǎn)對(duì)象有四個(gè)域：key，left，right，p（parent），而紅黑樹有五個(gè)域：color， key，left，right，p。key域不為空的這里稱之為內(nèi)節(jié)點(diǎn)，而key域?yàn)榭盏牟⑶覜]有一個(gè)子節(jié)點(diǎn)或父節(jié)點(diǎn)的Nil節(jié)點(diǎn)視為外節(jié)點(diǎn)（如果有不懂請(qǐng)看下圖）。

一顆二叉查找樹如果滿足如下的紅黑性質(zhì)，則是紅黑樹：

1. 每個(gè)節(jié)點(diǎn)或是紅的或是黑的。
2. 根節(jié)點(diǎn)是黑的。
3. 葉節(jié)點(diǎn)（Nil節(jié)點(diǎn)）是黑的。
4. 如果一個(gè)節(jié)點(diǎn)是紅的，它兩個(gè)孩子節(jié)點(diǎn)都是黑的。
5. 對(duì)每個(gè)節(jié)點(diǎn)，從該節(jié)點(diǎn)到其子孫節(jié)點(diǎn)的所有路徑包含相同數(shù)目的黑色節(jié)點(diǎn)。

下圖是一個(gè)紅黑樹的例子：

red-black-tree

上圖中有個(gè)哨兵的概念，該解釋在《算法導(dǎo)論》10.2鏈表章節(jié)：

哨兵（sentinel）是個(gè)?。╠ummy）對(duì)象，可以簡化邊界條件，例如，有鏈表L和一個(gè)對(duì)象nil[L]，后者表示Nil，但也包含和其他元素一樣的各個(gè)域?，F(xiàn)在就可以將鏈表算法代碼中出現(xiàn)的每次對(duì)Nil的引用，用對(duì)哨兵元素nil[L]的引用來代替。這樣，就可以一個(gè)一般的雙向鏈表，變成一個(gè)帶哨兵的環(huán)形雙向鏈表。這時(shí)，鏈表的head不再需要了，因?yàn)榭梢酝ㄟ^next[nil[L]]來訪問表頭。如下圖：

sentinel-in-list

好，回到紅黑樹來。同樣，為了處理紅黑樹T中的邊界條件，采用哨兵來代表Nil，就可以將節(jié)點(diǎn)x的Nil孩子視為一個(gè)其父節(jié)點(diǎn)為x的普通節(jié)點(diǎn)。雖然我們可以在樹內(nèi)的每個(gè)Nil都做一個(gè)哨兵節(jié)點(diǎn)但是顯然浪費(fèi)空間，所以采用一個(gè)哨兵nil[T]來代表所有的Nil節(jié)點(diǎn)。

從某個(gè)節(jié)點(diǎn)x出發(fā)（不包括該節(jié)點(diǎn)）到達(dá)一個(gè)葉節(jié)點(diǎn)的任意路徑上，黑色節(jié)點(diǎn)的個(gè)數(shù)稱之為該節(jié)點(diǎn)的黑高度，用bh(x)表示，紅黑樹的黑高度定義為根節(jié)點(diǎn)的黑高度。

2.1.2 為什么紅黑樹是種好的查找樹

《算法導(dǎo)論》中對(duì)紅黑樹的高度引理如下：

一顆有n個(gè)內(nèi)節(jié)點(diǎn)的紅黑樹的高度至多為2lg(n+1)。

其證明如下：

先來通過歸納法證明以某一節(jié)點(diǎn)x為根的子樹至少包含2^bh(x)-1個(gè)內(nèi)節(jié)點(diǎn)。

• 如果x的高度是0，x必為一葉節(jié)點(diǎn)（nil[T]），這時(shí)bh(x)=0，滿足2^bh(x)-1=0個(gè)內(nèi)節(jié)點(diǎn)。

• 考慮一個(gè)其高度值為正值的內(nèi)節(jié)點(diǎn)x，它有兩個(gè)child，每個(gè)child根據(jù)其自身顏色是紅還是黑，對(duì)應(yīng)有黑高度bh(x)或bh(x)-1。因?yàn)閤的child的高度小于x自身的高度，利用歸納，可得出每個(gè)child至少包含2^{(bh(x)-1)-1個(gè)內(nèi)節(jié)點(diǎn)。這樣，以x為根的子樹至少包含(2}(bh(x)-1)-1)+(2^{(bh(x)-1)-1)+1即左子樹節(jié)點(diǎn)和右子樹節(jié)點(diǎn)加根節(jié)點(diǎn)的和，也就是2}(bh(x))-1個(gè)內(nèi)節(jié)點(diǎn)。

這樣證明了前面的推斷。

設(shè)h為樹的高度，根據(jù)性質(zhì)4（如果一個(gè)節(jié)點(diǎn)是紅的，它兩個(gè)孩子都是黑的），可得出從根到葉節(jié)點(diǎn)（不包括根）的任何一條簡單路徑上至少有一半的節(jié)點(diǎn)是黑色。從而根的黑高度至少是h/2，所以，

n >= 2^(h/2) - 1

1移到另一側(cè)，兩邊取對(duì)數(shù)，得

lg(n+1) >= h/2， 或者h(yuǎn) <= 2lg(n+1)

所以，紅黑樹的動(dòng)態(tài)集合操作可以在O(lgn)時(shí)間復(fù)雜度實(shí)現(xiàn)，因?yàn)閺母降椎臅r(shí)間復(fù)雜度是O(h)。

紅黑樹的具體實(shí)現(xiàn)可以參考博文。

2.2 B樹（B-樹）

B樹是為磁盤或其他直接存取輔助設(shè)備而設(shè)計(jì)的一種平衡查找樹。與紅黑樹類似，但在降低磁盤I/O操作次數(shù)方面要好一些。許多數(shù)據(jù)庫使用B樹或B樹的變形來存儲(chǔ)信息。

B樹是多叉樹，這就是說，B樹的“分支因子”可能很大，這一因子常常由所使用的磁盤特性決定的。

下圖給出一個(gè)簡單B樹：

sentinel-in-list

(解釋一下圖中節(jié)點(diǎn)由廣度遍歷順序分別是 M、D H、Q T X、B C、F G、J K L、N P、R S、V W、Y Z)。

如果B樹的內(nèi)節(jié)點(diǎn)x包含n[x]個(gè)關(guān)鍵字，則x就有n[x]+1個(gè)子女。節(jié)點(diǎn)x中的關(guān)鍵字是用來將x所處理的關(guān)鍵字域劃分成n[x]+1個(gè)子域的分割點(diǎn)，每個(gè)子域都由x中的一個(gè)子女來處理。

2.2.1 《算法導(dǎo)論（第3版）》的定義（B樹的定義第3版比第2版清晰不易誤解）：

一棵B樹T是具有如下性質(zhì)的有根的樹（根為root[T]）：

1. 每個(gè)節(jié)點(diǎn)x有以下域：
   • x.n，當(dāng)前存儲(chǔ)在節(jié)點(diǎn)x中的關(guān)鍵字個(gè)數(shù)
   • x.n個(gè)關(guān)鍵字本身x.key1，x.key2，……，x.keyx.n，非降序存放，使得x.key1<=x.key2<=...<=x.keyx.n。
   • x.leaf，一個(gè)布爾值，如果x是葉節(jié)點(diǎn)，則為true，如果x是內(nèi)部節(jié)點(diǎn)，則為false。
2. 每個(gè)內(nèi)部節(jié)點(diǎn)x還包含x.n+1個(gè)指向其children的指針x.c1，x.c2，……，x.c(x.n+1)。葉節(jié)點(diǎn)沒有child。
3. 關(guān)鍵字x.keyi對(duì)存儲(chǔ)在各子樹上的關(guān)鍵字范圍加以分割，如上面提到。如果ki為任何一個(gè)存儲(chǔ)在以x.ci為根的子樹中的關(guān)鍵字，那么

   k1<=x.key1<=k2<=x.key2<=...<=x.keyx.n<=k(x.n+1)

4. 每個(gè)葉節(jié)點(diǎn)具有相同的深度，即樹的高度
5. 每個(gè)節(jié)點(diǎn)所包含的關(guān)鍵字個(gè)數(shù)有上界和下界。用一個(gè)被稱為B樹的最小度數(shù)（minimum degree）的固定整數(shù)t>=2來表示這些界：
   • 除了根節(jié)點(diǎn)以外的每個(gè)節(jié)點(diǎn)必須至少有t-1個(gè)關(guān)鍵字，所以內(nèi)部結(jié)點(diǎn)至少會(huì)有t個(gè)child，如果樹非空，根節(jié)點(diǎn)至少有一個(gè)關(guān)鍵字。
   • 每個(gè)節(jié)點(diǎn)至多包含2t-1個(gè)關(guān)鍵字，因此，一個(gè)內(nèi)部結(jié)點(diǎn)最多有2t個(gè)child，當(dāng)節(jié)點(diǎn)恰好有2t-1個(gè)關(guān)鍵字，稱之為滿（full）節(jié)點(diǎn)。

t=2時(shí)，B樹每個(gè)內(nèi)部結(jié)點(diǎn)有2、3、4個(gè)child，稱之為2-3-4樹。

而另外一種B*樹，要求每個(gè)內(nèi)節(jié)點(diǎn)至少2/3滿，而不是像B樹一樣要求至少半滿。

2.2.2 B樹的高度

對(duì)于一個(gè)包含n個(gè)關(guān)鍵字(n>=1)，最小度數(shù)t>=2的B樹T，其高度h滿足如下規(guī)律：

h<=logt(n+1)/2

從這一點(diǎn)也看出當(dāng)對(duì)數(shù)的底t越大，h越小，所以這也是B樹的查找速度優(yōu)于紅黑樹的原因。

2.2.3 B樹與磁盤

為了平攤等待移動(dòng)磁臂的時(shí)間，磁盤會(huì)一次讀取多個(gè)數(shù)據(jù)項(xiàng)。信息被分割成一些在柱面上連續(xù)出現(xiàn)的相等大小的位的頁面，每次磁盤讀寫的都是一個(gè)或多個(gè)磁盤頁。信息在大多數(shù)的系統(tǒng)中，B樹算法的運(yùn)行時(shí)間主要由它所執(zhí)行的DISK-READ和DISK-WRITE操作的次數(shù)決定。在B樹中，一個(gè)節(jié)點(diǎn)的大小通常相當(dāng)于一個(gè)完整的磁盤頁。因此，一個(gè)B樹節(jié)點(diǎn)可以擁有的子女?dāng)?shù)就由磁盤頁的大小決定。

下一篇文章，我們會(huì)講B+樹和LSM樹的概念，未完待續(xù)。。。