數(shù)組和鏈表是常用的數(shù)據(jù)結(jié)構(gòu)，數(shù)組雖然查找快（有序數(shù)組可以通過(guò)二分法查找），但是插入和刪除是比較慢的；而鏈表，插入和刪除很快（只需要改變一些引用值），但是查找就很慢，需要從頭開始遍歷； 那么有沒(méi)有一種數(shù)據(jù)結(jié)構(gòu)能同時(shí)具備數(shù)組查找快的優(yōu)點(diǎn)以及鏈表插入和刪除快的優(yōu)點(diǎn)呢，那就是接下來(lái)要介紹的——樹。

1、二叉查找樹

特性：

• 1、左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；
• 2、右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；
• 3、左、右子樹也分別為二叉排序樹。

2、平衡二叉查找樹

特性：

• 1、在二叉樹的基礎(chǔ)上，要求兩個(gè)子樹的高度差不能超過(guò)1；
• 2、每次增刪都會(huì)通過(guò)一次或多次旋轉(zhuǎn)來(lái)平衡二叉樹；

調(diào)整平衡的基本思想：

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

先插入指定節(jié)點(diǎn)，記錄下當(dāng)前節(jié)點(diǎn)的信息，LH，EH或者RH。

• 若左子樹高LH，查看其左子樹根節(jié)點(diǎn)的信息，若是LH，則一次右旋；若是RH，則一次左旋+一次右旋
• 若右子樹高RH，查看右子樹根節(jié)點(diǎn)的信息，若是RH，則一次左旋；若是LH，則一次右旋+一次左旋
• 調(diào)整改變的節(jié)點(diǎn)信息

雖然平衡樹解決了二叉查找樹退化為近似鏈表的缺點(diǎn)，能夠把查找時(shí)間控制在 O(logn)，不過(guò)卻不是最佳的，因?yàn)槠胶鈽湟竺總€(gè)節(jié)點(diǎn)的左子樹和右子樹的高度差至多等于1，這個(gè)要求實(shí)在是太嚴(yán)了，導(dǎo)致每次進(jìn)行插入/刪除節(jié)點(diǎn)的時(shí)候，幾乎都會(huì)破壞平衡樹的第二個(gè)規(guī)則，進(jìn)而我們都需要通過(guò)左旋和右旋來(lái)進(jìn)行調(diào)整，使之再次成為一顆符合要求的平衡樹，且隨著樹的高度的增加，動(dòng)態(tài)插入和刪除的代價(jià)也越來(lái)越大，為了解決優(yōu)化插入和刪除性能，紅黑樹出現(xiàn)了。

顯然，如果在那種插入、刪除很頻繁的場(chǎng)景中，平衡樹需要頻繁著進(jìn)行調(diào)整，這會(huì)使平衡樹的性能大打折扣，為了解決這個(gè)問(wèn)題，于是有了紅黑樹，紅黑樹具有如下特點(diǎn)：

3、紅黑樹：

特性：

1、根節(jié)點(diǎn)是黑色；

2、每個(gè)節(jié)點(diǎn)或者是黑色，或者是紅色；

3、每個(gè)葉子節(jié)點(diǎn)是黑色。 [注意：這里葉子節(jié)點(diǎn)，是指為空的葉子節(jié)點(diǎn)?。?/p>

4、如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的，也就是說(shuō)一個(gè)紅節(jié)點(diǎn)的父節(jié)點(diǎn)只能是黑色

5、從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)，也就是說(shuō)確保沒(méi)有一條路徑會(huì)比其他路徑長(zhǎng)出倆倍；

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

紅黑樹的操作代價(jià)：

• 查找代價(jià)：由于紅黑樹的性質(zhì)(最長(zhǎng)路徑長(zhǎng)度不超過(guò)最短路徑長(zhǎng)度的2倍)，可以說(shuō)明紅黑樹雖然不像平衡二叉查找樹一樣是嚴(yán)格平衡的，但平衡性能還是要比二叉查找樹要好。其查找代價(jià)基本維持在O(logN)左右，但在最差情況下(最長(zhǎng)路徑是最短路徑的2倍少1)，比平衡二叉查找樹要略遜色一點(diǎn)。
• 插入代價(jià)：RBT插入結(jié)點(diǎn)時(shí)，需要旋轉(zhuǎn)操作和變色操作。但由于只需要保證RBT基本平衡就可以了。因此插入結(jié)點(diǎn)最多只需要2次旋轉(zhuǎn)，這一點(diǎn)和平衡二叉查找樹的插入操作一樣。雖然變色操作需要O(logN)，但是變色操作十分簡(jiǎn)單，代價(jià)很小。
• 刪除代價(jià)：紅黑樹的刪除操作代價(jià)要比平衡二叉查找樹要好的多，刪除一個(gè)結(jié)點(diǎn)最多只需要3次旋轉(zhuǎn)操作。

