大綱

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

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

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

二叉搜索樹

概念

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

我們?cè)诙嫠阉鳂涞纳疃缺闅v過程中，使用中序遍歷，就能獲取得到有序的序列。

特點(diǎn)

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

存在的局限

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

出現(xiàn)一些特殊的情況的時(shí)候，會(huì)導(dǎo)致搜索節(jié)點(diǎn)的時(shí)間復(fù)雜度變高。什么特殊情況呢？下面請(qǐng)?jiān)囍诙娌檎覙渲幸来尾迦?0、11、9、8、7、6、5、4，看看會(huì)出現(xiàn)什么 ? 好好的一個(gè)二叉樹，變成“跛腳”啦！

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

B樹

概念

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

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

特點(diǎn)：

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

查詢分析

• 如果要查找數(shù)據(jù)項(xiàng)29，那么首先會(huì)把磁盤塊1由磁盤加載到內(nèi)存，此時(shí)發(fā)生一次IO，在內(nèi)存中用二分查找確定29在17和35之間，鎖定磁盤塊1的P2指針，內(nèi)存時(shí)間因?yàn)榉浅６蹋ㄏ啾却疟P的IO）可以忽略不計(jì)，
• 通過磁盤塊1的P2指針的磁盤地址把磁盤塊3由磁盤加載到內(nèi)存，發(fā)生第二次IO，29在26和30之間，鎖定磁盤塊3的P2指針，
• 通過指針加載磁盤塊8到內(nèi)存，發(fā)生第三次IO，同時(shí)內(nèi)存中做二分查找找到29，結(jié)束查詢，總計(jì)三次IO。

B+樹

概念

特點(diǎn)

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

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

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

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

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

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

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

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

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

3)范圍查找更快

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

AVL樹（平衡二叉樹）

概念

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

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

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

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

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

AVL保持平衡的四種操作

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

1 LL右單旋轉(zhuǎn)

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

2 RR左單旋轉(zhuǎn)

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

3 LR先左后右

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

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

4 RL先右后左

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

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

紅黑樹

概念

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

特點(diǎn)

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

紅黑樹的自平衡操作

紅黑樹插入

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

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

旋轉(zhuǎn)

變色

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

變色

繼續(xù)變色

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

左旋

變色

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

變色

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

左旋

變色

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

右旋

左旋變色

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

變色

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

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

變色

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

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

紅黑樹的刪除

紅黑樹的刪除情況相對(duì)插入會(huì)復(fù)雜一些，這這里先不過多的介紹了，肝不動(dòng)了。如果感興趣的話，我們?cè)趤硪黄鹛接憕~

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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