大綱

在了解 B樹、B+樹、AVL樹、紅黑樹 之前，我們先看一下各種樹型結(jié)構(gòu)的大致實際應(yīng)用場景：

B和B+樹：主要用在文件系統(tǒng)以及數(shù)據(jù)庫中做索引等AVL樹：平衡二叉樹之一，應(yīng)用相對其他數(shù)據(jù)結(jié)構(gòu)比較少，windows對進(jìn)程地址空間的管理用到了AVL紅黑樹：平衡二叉樹，廣泛應(yīng)用在C++STL中，比如map和set，Java的TreeMap

樹結(jié)構(gòu)已經(jīng)有了很多種形式，為何出現(xiàn) B樹、B+樹、AVL樹、紅黑樹？下面我們按照這個大綱來看一下這些問題？

二叉搜索樹

概念

二叉搜索樹 (平衡二叉樹) 是采用二分法思維把數(shù)據(jù)按規(guī)則組裝成一個樹形結(jié)構(gòu)的數(shù)據(jù)，用這個樹形結(jié)構(gòu)的數(shù)據(jù)減少無關(guān)數(shù)據(jù)的檢索，大大的提升了數(shù)據(jù)檢索的速度。

我們在二叉搜索樹的深度遍歷過程中，使用中序遍歷，就能獲取得到有序的序列。

特點

• 如果任意節(jié)點左子樹不為空，則左子樹的值均小于根節(jié)點的值。
• 如果任意節(jié)點右子樹不為空，則右子樹的值均大于于根節(jié)點的值。
• 任意節(jié)點的左右子樹也分別是二叉查找樹。
• 沒有鍵值相等的節(jié)點。

存在的局限

對于一個節(jié)點分布相對均衡 的二叉查找樹來說，如果節(jié)點總數(shù)是n，那 么搜索節(jié)點的時間復(fù)雜度就是O(logn) ，和樹的深度是一樣的。 這種依靠比較大小來逐步查找的方式，和二分查找算法非常相似。

出現(xiàn)一些特殊的情況的時候，會導(dǎo)致搜索節(jié)點的時間復(fù)雜度變高。什么特殊情況呢？下面請試著在二叉查找樹中依次插入10、11、9、8、7、6、5、4，看看會出現(xiàn)什么 ? 好好的一個二叉樹，變成“跛腳”啦！

不只是外觀看起來變得怪異了，查詢節(jié)點的時間復(fù)雜度也退化成了O(n)。 怎么解決這個問題呢？這就涉及二叉樹的自平衡 了。二叉樹自平衡的方式有多種，如紅黑樹、AVL樹等，這兩種我們在后面會介紹到，我們先來看一下B樹和B+樹。

B樹

概念

B樹又名平衡多路查找樹（也把B樹稱為B-樹）查找路徑不只兩個，不同于常見的二叉樹，它是一種多叉樹，我們常見的使用場景一般是在數(shù)據(jù)庫索引技術(shù)里，大量使用者B樹和B+樹的數(shù)據(jù)結(jié)構(gòu)。

B樹大多用在磁盤上用于查找磁盤的地址。因為磁盤會有大量的數(shù)據(jù)，有可能沒有辦法一次將需要的所有數(shù)據(jù)加入到內(nèi)存中，所以只能逐一加載磁盤頁，每個磁盤頁就對應(yīng)一個節(jié)點，而對于B樹來說，B樹很好的將樹的高度降低了，這樣就會減少IO查詢次數(shù)，雖然一次加載到內(nèi)存的數(shù)據(jù)變多了，但速度絕對快于AVL或是紅黑樹的。

特點：

• 所有鍵值分布在整個樹中（區(qū)別與B+樹，B+樹的值只分部在葉子節(jié)點上）
• 任何關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個節(jié)點中（區(qū)別與B+樹）
• 搜索有可能在非葉子節(jié)點結(jié)束（區(qū)別與B+樹，因為值都在葉子節(jié)點上，只有搜到葉子節(jié)點才能拿到值）
• 在關(guān)鍵字全集內(nèi)做一次查找，性能逼近二分查找算法

查詢分析