RBT 效率總結(jié) : 查找效率最好情況下時(shí)間復(fù)雜度為O(logN)，但在最壞情況下比平衡二叉查找樹要差一些，但也遠(yuǎn)遠(yuǎn)好于二叉查找樹。 插入和刪除操作改變樹的平衡性的概率要遠(yuǎn)遠(yuǎn)小于AVL（RBT不是高度平衡的）。因此需要的旋轉(zhuǎn)操作的可能性要小，而且一旦需要旋轉(zhuǎn)，插入一個(gè)結(jié)點(diǎn)最多只需要旋轉(zhuǎn)2次，刪除最多只需要旋轉(zhuǎn)3次(小于AVL的刪除操作所需要的旋轉(zhuǎn)次數(shù))。雖然變色操作的時(shí)間復(fù)雜度在O(logN)，但是實(shí)際上，這種操作由于簡(jiǎn)單所需要的代價(jià)很小。

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

調(diào)整平衡的基本思想：

• 變色：為了重新符合紅黑樹的規(guī)則，嘗試把紅色節(jié)點(diǎn)變?yōu)楹谏?，或者把黑色?jié)點(diǎn)變?yōu)榧t色。
• 左旋轉(zhuǎn)：逆時(shí)針旋轉(zhuǎn)紅黑樹的兩個(gè)節(jié)點(diǎn)，使得父節(jié)點(diǎn)被自己的右孩子取代，而自己成為自己的左孩子。說(shuō)起來(lái)很怪異，大家看下圖：

• 右旋轉(zhuǎn)：順時(shí)針旋轉(zhuǎn)紅黑樹的兩個(gè)節(jié)點(diǎn)，使得父節(jié)點(diǎn)被自己的左孩子取代，而自己成為自己的右孩子。大家看下圖：

場(chǎng)景：HashMap TreeSet TreeMap

4、 B樹：

設(shè)計(jì)緣由：

數(shù)據(jù)庫(kù)索引是存儲(chǔ)在磁盤上的，當(dāng)數(shù)據(jù)量比較大的時(shí)候，索引的大小可能有十幾個(gè)G，甚至更多。當(dāng)我們利用索引查詢的時(shí)候，能把整個(gè)索引全部加載到內(nèi)存嗎？顯然不可能，能做的只有逐一加載每一個(gè)磁盤頁(yè)，這里的磁盤頁(yè)對(duì)應(yīng)著索引樹的節(jié)點(diǎn)。

如果我們利用二叉查找樹作為索引結(jié)構(gòu)，那么最壞（每個(gè)節(jié)點(diǎn)數(shù)據(jù)在不同磁盤頁(yè)上）的情況下，磁盤IO次數(shù)等于索引樹的高度。 所以，為了減少磁盤IO次數(shù)，我們就需要把原本“瘦高”的樹結(jié)構(gòu)變得“矮胖”（節(jié)點(diǎn)數(shù)變少了）。這就是B樹的特征之一

B樹是一種多路平衡查找樹，它的每一個(gè)節(jié)點(diǎn)最多包含m個(gè)孩子，m被稱為B樹的階，m的大小取決于磁盤頁(yè)的大小。——一個(gè)節(jié)點(diǎn)最多包含一個(gè)磁盤頁(yè)的數(shù)據(jù)

也就是說(shuō)，當(dāng)B樹變得矮胖以后，每個(gè)節(jié)點(diǎn)可以包含多個(gè)數(shù)據(jù)（數(shù)據(jù)量大小由磁盤頁(yè)的大小決定），同樣的數(shù)據(jù)，B樹比二叉樹/紅黑樹節(jié)點(diǎn)少。所以，B樹在查詢時(shí)，磁盤IO次數(shù)變少了，從而可以提升查找性能。

特征：

一個(gè)m階的B樹具有如下幾個(gè)特征：

1.根結(jié)點(diǎn)至少有兩個(gè)子女。
2.每個(gè)中間節(jié)點(diǎn)都包含k-1個(gè)元素和k個(gè)孩子，其中 m/2 <= k <= m
3.每一個(gè)葉子節(jié)點(diǎn)都包含k-1個(gè)元素，其中 m/2 <= k <= m
4.所有的葉子結(jié)點(diǎn)都位于同一層。
5.每個(gè)節(jié)點(diǎn)中的元素從小到大排列，節(jié)點(diǎn)當(dāng)中k-1個(gè)元素正好是k個(gè)孩子包含的元素的值域分劃

場(chǎng)景：

B樹主要應(yīng)用于文件系統(tǒng)以及部分?jǐn)?shù)據(jù)庫(kù)索引，比如著名的非關(guān)系型數(shù)據(jù)MongoDB。 而大部分關(guān)系型數(shù)據(jù)庫(kù)，比如mysql，則使用B+樹作為索引

5、 B+樹

B+樹是B樹的一種變體，但是又有所不同，

特征：

一個(gè)m階的B+樹具有如下幾個(gè)特征：

• 1.有k個(gè)子樹的中間節(jié)點(diǎn)包含有k個(gè)元素（B樹中是k-1個(gè)元素），每個(gè)元素不保存數(shù)據(jù)，只用來(lái)索引，所有數(shù)據(jù)都保存在葉子節(jié)點(diǎn)。
• 2.所有的葉子結(jié)點(diǎn)中包含了全部元素的信息，及指向含這些元素記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。
• 3.所有的中間節(jié)點(diǎn)元素都同時(shí)存在于子節(jié)點(diǎn)，在子節(jié)點(diǎn)元素中是最大（或最?。┰?。

