一味抖、集合框架源碼分析

• 集合框架 （第 01 篇） 源碼分析：Collection<E> 框架總覽
• 集合框架 （第 02 篇） 源碼分析：Map<K,V > 框架總覽
• 集合框架 （第 03 篇） 源碼分析：ArrayList<E>
• 集合框架 （第 04 篇） 源碼分析：LinkedList
• 集合框架 （第 05 篇） 源碼分析：Map<K, V>接口與其內(nèi)部接口Entry<K,V>
• 集合框架 （第 06 篇） 源碼分析：哈希沖突(哈希碰撞)與解決算法
• 集合框架 （第 07 篇） 源碼分析：jdk1.7版 HashMap
• 集合框架 （第 08 篇） 源碼分析：HashMap、Hashtable灰粮、ConcurrentHashMap之間的區(qū)別
• 集合框架 （第 09 篇） 源碼分析：jdk1.7版 ConcurrentHashMap
• 集合框架 （第 10 篇） 源碼分析：二叉樹仔涩、平衡二叉樹、二叉查找樹粘舟、AVL樹熔脂、紅黑樹
• 集合框架 （第 11 篇） 源碼分析：jdk1.8版 HashMap
• 集合框架 （第 12 篇） 源碼分析：jdk1.8版 ConcurrentHashMap
• 集合框架 （第 13 篇） 源碼分析：LinkedHashMap
• 集合框架 （第 14 篇） 源碼分析：TreeMap
• 集合框架 （第 15 篇） 源碼分析：Set<E> 集合
• 集合框架 （第 16 篇） 源碼分析：BlockingQueue 接口
• 集合框架 （第 17 篇） 源碼分析：CopyOnWriteArrayList 與 CopyOnWriteArraySet

原文持續(xù)更新鏈接: https://github.com/about-cloud/JavaCore

正文

tree

一、樹

浩瀚宇宙蓖乘，從 點(diǎn) 到線，線到面韧骗，面到體嘉抒，組成了豐富多彩的世界。動(dòng)物袍暴、植物和其他物體正是存儲(chǔ)在 宇宙 這個(gè)數(shù)據(jù)結(jié)構(gòu)中些侍。

前幾篇文章介紹了 線性 的數(shù)據(jù)結(jié)構(gòu): ArrayList隶症、LinkedList及其組合HashMap。從 線性 數(shù)據(jù)結(jié)構(gòu)到 非線性 數(shù)據(jù)結(jié)構(gòu)岗宣，就像 樹干 發(fā)叉一樣：

line to tree

從數(shù)據(jù)結(jié)構(gòu)進(jìn)化的角度來看蚂会，樹(tree) 的生成是 鏈表 進(jìn)化而來。鏈(Linked) 每個(gè)節(jié)點(diǎn)最多只有一個(gè) 前驅(qū)節(jié)點(diǎn) 耗式，那么可以稱這個(gè) 鏈 為 ??樹(tree) 胁住。數(shù)據(jù)結(jié)構(gòu)中的樹就像一顆倒掛的樹。

鏈表 只不過是特殊的樹刊咳，就像樹沒有樹枝只有樹干一樣彪见。

樹的基本術(shù)語

1. 節(jié)點(diǎn)(Node)：樹中的每個(gè)元素稱為 節(jié)點(diǎn)(Node)；
2. 根節(jié)點(diǎn)(Root Node)：樹最頂端的節(jié)點(diǎn)被稱為根節(jié)點(diǎn)（樹根）娱挨，根節(jié)點(diǎn)無父節(jié)點(diǎn)余指；
3. 父節(jié)點(diǎn)(Parent Node)：節(jié)點(diǎn)的（上面的）前驅(qū)節(jié)點(diǎn)在樹中被稱為父節(jié)點(diǎn)；
4. 子節(jié)點(diǎn)(Child Node)：（下面的）后繼節(jié)點(diǎn)被稱為子節(jié)點(diǎn)跷坝；
5. 子樹(Subtree)：子節(jié)點(diǎn)及其下面的節(jié)點(diǎn)組成的樹稱為子樹 酵镜；
6. 一棵樹最多只有一個(gè)根節(jié)點(diǎn)，樹中的每個(gè)子節(jié)點(diǎn)最多只有一個(gè)父節(jié)點(diǎn)柴钻；
7. 節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度（葉子節(jié)點(diǎn)的度為0）淮韭；
8. 葉節(jié)點(diǎn)(Leaf Node)（葉子節(jié)點(diǎn)或終端節(jié)點(diǎn)）：度為0的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)（也就是沒有子節(jié)點(diǎn)的節(jié)點(diǎn)稱為葉子節(jié)點(diǎn)）；
9. 非終端節(jié)點(diǎn) 或分支節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)（擁有子節(jié)點(diǎn)的節(jié)點(diǎn)）顿颅；
10. 兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)缸濒；
11. 樹的度：一棵樹中，節(jié)點(diǎn)中最大的度稱為樹的度粱腻；
12. 節(jié)點(diǎn)的層次：從根開始定義起庇配，根為第1層，根的子節(jié)點(diǎn)為第2層绍些，以此類推捞慌；
13. 樹的高度或深度：樹中節(jié)點(diǎn)的最大層次；
14. 堂兄弟節(jié)點(diǎn)：雙親在同一層的節(jié)點(diǎn)互為堂兄弟柬批；
15. 節(jié)點(diǎn)的祖先：從該節(jié)點(diǎn)上溯至根節(jié)點(diǎn)啸澡，所經(jīng)分支上的所有節(jié)點(diǎn)；
16. 子孫節(jié)點(diǎn)：該節(jié)點(diǎn)下面所有所有的節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子孫節(jié)點(diǎn)氮帐；
17. 空樹：沒有節(jié)點(diǎn)的樹稱為空樹嗅虏；
18. 森林：由多棵互不相交（沒有重疊節(jié)點(diǎn)）的樹組成的集合稱為森林（單棵樹可以認(rèn)為是特殊的森林）；

