01.22 深入淺出Java Tree

在計算機中，樹隨處可在，可說是圖論和計算機科學中的重中之重，理解樹的結構、樹的思想和樹的優異性質對於程序設計大有裨益！

一、前言

我們都知道，數組的特點是查詢快，直接可以通過下標獲取元素，時間複雜度為O(1)；但是當我們在指定的位置插入元素或者刪除元素的時候，數組下標和所對應的元素是需要重新排列的，所需要的時間複雜度為O(n)！

所以對於頻繁的插入、刪除的場景，不建議採用有序數組！

可能有的朋友會想到，對於需要頻繁的插入、刪除的場景，可以使用鏈表結構，因為對於鏈表結構來說，在進行插入或者刪除的時候，只需要改變元素的前驅或者後繼節點的引用就可以了，所需要的時間複雜度為O(1)；但是如果我們想查詢指定的內容時候，需要遍歷鏈表元素並逐步判斷，直到查找到目標元素為止，所需要的時間複雜度為O(n)！

所以對於查找頻繁的數據，不建議使用鏈表！

哪有沒有一種查詢速度快、插入刪除也很快的一種數據結構呢？

樹就是其中一個！樹這種數據結構，在計算機領域中有著很多的實際應用！比如說：

• mysql 數據庫的索引就是 B+ 樹結構，查找效率極高；
• Windows OS 的文件系統結構也是採用 B+ 樹進行存儲的；
• Linux 的文件系統結構同樣也是採用 B+ 樹進行存儲的；

二、樹介紹

說到樹這種數據結構，相信很多人首先想到的就是二叉樹！

不錯，二叉樹作為一個很重要的數據結構，在某些情況下既可以滿足我們要求查詢快的特點同時也可以滿足插入刪除也快的要求。

當然，在生活中我們可以看到樹，其實是分很多種類的，我們剛剛也說了在某些情況下，假如一個樹是任意自由的結構，那麼它可能既達不到查詢快也達不到插入刪除快的要求，因此我們需要給樹作出一些定義。

在現實中，樹是一個根朝下、葉朝上的結構，而在計算機科學中，樹是由n個有限節點組成一個具有層次關係的集合，看起來像一顆倒掛的樹，根朝上、葉朝下，特點如下：

• 每個節點都只有有限個子節點或無子節點；
• 沒有父節點的節點稱為根節點；
• 每一個非根節點有且只有一個父節點；
• 除了根節點外，每個子節點可以分為多個不相交的子樹；
• 樹裡面沒有環路；

計算機科學中，樹的定義：

如下圖，看起來像一顆樹，但不是樹結構：

雖然樹做出了一些基本定義，但是不足以滿足我們的需求，在計算機科學中，樹可以被分為以下幾種類型：

• 無序樹：樹中任意節點的子節點之間沒有順序關係，這種樹稱為無序樹，也稱為自由樹；
• 有序樹：樹中任意節點的子節點之間有順序關係，這種樹稱為有序樹；

對於無序樹，也就是那種自由樹結構，沒有任何規律，所以無從查找，這種結構一般不考慮；而有序樹，因為各個子節點存在一個的順序關係，那麼在查詢的時候，就可以以此為基礎進行查找！

當然，有序樹又可以進行種類細分，內容如下：

• 二叉樹：每個節點最多含有兩個子樹的樹稱為二叉樹；
• B 樹：一種平衡的多路查找（又稱排序）樹，能夠保持數據有序，擁有多於兩個子樹；

上文說到的二叉樹其實就是有序樹的一種，在程序開發中，用的也是最多的一種樹形結構！

而對於B 樹，主要在文件系統和數據庫領域中有所應用，像 Linux 操作系統的文件系統就是使用 B+ 樹進行文件的存儲。

三、二叉樹

在計算機科學中，二叉樹（英文名：Binary Tree）是每個結點最多有兩個子樹的樹結構，通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。

按照這個定義，在邏輯上二叉樹可以進行五種基本形態的分類：

• 1、空二叉樹；
• 2、只有一個根結點的二叉樹；
• 3、只有左子樹的二叉樹；
• 4、只有右子樹的二叉樹；
• 5、擁有左、右子樹的二叉樹；