• 如果要查找數(shù)據(jù)項29，那么首先會把磁盤塊1由磁盤加載到內(nèi)存，此時發(fā)生一次IO，在內(nèi)存中用二分查找確定29在17和35之間，鎖定磁盤塊1的P2指針，內(nèi)存時間因為非常短（相比磁盤的IO）可以忽略不計，
• 通過磁盤塊1的P2指針的磁盤地址把磁盤塊3由磁盤加載到內(nèi)存，發(fā)生第二次IO，29在26和30之間，鎖定磁盤塊3的P2指針，
• 通過指針加載磁盤塊8到內(nèi)存，發(fā)生第三次IO，同時內(nèi)存中做二分查找找到29，結(jié)束查詢，總計三次IO。

B+樹

概念

特點

• 所有葉子節(jié)點連接成為一個單鏈表，且這個鏈表是有序的。
• 所有關(guān)鍵字都在葉子節(jié)點出現(xiàn)，因此不可能在非葉子節(jié)點命中。
• 內(nèi)節(jié)點不存數(shù)據(jù)，只存key。
• 非葉子節(jié)點相當(dāng)于是葉子節(jié)點的索引，葉子節(jié)點相當(dāng)于是存儲數(shù)據(jù)的數(shù)據(jù)層。

B+Tree與B-Tree 的區(qū)別

1）B樹的關(guān)鍵字和記錄是放在一起的，葉子節(jié)點可以看作外部節(jié)點，不包含任何信息；B+樹的非葉子節(jié)點中只有關(guān)鍵字和指向下一個節(jié)點的索引，記錄只放在葉子節(jié)點中。

2）在B樹中，越靠近根節(jié)點的記錄查找時間越快，只要找到關(guān)鍵字即可確定記錄的存在；而B+樹中每個記錄的查找時間基本是一樣的，都需要從根節(jié)點走到葉子節(jié)點，而且在葉子節(jié)點中還要再比較關(guān)鍵字。

思考：為什么說B+tree比B-tree更適合實際應(yīng)用中操作系統(tǒng)的文件索引和數(shù)據(jù)庫索引？

1) B+樹的磁盤讀寫代價更低

　　B+樹的內(nèi)部結(jié)點并沒有指向關(guān)鍵字具體信息的指針。因此其內(nèi)部結(jié)點相對B 樹更小。如果把所有同一內(nèi)部結(jié)點的關(guān)鍵字存放在同一盤塊中，那么盤塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多。一次性讀入內(nèi)存中的需要查找的關(guān)鍵字也就越多。相對來說IO讀寫次數(shù)也就降低了。

2) B+樹的查詢效率更加穩(wěn)定

　　由于非終結(jié)點并不是最終指向文件內(nèi)容的結(jié)點，而只是葉子結(jié)點中關(guān)鍵字的索引。所以任何關(guān)鍵字的查找必須走一條從根結(jié)點到葉子結(jié)點的路。所有關(guān)鍵字查詢的路徑長度相同，導(dǎo)致每一個數(shù)據(jù)的查詢效率相當(dāng)。

3)范圍查找更快

mysql是關(guān)系型數(shù)據(jù)庫，經(jīng)常會按照區(qū)間來訪問某個索引列，B+樹的葉子節(jié)點間按順序建立了鏈指針，加強了區(qū)間訪問性，所以B+樹對索引列上的區(qū)間范圍查詢很友好。而B樹的數(shù)據(jù)有一部分存在在非葉子節(jié)點上面，而且默認(rèn)的B樹的相鄰的葉子節(jié)點之間是沒有指針的，所以范圍查找相對更慢。

AVL樹（平衡二叉樹）

概念

AVL、紅黑樹是對二叉搜索樹的改進(jìn)版本。

平衡因子：某個節(jié)點的左右子樹深度之差。在一棵平衡二叉樹中，節(jié)點的平衡因子只能取 0 、1 或者 -1 ，分別對應(yīng)著左右子樹等高，左子樹比較高，右子樹比較高。