二上沐、二叉樹

二叉樹是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)子樹的樹皮服。子樹通常被稱為左子樹(Left subtree)和右子樹(Right subtree)。

BinaryTree

二叉樹的特性

1. 在非空二叉樹的 i 層上，至多有 個(gè)節(jié)點(diǎn)(i>=1)龄广；
2. 在深度為 d 的二叉樹上最多有 2d-1 個(gè)結(jié)點(diǎn)（d>=1);
3. 對(duì)于任何一棵非空的二叉樹,如果葉節(jié)點(diǎn)個(gè)數(shù)為 n0硫眯，度數(shù)為 2 的節(jié)點(diǎn)個(gè)數(shù)為 n2，則有: n0 = n2 + 1择同。

二叉樹的遍歷

二叉樹遍歷：從樹的根節(jié)點(diǎn)出發(fā)两入，按照某種 次序 依次訪問二叉樹中所有的節(jié)點(diǎn)，使得每個(gè)節(jié)點(diǎn)被訪問僅且一次敲才。

這里有兩個(gè)關(guān)鍵詞：訪問 和 次序裹纳。訪問 包括 增刪改查， 次序 包括 前序归斤、中序痊夭、后序，前中后是以樹的根節(jié)點(diǎn)作為參照物脏里，又規(guī)定不管如何遍歷 左子樹 的訪問順序要排在 右子樹 前面（左邊）她我。

1、前序遍歷（先序遍歷）

遍歷步驟：先訪問根節(jié)點(diǎn)迫横，然后再先序遍歷左子樹番舆，最后再先序遍歷右子樹即 根—左—右。

先序遍歷

上圖先序遍歷的結(jié)果：

2矾踱、中序遍歷

遍歷步驟：先中序遍歷左子樹恨狈，然后再訪問根節(jié)點(diǎn)，最后再中序遍歷右子樹即 左—根—右呛讲。

中序遍歷

上圖中序遍歷的結(jié)果：

3禾怠、后序遍歷

遍歷步驟：先后序遍歷左子樹，再后序遍歷右子樹贝搁，最后再訪問根節(jié)點(diǎn)吗氏，即 左—右—根。

后序遍歷

上圖后序遍歷的結(jié)果：

三雷逆、平衡二叉樹

平衡二叉樹（Balanced Binary Tree）的 平衡性 體現(xiàn)在以下幾點(diǎn)：

1. 樹的左弦讽、右子樹的 高度差 的絕對(duì)值不超過1；
2. 任意節(jié)點(diǎn)左膀哲、右子樹也分別平衡二叉樹往产；

一棵數(shù)頻繁的刪除和插入節(jié)點(diǎn)都有可能使數(shù)發(fā)生旋轉(zhuǎn)。平衡二叉樹中訪問節(jié)點(diǎn)的操作(插入某宪、查找仿村、刪除)的時(shí)間復(fù)雜度維持在一個(gè)“平衡”的水準(zhǔn)，既最壞情況和最好情況的時(shí)間復(fù)雜度維持在 O(logN)兴喂。

平衡二叉樹

四蔼囊、二叉查找樹

二叉查找樹(二叉搜索樹 Binary Search Tree)的 查找 特性體現(xiàn)在以下幾點(diǎn)：

