深入理解hashmap（三）雜湊表和二叉搜尋樹的恩怨情仇
前面兩篇文章介紹了hashmap的原始碼和理論，今天把剩餘的部分紅黑樹講一下。理解好紅黑樹，對我們後續對hashmap或者其他資料結構的理解都是很有好處的。比方說為什麼後面jdk要把hashmap中的單鏈表更新成紅黑樹？
要理解紅黑樹首先要弄清楚普通二叉樹的一些基本概念
父節點和子節點，這個我就不多說了。應該都知道。
如果某幾個子節點的父節點都是一個節點，那他們就是兄弟節點。
如果某個節點沒有父節點，那他就是根節點。
如果某個節點沒有子節點，拿他就是葉子節點
看下面這個二叉樹：
A 節點的高度 ：就是節點A到最遠端的葉子節點的邊數。 比方說這裡A節點的高度就是3
E 節點的深度 ：就是根節點A到節點E的邊數，這裡明顯就是2了，所以E節點的深度就是2
E 節點的層數 ：就是E節點的深度+1. 所以這裡E節點的層數就是3.
再看這張圖：
圖1 就叫做 滿二叉樹 ：
條件1：葉子節點全部在最下面
條件2：除了葉子節點以外，每個節點都有左右2個子節點。
滿二叉樹很好理解對吧，不多說了。我們繼續看圖2，
圖2 就叫做 完全二叉樹 ：
條件1：葉子節點只能在最下面 2層 。
條件2：最後一層的葉子節點都靠左排列。
條件3：除了最後一層，其他層的子節點個數必須達到最大。（ 也可以理解成：把最後一層去掉以後，必須是一個滿二叉樹 ）
恩，好像完全二叉樹的判定就有點複雜了，沒關係，我們看幾個圖練習一下
再看幾張圖：
圖1：不是完全二叉樹吧，條件1就不符合。因為第二層就有一個葉子節點了
圖2：不符合條件2，圖2 裡最後一層葉子節點都向右邊了
圖3：不符合條件3 ，因為我們把最後一層去掉以後發現並不是一個滿二叉樹。
為什麼要有一個完全二叉樹，這東西幹啥的？為什麼條件2要求最後一層葉子節點都靠左排列？向右不可以嗎？
首先要明確一個概念， 二叉樹除了用連結串列實現以外，還可以用陣列來實現。
連結串列實現的二叉樹不多說了，網上太多了，其實資料結構就是一個data欄位，然後配一個left指標和right指標。
那如果用陣列來做，怎麼儲存一個二叉樹呢？看下面這張圖：
很好理解吧，數字就代表陣列的下標。比如說 跟節點A 就放在[1]位置，節點F 就放在[6]位置，節點I就放在[9]位置，等等
所以數學歸納法以後，我們可以抽象出如下的規則：
如果一個二叉樹用陣列來儲存，那麼節點對應的下表規則如下：
規則1：下標為2*i的 必然是左子節點。
規則2：下標為2*i+1 的，必然是右子節點。
規則3：下標為i/2的節點必然是 節點i的 父親節點。
所以我們只要把一個二叉樹的根節點放到陣列的任意一個位置中，就必然可以把整個二叉樹利用上述的規則串聯起來，整個就是二叉樹的陣列儲存法。
而用陣列儲存二叉樹的好處就是可以節省left和right 這2個指標，可以節約記憶體空間
再看一張圖：
你看這個二叉樹，我們的出來的陣列下標是 1，2，3，4，7，8，9，13.
浪費了 5，6，10，11，12. 浪費了這5個數組空間空閒在那裡。
所以完全二叉樹的優點就是不會浪費任何陣列空間，所以對於完全二叉樹來說，陣列儲存是最合適的方法，比方說堆就是用陣列來 做二叉樹的儲存結構的
前序遍歷：先列印節點本身，再列印左子樹，再列印右子樹
中序遍歷：左子樹-節點本身-右子樹
後序遍歷：左子樹-右子樹-節點本身
那這三種遍歷的方法我就不多說了，網上一搜一大堆。
有了這些前置的概念 我們就可以繼續深挖。
二叉搜尋樹是咩啊？
二叉搜尋樹：對於任意一個節點來說，他的左節點的值都要小於這個節點，右節點的值都要大於這個節點。
那麼，我們來對一個二叉搜尋樹進行他的 查詢，插入操作。 為什麼要學這個，因為對於大部分資料結構來說，衡量他的
效能主要就是 看查詢資料和插入資料的效率。比方說陣列和連結串列 就是查詢和插入效率截然相反的兩種資料結構。
廢話不多說，我們首先來看一下二叉搜尋樹的 查詢操作要怎麼完成：
其實也很簡單，對於二叉搜尋樹來說， 左節點的值《父節點《右節點。
所以想查詢一個值，我們只要從二叉搜尋樹的頂部也就是根節點來遍歷即可：
如果這個值比節點大，那麼就去右子樹繼續遞迴查詢，如果這個值比節點的值小，那麼就去左子樹查。直到找到為止
這個遞迴函式我就不寫了，大家知道這個演算法思路就可以，自己多練習一下。
二叉搜尋樹的插入操作就稍微複雜一點：
1.如果要插入的值，比節點的值要大，並且這個節點的右子樹為空，那麼就直接放在這個節點的右節點位置上（注意哦，這個就是遞迴的結束條件）
2.如果不為空，那麼就繼續 步驟1的操作，直到我們找到對應的節點位置為止。
- 如果插入的值 比節點的值要小，並且這個節點的左子樹為空，那麼就直接放在節點的左節點位置上。。 以此類推。和步驟1-2 其實是一個思路
可以看出來，遞迴是實現二叉樹相關演算法的核心思想。
此外最重要的一點，我們再回顧一下這個二叉搜尋樹的特性你會發現：如果我們用中序遍歷的方法 print這個 二叉搜尋樹，那麼 得到的結果一定是一個有序的。時間複雜度為o(n)
所以，二叉搜尋樹又叫二叉排序樹。
如果二叉搜尋樹中有重複的資料要插入怎麼辦？
這個問題問的好，這裡給出2個解決方案，大家有興趣可以實現一下
方案1：
正常情況下，我們一個二叉樹如果用連結串列來實現，那麼基礎資料結構肯定是 data欄位和left以及right指標對吧，那麼
我們可以人為的增加一個欄位，叫 more指標。這個指標是幹嘛的呢？這個指標就是把重複的資料串起來。
比方說下圖的例子：
大家可以看一下，這個二叉搜尋樹的 11的那個節點 有一個連結串列，儲存的都是值為11的節點。
這個處理方式是不是有點像hashmap中處理雜湊衝突的方法？
那有人又要問了，重複的值插到二叉搜尋樹的意義何在？
在實際生產中，我們儲存的資料結構不可能是一個個簡單的int值，而是一個個物件，那麼一個個物件裡面肯定有很多欄位， 比如 商品這個物件，可以有很多欄位，價格，商品名稱，商品圖片等。 如果用商品價格來作為二叉搜尋樹的key值， 那麼就肯定會出現這種情況,因為相同價格的商品可以是不同的商品，比如iphone和mate20 都賣7000元，但顯然他們是不 一樣的東西
方案2：
在插入資料的時候，如果發現插入的值和節點的值相同，那麼就把這個值插入到這個節點的右節點的位置。（也就是說 插入一個大於節點的值和插入一個等於節點的值 方法是一樣的）
那麼針對這種情況，我們的查詢方法就要修改一下了，不能說是找到和節點相同的值就退出遞迴了，而是找到相同節點的值以後 還要繼續找他的右子樹，看看有沒有值和查詢的值相同，一直到葉子節點為止（注意退出遞迴的條件）
二叉搜尋樹的效率如何？看起來不如雜湊表啊，存在的意義何在？
實際上，我們看一下二叉搜尋樹的演算法可以得出來一個結果，他的查詢效率是O(logn)的，完全不如雜湊表查詢的效率o(1). 且，二叉搜尋樹極端情況下很容易退化成單鏈表，那麼單鏈表的查詢效率我們都知道是O(N)的。這個就更慢了。
但，即便如此，二叉搜尋樹還有一些雜湊表不具備的優點：
-
二叉搜尋樹用中序遍歷可以很容易對 資料進行排序，這個是雜湊表做不到的。
-
雜湊表遇到雜湊衝突的時候需要擴容，這個擴容操作相當耗時，效能有時候不穩定，雖然說二叉搜尋樹的效能也不穩定， 但是 我們有更特殊的 平衡二叉搜尋樹可以把時間複雜度穩定在O(logn)
-
二叉搜尋樹比較簡單，資料結構一目瞭然，遞迴遞迴遞迴就行了，但是雜湊表你們懂的，實現起來超級複雜。
所以可以知道，hashmap和二叉搜尋樹各有各的優點，具體怎麼用，還是要看實際情況，但是大家要知道這兩種資料結構的 優劣在哪裡以及為什麼？
千呼萬喚始出來的 紅黑樹到底是什麼？和我們上面提到的平衡二叉搜尋樹又是什麼關係呢？
前面我們說到了，普通的二叉搜尋樹極端情況下會退化成單鏈表，比如說：
你看這個二叉搜尋樹運氣就非常差，全在左邊，一點都不平衡，看起來跟個單鏈表一樣，一看就是很慢的資料結構。
所以 所謂的平衡二叉搜尋樹就是要想辦法保證在插入的過程中，讓這個二叉搜尋樹變的平衡起來，所謂的平衡起來 就是不能全在左邊或者全在右邊，最好是左右兩邊都有，且左右兩邊子樹的高度越接近就越好就越平衡。因為只有這樣 我們的時間複雜度才會穩定在 O(logn)
平衡二叉搜尋樹的實現方法有很多，其中最出名的就是紅黑樹了，對於我們普通寫業務程式碼不是專業寫演算法的人來說 紅黑樹幾乎就可以代表平衡二叉搜尋樹，兩者無限接近。
但是我們要注意的是，紅黑樹是近似平衡的 平衡二叉搜尋樹，並不是嚴格的平衡二叉樹，有興趣的同學可以查一查AVL樹 這個才是嚴格平衡二叉樹，不過這個東西因為太嚴格導致每次插入刪除的效率太低，所以生產環境用的人很少。
關於紅黑樹的具體實現，我這裡就不多說了，因為紅黑樹的實現比較複雜，我估計除非是寫演算法的人，否則絕大多數人 一輩子都不會寫一次紅黑樹，如果實在要用，實際上跳錶寫起來比紅黑樹簡單多了。。也好理解。
所以這裡有興趣的同學可以自行搜尋紅黑樹的相關資料，開開眼界。沒有興趣的同學就只要知道紅黑樹是一種平衡二叉查詢樹，它是為了解決普通二叉查詢樹在資料插入的時候容易退化成單鏈表導致效率大幅降低的資料結構。他的高度會無限接近於log2n，所以 他的查詢效率也就可以穩定在O(logn)了。這也就是為什麼hashmap在高版本jdk中的實現 用紅黑樹代替單鏈表來解決雜湊碰撞的原因。