AVL樹是帶有平衡條件的二叉查找樹，一般是用平衡因子差值判斷是否平衡并通過旋轉(zhuǎn)來實現(xiàn)平衡，左右子樹樹高不超過1，和紅黑樹相比，它是嚴(yán)格的平衡二叉樹，平衡條件必須滿足（所有節(jié)點的左右子樹高度差不超過1）。

不管我們是執(zhí)行插入還是刪除操作，只要不滿足上面的條件，就要通過旋轉(zhuǎn)來保持平衡，而旋轉(zhuǎn)是非常耗時的，由此我們可以知道AVL樹適合用于插入刪除次數(shù)比較少，但查找多的情況。

如上圖所示：任意節(jié)點的左右子樹的平衡因子差值都不會大于1

AVL保持平衡的四種操作

增刪改查操作和二分搜索樹類似，但是要多考慮的就是對節(jié)點的平衡考慮，如果一串?dāng)?shù)字的插入順序為3，4，5。那么這棵樹結(jié)構(gòu)就會退化為一個鏈表。而這時候AVL就會對這個樹進(jìn)行旋轉(zhuǎn)操作來達(dá)到平衡，所以，我們就知道旋轉(zhuǎn)的操作會在增加，刪除，修改這三個地方進(jìn)行旋轉(zhuǎn)。旋轉(zhuǎn)操作分為下面四種情況

1 LL右單旋轉(zhuǎn)

如圖，8的左子樹已經(jīng)退化為鏈表，并且5，8這兩個節(jié)點不再平衡，這時我們先找到深度最深的不平衡節(jié)點5，對節(jié)點5進(jìn)行LL旋轉(zhuǎn)操作，在如圖的這種情況下，得到右圖的結(jié)構(gòu)

2 RR左單旋轉(zhuǎn)

如圖，當(dāng)插入順序為當(dāng)插入順序為8，3，10，13，15的時候，樹的結(jié)構(gòu)變成左邊的樣子，這時10節(jié)點和8節(jié)點已經(jīng)不平衡，為了保持AVL的平衡，我們要對10節(jié)點進(jìn)行RR旋轉(zhuǎn)，如右圖所示

3 LR先左后右

如圖。5，8節(jié)點已經(jīng)不平衡，這時要對5節(jié)點做平衡處理，首先將5進(jìn)行RR左旋轉(zhuǎn)，7的左節(jié)點也變?yōu)?的右節(jié)點。

這時7，8還是不平衡的，對8進(jìn)行右旋轉(zhuǎn)，8的右節(jié)點也變?yōu)?的左節(jié)點，如圖。

4 RL先右后左

如左圖，8，13節(jié)點不平衡，對13節(jié)點進(jìn)行LL右旋轉(zhuǎn)，得到右圖

這時8，10是不平衡的，對8節(jié)點進(jìn)行RR左旋轉(zhuǎn)，得到右圖。

紅黑樹

概念

一種二叉查找樹，但在每個節(jié)點增加一個存儲位表示節(jié)點的顏色，可以是red或black（非紅即黑）。通過對任何一條從根到葉子的路徑上各個節(jié)點著色的方式的限制，紅黑樹確保沒有一條路徑會比其它路徑長出兩倍。它是一種弱平衡二叉樹，相對于要求嚴(yán)格的AVL樹來說，它的旋轉(zhuǎn)次數(shù)少，所以對于插入、刪除操作較多的情況下，我們就用紅黑樹。

特點

• 每個節(jié)點非紅即黑；
• 根節(jié)點是黑的；
• 每個葉節(jié)點(葉節(jié)點即樹尾端NULL指針或NULL節(jié)點)都是黑的；
• 如果一個節(jié)點是紅的,那么它的兩兒子都是黑的；
• 對于任意節(jié)點而言，其到葉子點樹NULL指針的每條路徑都包含相同數(shù)目的黑節(jié)點；
• 高度始終保持在h = logn
• 一般插入的是紅色結(jié)點

紅黑樹的自平衡操作

紅黑樹插入

兩個操作：旋轉(zhuǎn)+變色

在紅黑樹的結(jié)點上添加20，剛開始作為50的左子結(jié)點，這樣不符合紅黑樹的規(guī)則，并且這樣的情況滿足上面說的情況5，因此50結(jié)點會變成黑色，根結(jié)點右旋。先完成右旋，再完成變色。