3.1、樹的種類

對於 1～4 種形態的二叉樹，形狀比較簡單，對於第 5 種既有左子樹又有右子樹的二叉樹，在形態上比較複雜，我們也可以進行特殊類型細分，內容如下：

• 完全二叉樹：若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第h層有葉子結點，並且葉子結點都是從左到右依次排布，這樣的二叉樹被稱為完全二叉樹；
• 滿二叉樹：所有葉節點都在最底層的完全二叉樹；
• 平衡二叉樹：當且僅當任何節點的兩棵子樹的高度差不大於1的二叉樹；

3.1.1、完全二叉樹

完全二叉樹是一種特殊的二叉樹，特性如下：

• 所有葉子節點都出現在 k 或者 k-1 層，而且從 1 到 k-1 層必須達到最大節點數；
• 第 k 層可以不是滿的，但是第 k 層的所有節點必須集中在最左邊；
• 任何一個節點不能只有左子樹沒有右子樹；
• 葉子節點出現在最後一層或者倒數第二層，不能再往上；

在實際的開發中也有所應用，完全二叉樹會使用二叉查找樹算法（會在下文介紹），來保證查找的數據是有序的

當我們用數組存儲一個完全二叉樹時，以上面圖中完全二叉樹為例，標號為 2 的節點，它在數組中的位置也是 2，它的父節點就是 (k/2 = 1)，它的孩子節點分別是 (2k=4)和 (2k+1=5)，別的節點也是類似。

因為葉子節點的位置比較規律，所有查詢排序效率比較高，比如

3.1.2、滿二叉樹

除最後一層結點均無任何子節點外，每一層的所有結點都有兩個子結點的樹，稱為滿二叉樹！

也就是說，如果一個二叉樹的層數為K，且結點總數是(2^k) -1，滿二叉樹形狀：

滿二叉樹，特性完全同完全二叉樹

3.1.3、平衡二叉樹

平衡二叉樹的提出就是為了保證樹不至於太傾斜，儘量保證兩邊平衡，特性如下：

• 平衡二叉樹要麼是一棵空樹；
• 要麼保證左右子樹的高度之差不大於 1；
• 左右兩個子樹都是一棵平衡二叉樹；

平衡二叉樹的常用實現方法有紅黑樹、AVL、替罪羊樹、Treap、伸展樹等。

像 JDK1.8 中 HashMap、TreeMap 等就使用到了紅黑樹實現。

3.2、二叉查找樹

上面介紹了完全二叉樹、滿二叉樹、平衡二叉樹都屬於特殊類型的二叉樹，需要我們從邏輯上去控制才可以滿足要求！

上文中我們說到，二叉樹的出現就是為了解決查詢效率問題，按照二分進行查找，每次查詢只需要選擇其中一個子樹就進行查找，從而減少查找次數，提升查詢效率！

那麼我們如何進行二分查找呢？

這就要求查找的數據必須是有序的，每次查找、插入刪除時都要維護一個有序的數據集，於是就有了二叉查找樹這個概念，英文全稱 Binary Search Tree，簡稱 BST。

二叉查找樹，也被稱為二叉排序樹，可以說是從算法層面來定義二叉樹結構，這種算法思路適用於所有的二叉樹結構，特性如下：

• 若左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
• 若右子樹不空，則右子樹上所有結點的值均大於或等於它的根結點的值；
• 它的左、右子樹也分別為二叉查找樹；

二叉查找樹，在最好的情況下，按照折半查找，查詢效率得到提升，時間複雜度為O（logn）；但是，如果構成的二叉排序樹蛻變為單支樹，樹的深度為 n，其查找時間複雜度與順序查找一樣為O(n)。

如果二叉查找樹變成了單支樹，查詢效率就大大折扣了，於是就有平衡二叉查找樹的出現！

3.3、平衡二叉查找樹

平衡二叉查找樹，又稱 AVL 樹，因為算法的發明者為Adel'son-Vel'skii和 Landis，被稱為 AVL 樹來自於大神的姓名縮寫組合。

它除了具備二叉查找樹的基本特徵之外，還具有一個非常重要的特點：

