在計算機中,樹隨處可在,可說是圖論和計算機科學中的重中之重,理解樹的結構、樹的思想和樹的優異性質對于程序設計大有裨益!
一、前言
我們都知道,數組的特點是查詢快,直接可以通過下標獲取元素,時間複雜度爲O(1);但是當我們在指定的位置插入元素或者刪除元素的時候,數組下標和所對應的元素是需要重新排列的,所需要的時間複雜度爲O(n)!
所以對于頻繁的插入、刪除的場景,不建議采用有序數組!
可能有的朋友會想到,對于需要頻繁的插入、刪除的場景,可以使用鏈表結構,因爲對于鏈表結構來說,在進行插入或者刪除的時候,只需要改變元素的前驅或者後繼節點的引用就可以了,所需要的時間複雜度爲O(1);但是如果我們想查詢指定的內容時候,需要遍曆鏈表元素並逐步判斷,直到查找到目標元素爲止,所需要的時間複雜度爲O(n)!
所以對于查找頻繁的數據,不建議使用鏈表!
哪有沒有一種查詢速度快、插入刪除也很快的一種數據結構呢?
樹就是其中一個!樹這種數據結構,在計算機領域中有著很多的實際應用!比如說:
- mysql 數據庫的索引就是 B+ 樹結構,查找效率極高;
- Windows OS 的文件系統結構也是采用 B+ 樹進行存儲的;
- Linux 的文件系統結構同樣也是采用 B+ 樹進行存儲的;
如下圖,看起來像一顆樹,但不是樹結構:
三、二叉樹
在計算機科學中,二叉樹(英文名:Binary Tree)是每個結點最多有兩個子樹的樹結構,通常子樹被稱作“左子樹”(left subtree)和“右子樹”(right subtree)。
按照這個定義,在邏輯上二叉樹可以進行五種基本形態的分類:
- 1、空二叉樹;
- 2、只有一個根結點的二叉樹;
- 3、只有左子樹的二叉樹;
- 4、只有右子樹的二叉樹;
- 5、擁有左、右子樹的二叉樹;
在實際的開發中也有所應用,完全二叉樹會使用二叉查找樹算法(會在下文介紹),來保證查找的數據是有序的,葉子節點可以按從上到下、從左到右的順序依次添加到數組中。知道一個節點的位置,就可以輕松地算出它的父節點、孩子節點的位置。
滿二叉樹,特性完全同完全二叉樹,但是比完全二叉樹更嚴格,每個葉節點到達根路徑所需的長度都相同!而完全二叉樹的k-1層可以爲葉節點!
平衡二叉樹的常用實現方法有紅黑樹、AVL、替罪羊樹、Treap、伸展樹等。
像 JDK1.8 中 HashMap、TreeMap 等就使用到了紅黑樹實現。
3.2、二叉查找樹
上面介紹了完全二叉樹、滿二叉樹、平衡二叉樹都屬于特殊類型的二叉樹,需要我們從邏輯上去控制才可以滿足要求!
上文中我們說到,二叉樹的出現就是爲了解決查詢效率問題,按照二分進行查找,每次查詢只需要選擇其中一個子樹就進行查找,從而減少查找次數,提升查詢效率!
那麽我們如何進行二分查找呢?
這就要求查找的數據必須是有序的,每次查找、插入刪除時都要維護一個有序的數據集,于是就有了二叉查找樹這個概念,英文全稱 Binary Search Tree,簡稱 BST。
二叉查找樹,也被稱爲二叉排序樹,可以說是從算法層面來定義二叉樹結構,這種算法思路適用于所有的二叉樹結構,特性如下:
- 若左子樹不空,則左子樹上所有結點的值均小于它的根結點的值;
- 若右子樹不空,則右子樹上所有結點的值均大于或等于它的根結點的值;
- 它的左、右子樹也分別爲二叉查找樹;
如果二叉查找樹變成了單支樹,查詢效率就大大折扣了,于是就有平衡二叉查找樹的出現!
3.3、平衡二叉查找樹
平衡二叉查找樹,又稱 AVL 樹,因爲算法的發明者爲Adel’son-Vel’skii和 Landis,被稱爲 AVL 樹來自于大神的姓名縮寫組合。
它除了具備二叉查找樹的基本特征之外,還具有一個非常重要的特點:
- 它的左子樹和右子樹都是平衡二叉樹;
- 且它的左子樹和右子樹的深度之差的絕對值(平衡因子 ) 不超過1;
也就是說 AVL 樹每個節點的平衡因子只可能是-1、0和1(平衡因子算法:左子樹高度減去右子樹高度)。
那麽如何保證二叉查找樹在添加元素的同時保證節點平衡呢?
基本思想就是:當在二叉排序樹中插入一個節點時,首先檢查是否因插入而破壞了平衡,若破壞,則找出其中的最小不平衡二叉樹,在保持二叉查找樹特性的情況下,調整最小不平衡子樹中節點之間的關系,以達到新的平衡。
所謂最小不平衡子樹是指:離插入節點最近且以平衡因子的絕對值大于1的節點作爲根的子樹。
當新插入的節點導致樹結構發生失衡就會進行調整,主要操作有左旋轉、右旋轉操作!
3.3.1、繞某元素左旋轉
從圖中可以看出,在插入數據 30 之前,左圖 BST 樹只有 80 節點的平衡因子是 1(左子樹高度減去右子樹高度),但整棵樹還是平衡的。
插入 30 之後,80節點的平衡因子就成爲了 2,此時平衡被破壞,需要進行調整,繞節點 50 進行右旋轉,最終樹型結構變成右圖。
右旋轉場景:當樹中節點 X 的左孩子的左孩子上插入新元素,且平衡因子從 1 變成 2 後,就需要繞節點 X 進行右旋轉。
3.3.3、繞某元素的左子節點左旋轉,接著再繞該元素自己右旋轉
很多時候,插入元素一次調整滿足不了要求,如下圖就是左旋與右旋的結合,具體操作時可以分解成這兩種操作,只是圍繞點不一樣而已。
由此可見,通過左旋轉、右旋轉操作,平衡二叉樹不會出現普通二叉查找樹的最差情況,其查找的時間複雜度爲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樹。
哈夫曼樹是帶權路徑長度最短的樹,權值較大的結點離根較近。
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樹模型,比較深奧複雜,有興趣的朋友可以自己研究一些,如果有理解不當的地方,歡迎網友指出!
六、參考
1、百度百科 – 樹
2、維基百科 – 樹
3、掘金 – 西召 – 樹結構與Java實現
4、掘金 – 張拭心 – 二叉樹、平衡二叉樹、二叉查找樹
5、iteye – Heart.X.Raid – 動態查找樹比較
6、知乎 – 勤勞的小手 – 平衡二叉樹、B樹、B+樹、B*樹