前言
面試過程中，多多少少會問一點資料結構（二叉樹）的問題，今天我們來複習一下二叉樹的相關問題，文末總結。
1. 二叉樹的由來
在 jdk1.8 之前，HashMap 的資料結構由「數組+連結清單」組成，數組是 HashMap 的主體，連結清單是為了解決 Hash 沖突引入的，正常的資料存放是直接存在數組中，但如果發生 Hash 沖突就會以連結清單的形式進行存儲，而在 jdk1.8之後，當連結清單的長度超過 8 之後，将會轉換成紅黑樹經常存儲...
相信這一段 HashMap 的描述，一定是大家所熟知的，其實細品之後，我們可以從這段描述中發掘這些資訊。
數組
>
連結清單
樹
。
正所謂有需求就會有發展，我們來看看為什麼在有「數組+連結清單」的情況下，還出來個樹結構。
數組優點：
- 簡單易用，随機通路性強
- 無序數組插入速度很快，效率為O1
- 有序數組查找速度較快，效率為O(logN)
數組缺點：
- 插入和删除效率低
- 數組大小固定，無法動态擴容
連結清單優點：
- 大小不固定，無限擴容
- 插入和删除速度很快
連結清單缺點：
- 查詢效率低，不支援随機查找，必須從第一個開始周遊
- 在連結清單非表頭的位置進行插入、删除很慢，效率為O(N)
從數組到連結清單的優缺點，我們可以看出是各有千秋，不能很準确的說連結清單比數組就一定要高效，而正是因為這種關系的存在，是以二叉樹出現了。
是以二叉樹的由來：二叉樹整合了數組和連結清單的優缺點，使得插入、删除、查找的速度都很快，效率比較高。
2. 二叉樹是什麼
二叉樹是樹形結構的一個重要類型，也是衆多資料結構的基石。
樹有很多類型，每個節點最多隻能有兩個子節點的叫二叉樹。
是以，二叉樹的特性就是每個節點的子結點不允許超過兩個。
3. 二叉查找樹
二叉查找樹是一種特殊的二叉樹，二叉查找樹的特點就是，左子樹節點比父節點小，右子樹節點值比父節點大。
極端現象
二叉查找樹有一種極端的存在，二叉樹的大部分子節點都比父節點值小，然後導緻所有的資料偏向左側，進而退化成連結清單，如下圖所示：
我們使用二叉樹的目的是因為其效率高于連結清單查詢，但這種退化為連結清單的現象很顯然就突兀，怎麼辦呢。
是以為了解決二叉樹退化成一棵連結清單就引入了平衡二叉樹。
4. 平衡二叉樹
平衡二叉樹，又被稱為AVL樹，是為了解決二叉樹退化成一棵連結清單而誕生的。
平衡二叉樹特點：
- 擁有二叉查找樹的全部特性。
- 每個節點的左子樹和右子樹的高度差至多等于1。
其中左右子樹的高度差是通過左旋右旋實作的。
下面是一個平衡二叉樹和非平衡二叉樹的圖：
到底是如何判斷高度差的呢？我們可以來數節點最長連接配接數，比如左側節點最長連接配接數為「3 > 4 > 5」3個節點，右側為「9」一個節點，是以高度差為2。
再比如下面一個平衡二叉樹：
左側最長連接配接點為「3(9) > 7 >11」，即高度為2，右側最長連接配接點為「14(16) > 15 > 18 > 11」，即高度為4，是以高度差為2。
為了維持二叉樹的平衡，平衡二叉樹是通過左旋、右旋來保證的，從大的方向旋轉過程又被分為單旋轉和雙旋轉，總之，旋轉的作用就是避免出現節點偏向一邊的情況，具體左旋、右旋操作在這就不詳細闡述了。
但是平衡二叉樹這種高度差為 1 的要求太嚴格了，尤其是對于頻繁删除、插入的場景非常浪費時間...
5. 紅黑樹
對于那種頻繁删除、插入的場景，平衡二叉樹的調整過程顯然是存在性能問題的，是以為了解決這個問題，進而又引入了紅黑樹。
紅黑樹的特點：
- 具有二叉樹所有特點。
- 每個節點隻能是紅色或者是黑色。
- 根節點隻能是黑色，且黑色根節點不存儲資料。
- 任何相鄰的節點都不能同時為紅色。
- 紅色的節點，它的子節點隻能是黑色。
- 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。
紅黑樹如下圖所示：
概括為：紅黑樹所有的根節點都是黑色的的空節點，也就是根節點不存資料；任何相鄰的節點都不能同時為紅色，紅色節點是被黑色節點隔開的，每個節點，從該節點到達其可達的葉子節點是所有路徑，都包含相同數目的黑色節點。
正是因為這種特點，紅黑樹不同于平衡樹的操作，紅黑樹不會因為插入、删除等操作追求絕對的平衡，它的旋轉次數少，插入最多兩次旋轉，删除最多三次旋轉，是以對于搜尋、插入、删除操作較多的情況下，紅黑樹的效率是優于平衡二叉樹的。
但是需要注意的是，如果應用場景中對插入、删除不頻繁，隻是對查找要求較高，那麼平衡二叉樹還是較優于紅黑樹。
總結
為什麼有了數組和連結清單還要引入二叉樹？
針對數組和連結清單的優缺點，無法說連結清單一定優于數組，或者是數組一定優于連結清單，因為某些長期的需要，是以就推出一個相對折中的二叉樹。
為什麼有了二叉樹還要引入平衡二叉樹？
有了二叉樹還不算完，二叉樹有一種極端的情況，就是所有的子結點偏向一端，二叉樹退化成連結清單，這就相當于我選擇了這種的二叉樹，你現在罷工不幹了，找了個連結清單來糊弄我...
是以為了解決二叉查找樹退化為連結清單的情況，引入了平衡二叉樹，即：
平衡二叉樹是為了解決二叉樹退化成一棵連結清單而誕生的。
既然有了平衡二叉樹，這下總沒有問題了吧？
為什麼有了平衡二叉樹還要引入紅黑樹？
但是是實際使用過程中，因為平衡二叉樹追求絕對嚴格的平衡關系，顯然這個規則在于頻繁的插入、删除等操作的情景性能肯定會出現問題...
是以為了解決這個問題，進而又引入了紅黑樹。
平衡二叉樹追求絕對嚴格的平衡，平衡條件必須滿足左右子樹高度差不超過1，紅黑樹是放棄追求完全平衡，它的旋轉次數少，插入最多兩次旋轉，删除最多三次旋轉，是以對于搜尋、插入、删除操作較多的情況下，紅黑樹的效率是優于平衡二叉樹的。
紅黑樹是終結嗎？
時代總是進步的，大膽猜測不會是，就跟當初從數組、連結清單到二叉樹一樣。
至此，通過這篇希望大家對整個樹結構的出現有一個基礎的概念，目前面試中最為常問的就是紅黑樹了，當然這得益于 HashMap，但紅黑樹還有挺多其他的知識點可以考察，例如紅黑樹有哪些應用場景？紅黑樹與哈希表在不同應該場景的選擇？紅黑樹有哪些性質？紅黑樹各種操作(插入删除查詢)的時間複雜度是多少？等等等等...
希望這篇文章對你有所幫助，部落格園持續更新歡迎關注。
部落格園：https://www.cnblogs.com/niceyoo