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

1、二叉查找樹

特性：

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

2、平衡二叉查找樹

特性：

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

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

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

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

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

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

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

3、紅黑樹：

特性：

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

2、每個節(jié)點或者是黑色，或者是紅色；

3、每個葉子節(jié)點是黑色。 [注意：這里葉子節(jié)點，是指為空的葉子節(jié)點??；

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

5、從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑上包含相同數(shù)目的黑節(jié)點，也就是說確保沒有一條路徑會比其他路徑長出倆倍；

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

紅黑樹的操作代價：

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

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

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

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

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

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

場景：HashMap TreeSet TreeMap

4、 B樹：

設(shè)計緣由：

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

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

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

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

特征：

一個m階的B樹具有如下幾個特征：

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

場景：

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

5、 B+樹

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

特征：

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

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

這里特別要注意有兩點：

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

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

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

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

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

B+樹相對B樹的優(yōu)點：

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

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

場景：Mysql索引

6、紅黑樹 VS B+樹

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

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

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

最新評論