• 它的左子樹和右子樹都是平衡二叉樹;
• 且它的左子樹和右子樹的深度之差的絕對值（平衡因子 ） 不超過1；

也就是說 AVL 樹每個節點的平衡因子只可能是-1、0和1（平衡因子算法：左子樹高度減去右子樹高度）。

那麼如何保證二叉查找樹在添加元素的同時保證節點平衡呢？

基本思想就是：當在二叉排序樹中插入一個節點時，首先檢查是否因插入而破壞了平衡，若破壞，則找出其中的最小不平衡二叉樹，在保持二叉查找樹特性的情況下，調整最小不平衡子樹中節點之間的關係，以達到新的平衡。

所謂最小不平衡子樹是指：離插入節點最近且以平衡因子的絕對值大於1的節點作為根的子樹。

當新插入的節點導致樹結構發生失衡就會進行調整，主要操作有左旋轉、右旋轉操作！

3.3.1、繞某元素左旋轉

從圖中可以看出，在插入數據 100 之前，左圖 BST 樹只有 80 節點的平衡因子是 -1（左子樹高度減去右子樹高度），但整棵樹還是平衡的。

插入 100 之後，80節點的平衡因子就成為了-2，此時平衡被破壞，需要進行調整，繞節點 90 進行左旋轉，最終樹型結構變成右圖。

左旋轉場景：當樹中節點 X 的右孩子的右孩子上插入新元素，且平衡因子從 -1 變成 -2 後，就需要繞節點 X 進行左旋轉！

3.3.2、繞某元素右旋轉

從圖中可以看出，在插入數據 30 之前，左圖 BST 樹只有 80 節點的平衡因子是 1（左子樹高度減去右子樹高度），但整棵樹還是平衡的。

插入 30 之後，80節點的平衡因子就成為了 2，此時平衡被破壞，需要進行調整，繞節點 50 進行右旋轉，最終樹型結構變成右圖。

右旋轉場景：當樹中節點 X 的左孩子的左孩子上插入新元素，且平衡因子從 1 變成 2 後，就需要繞節點 X 進行右旋轉。

3.3.3、繞某元素的左子節點左旋轉，接著再繞該元素自己右旋轉

很多時候，插入元素一次調整滿足不了要求，如下圖就是左旋與右旋的結合，具體操作時可以分解成這兩種操作，只是圍繞點不一樣而已。

3.3.4、繞某元素的右子節點右旋轉，接著再繞該元素自己左旋轉

與之對應的，也有右旋與左旋的結合，如下圖：

由此可見，通過左旋轉、右旋轉操作，平衡二叉樹不會出現普通二叉查找樹的最差情況，其查找的時間複雜度為O（logN）！

在查詢的時候，操作與普通二叉查找樹上的查找操作相同；插入的時候，每一次插入結點操作最多隻需要單旋轉或雙旋轉，總體上插入操作的代價仍然在O（logN）級別；如果是動態刪除，刪除之後必須檢查從刪除結點開始到根結點路徑上的所有結點的平衡因子，最多可能需要O（logN）次旋轉。

為了解決儘可能少的旋轉調整，紅黑樹出現了！

3.4、紅黑樹

紅黑樹，英文名稱：red-black tree，簡稱 RBT！紅黑樹也是基於平衡二叉樹結構的一種實現，但是它的平衡指標沒有像 AVL 算法那樣要求很嚴格，並不是高度平衡但基本平衡，特性如下：

• 每一個結點要麼是紅色，要麼是黑色；
• 根結點是黑色的；
• 所有葉子結點都是黑色的（實際上都是Null指針，下圖用NIL表示）。葉子結點不包含任何關鍵字信息，所有查詢關鍵字都在非終結點上；
• 每個紅色結點的兩個子節點必須是黑色的。換句話說：從每個葉子到根的所有路徑上不能有兩個連續的紅色結點；
• 從任一結點到其每個葉子的所有路徑都包含相同數目的黑色結點；
• 
  

紅黑樹，在查找方面，與普通二叉查找樹上的查找操作相同；在插入、刪除方面，調整方式和平衡二叉查找樹類似，一樣是左旋轉、右旋轉，其中紅黑樹還增加一個調整操作：節點顏色轉換。