旋轉(zhuǎn)

變色

繼續(xù)添加結(jié)點200，首先會作為100的右結(jié)點添加，因此父結(jié)點和叔叔結(jié)點都變成黑色，祖父結(jié)點50變成紅色，然后根節(jié)點不能為紅色，因此繼續(xù)變色，最后根節(jié)點變成黑色。需要注意的是紅色節(jié)點的子結(jié)點必須為黑色節(jié)點，但是沒有規(guī)定黑色節(jié)點的子結(jié)點必須為紅色，說明黑色節(jié)點下面子結(jié)點什么顏色都可以。

變色

繼續(xù)變色

繼續(xù)添加結(jié)點300，首先會作為子結(jié)點添加到200的右子結(jié)點，因此首先以插入結(jié)點的祖父結(jié)點100為支點發(fā)生左旋，然后變色，父結(jié)點200變成黑色，原祖父結(jié)點變成紅色。

左旋

變色

繼續(xù)添加結(jié)點150，首先會作為子結(jié)點添加到100的右子結(jié)點，因此父結(jié)點和叔叔結(jié)點變成黑色，祖父結(jié)點200變成紅色，變完色后發(fā)現(xiàn)符合黑紅樹規(guī)則，無需再旋轉(zhuǎn)或變色。

變色

繼續(xù)添加元素160，會先作為右結(jié)點掛在150下面，然后這種情況符合上面第五種，因此先按照祖父結(jié)點100為支點左旋，然后父結(jié)點變成黑色，原祖父結(jié)點變成紅色，完后發(fā)現(xiàn)符合黑紅樹規(guī)則，無需再選擇或變色。

左旋

變色

添加320到子結(jié)點，會首先掛在350下面，父結(jié)點是紅色，叔叔結(jié)點（null）為黑色，由于當(dāng)前結(jié)點在父結(jié)點的左邊，因此先以父結(jié)點350為支點右旋，右旋后變成上面的第五種情況，因此先以祖父結(jié)點300左旋，然后父結(jié)點320變色為黑色，原祖父結(jié)點300變色為紅色。

右旋

左旋變色

最后添加180到結(jié)點中，首先添加到160的右子結(jié)點，父結(jié)點和叔叔結(jié)點都變色為黑色，祖父結(jié)點150變成紅色。

變色

右旋變成紅色后，這種為第四種情況，即150結(jié)點的父結(jié)點是紅色，叔叔結(jié)點是黑色，因此本例中需要右旋，由于右旋后200和160會碰撞，因此160結(jié)點的子樹將作為200結(jié)點的左子樹。

左旋需要以200結(jié)點的祖父結(jié)點50為支點左旋，由于左旋后，50和100會發(fā)生碰撞，因此100將掛在50結(jié)點的右邊。并且父結(jié)點150變成黑色，祖父結(jié)點50會變成紅色。

變色

紅黑樹插入自平衡總結(jié)

• N為根：涂黑完事；
• 父黑：啥事不用管；
• 父紅叔紅：父/叔涂黑，祖父涂紅，然后把祖父當(dāng)成新的平衡節(jié)點遞歸處理（我們下面平衡了，讓他老人家和上面溝通吧）；
• 父紅叔黑：父節(jié)點和新插入節(jié)點同一邊的話，扭一下就完事了（同左右旋，同右左旋，順便涂色）；不在同一邊的話，先扭到同一邊吧。

紅黑樹的刪除

紅黑樹的刪除情況相對插入會復(fù)雜一些，這這里先不過多的介紹了，肝不動了。如果感興趣的話，我們在來一起探討~~

二叉搜索樹、B樹、B+樹、AVL樹、紅黑樹的常見面試題

1 為什么設(shè)計紅黑樹

紅黑樹通過它規(guī)則的設(shè)定，確保了插入和刪除的最壞的時間復(fù)雜度是O(log N) 。

紅黑樹解決了AVL平衡二叉樹的維護(hù)起來比較麻煩的問題，紅黑樹，讀取略遜于AVL，維護(hù)強于AVL，每次插入和刪除的平均旋轉(zhuǎn)次數(shù)應(yīng)該是遠(yuǎn)小于平衡樹。