1. 如果它的左子樹不空包颁，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；
2. 如果它的右子樹不空压真，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；
3. 任意節(jié)點(diǎn)左蘑险、右子樹也分別為二叉查找樹滴肿。

先序遍歷

二叉查找樹的查找過程

1. 從樹的根節(jié)點(diǎn)開始查找，并沿著這棵樹中的一條簡單路徑向下進(jìn)行佃迄；
2. 若樹為空樹泼差，則查找失敗，返回 null呵俏；
3. 對(duì)于訪問的每個(gè)節(jié)點(diǎn) x堆缘，若指定的值 k 等于結(jié)點(diǎn) x 的值，返回該節(jié)點(diǎn)x 并結(jié)束查找普碎；
4. 若指定的值 k 小于節(jié)點(diǎn) x 的值吼肥，則在節(jié)點(diǎn) x 的左子樹中查找（根據(jù)上面二叉查找樹的性質(zhì)判斷）；
5. 相反麻车，若指定的值 k 大于節(jié)點(diǎn) x 的值缀皱，則查找在節(jié)點(diǎn) x 的右子樹中繼續(xù)；
6. 若查找至 葉子節(jié)點(diǎn) 后仍未匹配到相等值动猬，則表示不存在指定值的節(jié)點(diǎn)啤斗，返回null。

五赁咙、AVL樹（高度平衡樹）

AVL樹 得名于它的兩位發(fā)明者G. M. Adelson-Velsky和E. M. Landis的名字钮莲，樹的特性是：

1. :wink:本身首先是一棵二叉查找樹;
2. 每個(gè)節(jié)點(diǎn)的左右子樹的高度之差的絕對(duì)值（平衡因子）最多為 1 ；

AVL

ALV追求極限的平衡性彼水，優(yōu)點(diǎn)是在查找元素時(shí)崔拥，時(shí)間復(fù)雜度低，查找元素快猿涨。那么問題來了握童，在添加/刪除元素時(shí)，AVL樹為了追求“絕對(duì)的平衡性”叛赚，不斷的通過循環(huán)來達(dá)到自平衡澡绩，增加時(shí)間復(fù)雜度。適所以AVL樹適用于添加/刪除元素少俺附、查找操作多的環(huán)境下肥卡。

六、紅黑樹

紅黑樹（Red Black Tree） 也是一種 平衡二叉樹（而平衡二叉樹又是一種二叉查找樹事镣，所以紅黑樹也是一種二叉查找樹）步鉴，但它不像 AVL樹 那樣追求絕對(duì)的平衡，它這種于查找和添加/刪除之間。特性是：

1. 樹中所有節(jié)點(diǎn)都被染成紅色??或黑色??（官方話語：節(jié)點(diǎn)是紅色或黑色）氛琢；
2. 根節(jié)點(diǎn)和葉子節(jié)點(diǎn)都是黑色??
3. 每個(gè)紅色節(jié)點(diǎn)??的兩個(gè)子節(jié)點(diǎn)都是黑色??（從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)??）喊递；
4. 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)??。

紅黑樹

上述特性構(gòu)成了一個(gè)最關(guān)鍵的約束：從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長路徑不大于最短路徑的兩倍長阳似。

所以紅黑樹可以不是那么絕對(duì)的高度平衡骚勘。對(duì)于在樹中添加/刪除元素，紅黑樹也不像AVL樹那樣撮奏，為了達(dá)到絕對(duì)的自平衡而“使勁費(fèi)力”地旋轉(zhuǎn)整顆樹了俏讹。

最差平衡二叉樹即樹退化成鏈表（可以看成特殊的樹、沒有叉的樹）畜吊，這樣的樹添加/刪除元素快泽疆，不需要自平衡，但是查找慢玲献，最壞情況要遍歷整棵樹殉疼。而從增刪改查的時(shí)間復(fù)雜度來講，紅黑樹 介于 二叉查找樹 和 鏈表 之間捌年，這是在添加/刪除和查找之間一個(gè)折中的選擇株依。

總結(jié)：

鏈表：適用于添加/刪除多、查找少的場景延窜；

二叉查找樹：適用于查找多恋腕、添加/刪除少的場景；

紅黑樹：適用于查找逆瑞、添加荠藤、刪除都多的場景。

七获高、B-Tree哈肖、B+Tree、B*Tree

這種和MySQL的InnoDB索引息息相關(guān)念秧，單獨(dú)拿出一個(gè)章節(jié)去講解淤井，詳見：

https://github.com/about-cloud/JavaCore

原文持續(xù)更新鏈接: https://github.com/about-cloud/JavaCore