從上面的特性可以看出，從每個葉子到根的所有路徑上不能有兩個連續的紅色結點，對於不滿足特性的節點顏色，只需要轉換顏色一些即可，比較簡單！

紅黑樹，在插入的時候，與 AVL 一樣，結點最多隻需要2次旋轉；在刪除的時候，因為沒有像 AVL 那樣高度平衡的要求，刪除一個結點最多隻需要3次旋轉操，可見紅黑樹的刪除操作代價要比 AVL 要好的多；因為不是高度平衡，在查詢方面，紅黑樹在查詢效率方面稍遜於 AVL，但是比二叉查找樹強很多！

在 JDK 中就有很多紅黑樹的具體實現，最典型的就是 JDK1.8 中的 HashMap，當衝突鏈表長度大於 8 時，鏈表就會以紅黑樹結構存儲。

3.5、哈夫曼樹

哈夫曼樹是一種特殊結構的二叉樹，主要由哈夫曼編碼實現，內容定義如下：

給定N個權值作為N個葉子結點，構造一棵二叉樹，若這棵二叉樹的帶權路徑長度達到最小，則稱這樣的二叉樹為最優二叉樹，也稱為Huffman樹。

哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。

哈夫曼編碼的由來！

1951年，哈夫曼在麻省理工學院（MIT）攻讀博士學位，他和修讀信息論課程的同學正在想選擇是完成學期報告還是期末考試。此時的導師羅伯特·法諾（Robert Fano）出的學期報告題目是：查找最有效的二進制編碼。

由於無法證明哪個已有編碼是最有效的，哈夫曼放棄對已有編碼的研究，轉向新的探索，最終發現了基於有序頻率二叉樹編碼的想法，並很快證明了這個方法是最有效的。

哈夫曼使用自底向上的方法構建二叉樹，避免了次優算法香農-範諾編碼（Shannon–Fano coding）的最大弊端──自頂向下構建樹。

並於1952年，在論文《一種構建極小多餘編碼的方法》（A Method for the Construction of Minimum-Redundancy Codes）中發表了這個編碼方法。

四、B樹

在上文中講的 BST、AVL、RBT 都是典型的二叉查找樹結構，其查找的時間複雜度與樹高相關。

降低樹的高度可以提高查找效率，另外還有一個比較實際的問題：就是大量數據存儲中，實現查詢這樣一個實際背景下，平衡二叉樹由於樹深度過大而造成磁盤IO讀寫過於頻繁，進而導致效率低下。

那麼如何減少樹的高度，一個基本的想法就是：

• 每個節點存儲多個元素；
• 摒棄二叉樹結構，採用多叉樹；

這樣我們就提出來了一個新的查找樹結構 ——多路查找樹，根據 AVL 給我們的啟發，一顆平衡多路查找樹可以使得數據的查找效率保證在O(logN)這樣的對數級別上。

在計算機科學中，平衡多路查找樹，簡稱為B樹，每個節點可以擁有2個以上的子節點，能夠保持數據有序。

這種數據結構能夠讓查找數據、順序訪問、插入數據及刪除的動作，都在對數時間內完成。

與自平衡二叉查找樹不同，B 樹適用於讀寫相對大的數據塊的存儲系統，例如磁盤。

B樹減少定位記錄時所經歷的中間過程，從而加快存取速度。這種數據結構常被應用在數據庫和文件系統的實現上。

4.1、B- 樹

B~樹，也就是我們常說的 B 樹，其實 B~樹和 B 樹是同一種樹，我們知道 B 樹是多叉結構，假如給定一個變量 m 來指定多叉，一棵 m 階的 B~樹（m叉樹）的特性如下：

• 排序方式：所有節點關鍵字是按遞增次序排列，並遵循左小右大原則；
• 子節點數：非葉節點的子節點數>1，且<=M ，且M>=2，空樹除外（注：M階代表一個樹節點最多有多少個查找路徑，M=M路，當M=2則是2叉樹，M=3則是3叉）；
• 關鍵字數：枝節點的關鍵字數量大於等於ceil(m/2)-1個且小於等於M-1個（注：ceil()是個朝正無窮方向取整的函數 如ceil(1.1)結果為2);
• 所有葉子節點均在同一層、葉子節點除了包含了關鍵字和關鍵字記錄的指針外也有指向其子節點的指針只不過其指針地址都為null對應下圖最後一層節點的空格子;