因此：相對于要求嚴(yán)格的AVL樹來說，紅黑樹的旋轉(zhuǎn)次數(shù)少，所以對于插入、刪除操作較多的情況下，我們就用紅黑樹。但是，只是對查找要求較高,那么AVL還是較優(yōu)于紅黑樹.

2 B樹、B+樹和紅黑樹的區(qū)別

• 最大的區(qū)別就是樹的深度較高，在磁盤I/O方面的表現(xiàn)不如B樹。
• 在大規(guī)模數(shù)據(jù)存儲的時候，紅黑樹往往出現(xiàn)由于樹的深度過大而造成磁盤IO讀寫過于頻繁，進(jìn)而導(dǎo)致效率低下。在這方面，B樹表現(xiàn)相對優(yōu)異，B樹可以有多個子女，從幾十到上千，可以降低樹的高度。
• 紅黑樹多用在內(nèi)部排序，即全放在內(nèi)存中的，STL的map和set的內(nèi)部實現(xiàn)就是紅黑樹。
• B+樹多用于外存上時，B+也被成為一個磁盤友好的數(shù)據(jù)結(jié)構(gòu)。

3 AVL樹和紅黑樹的區(qū)別

紅黑樹的算法時間復(fù)雜度和AVL相同，但統(tǒng)計性能比AVL樹更高。

紅黑樹和AVL樹都能夠以O(shè)(log2 n)的時間復(fù)雜度進(jìn)行搜索、插入、刪除操作。 2、由于設(shè)計，紅黑樹的任何不平衡都會在三次旋轉(zhuǎn)之內(nèi)解決。AVL樹增加和刪除可能需要通過一次或多次樹旋轉(zhuǎn)來重新平衡這個樹。

在查找方面： 紅黑樹的性質(zhì)(最長路徑長度不超過最短路徑長度的2倍)，其查找代價基本維持在O(logN)左右，但在最差情況下(最長路徑是最短路徑的2倍少1)，比AVL要略遜色一點。 AVL是嚴(yán)格平衡的二叉查找樹（平衡因子不超過1）。查找過程中不會出現(xiàn)最差情況的單支樹。因此查找效率最好，最壞情況都是O(logN)數(shù)量級的。

所以，綜上： AVL比RBtree更加平衡，但是AVL的插入和刪除會帶來大量的旋轉(zhuǎn)。 所以如果插入和刪除比較多的情況，應(yīng)該使用RBtree, 如果查詢操作比較多，應(yīng)該使用AVL。

4 數(shù)據(jù)庫為什么使用B樹，而不使用AVL或者紅黑樹

我們假設(shè)B+樹一個節(jié)點可以有100個關(guān)鍵字，那么3層的B樹可以容納大概1000000多個關(guān)鍵字（100+101100+101101*100）。而紅黑樹要存儲這么多至少要20層。所以使用B樹相對于紅黑樹和AVL可以減少IO操作

5 為什么B+樹比B樹更為友好

• 磁盤讀寫代價更低 樹的非葉子結(jié)點里面沒有數(shù)據(jù)，這樣索引比較小，可以放在一個blcok（或者盡可能少的blcok）里面。避免了樹形結(jié)構(gòu)不斷的向下查找，然后磁盤不停的尋道，讀數(shù)據(jù)。這樣的設(shè)計，可以降低io的次數(shù)。
• 查詢效率更加穩(wěn)定 非終結(jié)點并不是最終指向文件內(nèi)容的結(jié)點，而只是葉子結(jié)點中關(guān)鍵字的索引。所以任何關(guān)鍵字的查找必須走一條從根結(jié)點到葉子結(jié)點的路。所有關(guān)鍵字查詢的路徑長度相同，導(dǎo)致每一個數(shù)據(jù)的查詢效率相當(dāng)。
• 遍歷所有的數(shù)據(jù)更方便 B+樹只要遍歷葉子節(jié)點就可以實現(xiàn)整棵樹的遍歷，而其他的樹形結(jié)構(gòu) 要中序遍歷才可以訪問所有的數(shù)據(jù)。