這里特別要注意有兩點(diǎn)：

其一：每個(gè)父節(jié)點(diǎn)的元素都出現(xiàn)在子節(jié)點(diǎn)中，是子節(jié)點(diǎn)的最大（或最?。┰?；因此所有葉子節(jié)點(diǎn)包含了全量元素信息；

其二：每個(gè)葉子節(jié)點(diǎn)都帶有指向下一個(gè)節(jié)點(diǎn)的指針，形成了一個(gè)有序鏈表；

其三：只有葉子節(jié)點(diǎn)帶有衛(wèi)星數(shù)據(jù)，其余中間節(jié)點(diǎn)僅僅是索引，沒(méi)有任何數(shù)據(jù)關(guān)聯(lián)，如下圖，所謂衛(wèi)星數(shù)據(jù)，指的是索引元素所指向的數(shù)據(jù)記錄，比如數(shù)據(jù)庫(kù)中的某一行，在B樹種，無(wú)論中間節(jié)點(diǎn)還是葉子節(jié)點(diǎn)都帶有衛(wèi)星數(shù)據(jù)。

設(shè)計(jì)優(yōu)勢(shì)

B+樹的好處主要體現(xiàn)在查詢性能上，由于B+樹的中間節(jié)點(diǎn)沒(méi)有衛(wèi)星數(shù)據(jù)，所以同樣大小的磁盤頁(yè)可以容納更多的節(jié)點(diǎn)元素，這就意味著，一次性加載到內(nèi)存中的節(jié)點(diǎn)元素更多，從而使得查詢時(shí)IO次數(shù)也更少。(舉個(gè)簡(jiǎn)單的例子，一個(gè)磁盤頁(yè)可以加載B樹的100個(gè)節(jié)點(diǎn)元素，但是可以加載B+樹的1000個(gè)節(jié)點(diǎn)元素，那么對(duì)于查找999這個(gè)數(shù)來(lái)說(shuō)，B數(shù)需要10次IO，B+數(shù)只需要1次IO)

B+樹相對(duì)B樹的優(yōu)點(diǎn)：

• IO一次讀數(shù)據(jù)是從磁盤上讀的，磁盤容量是固定的，取數(shù)據(jù)量大小是固定的，非葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，節(jié)點(diǎn)小，磁盤IO次數(shù)就少。
• B+樹查詢性能穩(wěn)定，因?yàn)锽+樹的查詢必須最終查找到葉子節(jié)點(diǎn)； 而B樹，只要找到匹配元素即可，無(wú)論匹配元素處于中間節(jié)點(diǎn)，還是葉子節(jié)點(diǎn)。所以B樹的查詢性能并不穩(wěn)定，最好情況是只查根節(jié)點(diǎn)，最壞情況是查到葉子節(jié)點(diǎn)
• B+樹的所有Data域在葉子節(jié)點(diǎn)，一般來(lái)說(shuō)都會(huì)進(jìn)行一個(gè)優(yōu)化，就是將所有的葉子節(jié)點(diǎn)用指針串聯(lián)起來(lái)（可以認(rèn)為是鏈表），遍歷葉子節(jié)點(diǎn)就能獲取全部數(shù)據(jù)，這樣就能進(jìn)行區(qū)間訪問(wèn)了。 B樹做范圍查詢，只能繁瑣的遍歷，但是B+樹，只需要查到查找到范圍下限以后，遍歷葉子節(jié)點(diǎn)（有序鏈表）就可以了。

綜合起來(lái)，B+樹比B樹的優(yōu)勢(shì)有三個(gè)：1、IO次數(shù)更少；2、查詢性能更佳；3、范圍查詢簡(jiǎn)便

場(chǎng)景：Mysql索引

6、紅黑樹 VS B+樹

紅黑樹的深度比B+樹大，當(dāng)數(shù)據(jù)量小時(shí)，可以把數(shù)據(jù)完全放到內(nèi)存中，紅黑樹的時(shí)間復(fù)雜度比B樹低（不用每次都查到葉子節(jié)點(diǎn)），如linux中進(jìn)程的調(diào)度用的是紅黑樹，Java中HashMap、TreeMap、TreeSet（都在內(nèi)存中操作）也都是用紅黑樹實(shí)現(xiàn)；

但是，當(dāng)數(shù)據(jù)量大時(shí)，不能一次性把數(shù)據(jù)放到內(nèi)存時(shí)，紅黑樹往往出現(xiàn)由于樹的深度過(guò)大而造成磁盤IO讀寫過(guò)于頻繁，進(jìn)而導(dǎo)致效率低下；而B樹因其讀磁盤次數(shù)少，具有更快的速度。

到此這篇關(guān)于關(guān)于Java的二叉樹、紅黑樹、B+樹詳解的文章就介紹到這了,更多相關(guān)Java二叉樹、紅黑樹、B+樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論