例如：下面就是一棵3階B~樹，如圖所示：

B樹相對於平衡二叉樹的不同是，每個節點包含的關鍵字增多了，特別是在 B 樹應用到數據庫中的時候，數據庫充分利用了磁盤塊的原理，把節點大小限制和充分使用在磁盤快大小範圍；把樹的節點關鍵字增多後樹的層級比原來的二叉樹少了，減少數據查找的次數和複雜度。

4.2、B+ 樹

B+樹是B樹的一個升級版，相對於B樹來說B+樹更充分的利用了節點的空間，讓查詢速度更加穩定，其速度完全接近於二分法查找。

一棵m階的B+樹和m階的B-樹的差異，內容如下：

• 有n棵子樹的結點中含有n個關鍵字；（B~樹是n棵子樹有n+1個關鍵字）
• 所有的葉子結點中包含了全部關鍵字的信息，及指向含有這些關鍵字記錄的指針，且葉子結點本身依關鍵字的大小自小而大的順序鏈接；（B~樹的葉子節點並沒有包括全部需要查找的信息）
• 所有的非終端結點可以看成是索引部分，結點中僅含有其子樹根結點中最大（或最小）關鍵字；（B~樹的非終節點也包含需要查找的有效信息）

例如：下面就是一棵3階B+樹，我們可以和B~樹做一個明顯的對比，如圖所示：

B+ 樹相比B樹的優勢如下：

• B+樹的層級更少：相較於B樹，B+每個非葉子節點存儲的關鍵字數更多，樹的層級更少所以查詢數據更快；
• B+樹查詢速度更穩定：B+所有關鍵字數據地址都存在葉子節點上，所以每次查找的次數都相同，所以查詢速度要比B樹更穩定;
• B+樹天然具備排序功能：B+樹所有的葉子節點數據構成了一個有序鏈表，在查詢大小區間的數據時候更方便，數據緊密性很高，緩存的命中率也會比B樹高。
• B+樹全節點遍歷更快：B+樹遍歷整棵樹只需要遍歷所有的葉子節點即可，而不需要像B樹一樣需要對每一層進行遍歷，這有利於數據庫做全表掃描。

但B樹也不是完全沒有優勢，B樹相對於B+樹的優點是：如果經常訪問的數據離根節點很近，而B樹的非葉子節點本身存有關鍵字其數據的地址，所以這種數據檢索的時候會要比B+樹快。

4.3、B*樹

B*樹，是 B+樹的變體，在 B+樹的非根和非葉子結點上增加了指向兄弟的指針，不同之處如下：

• 先是關鍵字個數限制問題，B+樹初始化的關鍵字初始化個數是cei(m/2)，B*樹的初始化個數為（cei(2/3*m)）；
• B+樹節點滿時就會分裂，而B*樹節點滿時會檢查兄弟節點是否滿（因為每個節點都有指向兄弟的指針），如果兄弟節點未滿則向兄弟節點轉移關鍵字，如果兄弟節點已滿，則從當前節點和兄弟節點各拿出1/3的數據創建一個新的節點出來；

B*樹相比B+樹的優勢：在B+樹的基礎上因其初始化的容量變大，使得節點空間使用率更高，而在非根和非葉子結點上增加指向兄弟的指針，可以向兄弟節點轉移關鍵字的特性使得B*樹的分解次數變得更少！

五、總結

關於樹的故事，基本介紹完了，內容比較多，尤其B樹模型，比較深奧複雜，有興趣的朋友可以自己研究一些，如果有理解不當的地方，歡迎網友指出！

六、參考

2、維基百科 - 樹

3、掘金 - 西召 - 樹結構與Java實現

4、掘金 - 張拭心 - 二叉樹、平衡二叉樹、二叉查找樹

5、iteye - Heart.X.Raid - 動態查找樹比較

6、知乎 - 勤勞的小手 - 平衡二叉樹、B樹、B+樹、B*樹

閱讀更多 科技伍小黑 的文章

關鍵字: 數據結構 數據庫 操作系統