昨天我們把HashMap的基本理論和1.7底層做了着重的分析講解，今天我們接着上篇文章最後提到過的紅黑樹繼續往下講。
文章目錄
- 紅黑樹
- 二叉查找樹簡介
- 左旋和右旋(平衡二叉查找樹)
- 紅黑樹簡介
紅黑樹
二叉查找樹簡介
說到紅黑樹我們就要先講解一下二叉查找樹，友善不了解二叉樹的同學了解一下，知道的同學也可以複習一下這部分的知識點。
二叉查找樹:二分查找算法映射出來的結構
引入圖檔如下: 
這裡說一下二叉查找樹的特點:
（1）若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
（2）若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
（3）左、右子樹也分别為二叉查找樹；
左旋和右旋(平衡二叉查找樹)
在每一次樹插入新元素後，樹的平衡都可能被破壞，需要旋轉調整樹的高度，以達到平衡樹結構，共分為以下四種情況：
1.LL：對該結點的左兒子的左子樹進行了一次插入，需右旋轉
2.LR：對該結點的左兒子的右子樹進行了一次插入，先左後右
3.RL：對該結點的右兒子的左子樹進行了一次插入，先右後左
4.RR：對該結點的右兒子的右子樹進行了一次插入，需左旋轉
引入圖檔如下: 
紅黑樹簡介
剛剛看完二叉查找樹的同學們應該對這種二叉樹有了一定的了解，接着我們繼續往下講解紅黑樹。
引入圖如下: 紅黑樹的性質:
1.節點是紅色或黑色。
2.根節點是黑色。
3.每個葉子節點都是黑色的空節點（NIL節點）。
4 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點，如果出現了連續兩個紅色節點就進行相應的旋轉變色)
5.從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。（這一點是平衡的關鍵）
這些限制強制了紅黑樹的關鍵性質: 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。
結果是這個樹大緻上是平衡的。因為操作比如插入、删除和查找某個值的最壞情況時間都要求與
樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的
二叉查找樹。 講到這裡相信同學們也對二叉查找樹，紅黑樹都有了一定的了解，下一章節我會帶大家深刻了解HashMap1.8底層是如何進行樹化，如果有同學想了解hashMap數組+連結清單結構和1.7的相關知識，可以看我上一篇的部落格，謝謝大家的觀看，希望能給各位同學帶來幫助。如果覺得部落客寫的還可以的，可以點贊關注。????