1. 概述
在jdk1.8中，HashMap和ConcurrentHashMap中都采用了紅黑樹這一數(shù)據(jù)結(jié)構(gòu)。即當鏈表達到一定的長度后，就把鏈表轉(zhuǎn)化成紅黑樹。這其中主要利用了紅黑樹的良好性質(zhì)，不管你節(jié)點怎樣，他始終保持查找時間復雜度為O(logn)。這樣的性質(zhì)相對于鏈表在長度很長的時候有很大的優(yōu)勢。O(logn）<O(lgn)
2. 紅黑樹的定義
- 每個結(jié)點要么是紅的，要么是黑的。
- 根結(jié)點是黑的。
- 每個葉結(jié)點（葉結(jié)點即指樹尾端NIL指針或NULL結(jié)點）是黑的。
- 如果一個結(jié)點是紅的，那么它的倆個兒子都是黑的。
-
對于任一結(jié)點而言，其到葉結(jié)點樹尾端NIL指針的每一條路徑都包含相同數(shù)目的黑結(jié)點。
一棵典型的紅黑樹如下：
紅黑樹
3. 紅黑樹的插入
在這里，默認你熟悉二叉查找樹的結(jié)構(gòu)，以及他的插入和刪除操作。紅黑樹本質(zhì)上是一棵二叉查找樹。
對紅黑樹的插入，我們先按二叉查找樹去插入，然后對對樹做調(diào)整，使其滿足紅黑樹的五條定義。（這是因為你插入會破壞其中的規(guī)則）
二叉查找樹的插入偽代碼如下：
RB-INSERT(T, z)
1 y ← nil[T]
2 x ← root[T]
3 while x ≠ nil[T]
4 do y ← x
5 if key[z] < key[x]
6 then x ← left[x]
7 else x ← right[x]
8 p[z] ← y
9 if y = nil[T]
10 then root[T] ← z
11 else if key[z] < key[y]
12 then left[y] ← z
13 else right[y] ← z
14 left[z] ← nil[T]
15 right[z] ← nil[T]
16 color[z] ← RED
17 RB-INSERT-FIXUP(T, z)
可以看出，RB-INSERT(T, z)前面的第1-13行代碼基本就是二叉查找樹的插入代碼，然后第14-16行代碼把z的左孩子、右孩子都賦為葉結(jié)點nil，再把z結(jié)點著為紅色，最后為保證紅黑性質(zhì)在插入操作后依然保持，調(diào)用一個輔助程序RB-INSERT-FIXUP來對結(jié)點進行重新著色，并旋轉(zhuǎn)。
換言之
- 如果插入的是根結(jié)點，因為原樹是空樹，此情況只會違反性質(zhì)2，所以直接把此結(jié)點涂為黑色。
- 如果插入的結(jié)點的父結(jié)點是黑色，由于此不會違反性質(zhì)2和性質(zhì)4，紅黑樹沒有被破壞，所以此時也是什么也不做。
但當遇到下述3種情況時：
- 插入修復情況1：如果當前結(jié)點的父結(jié)點是紅色且祖父結(jié)點的另一個子結(jié)點（叔叔結(jié)點）是紅色
- 插入修復情況2：當前結(jié)點的父結(jié)點是紅色,叔叔結(jié)點是黑色，當前結(jié)點是其父結(jié)點的右子
- 插入修復情況3：當前結(jié)點的父結(jié)點是紅色,叔叔結(jié)點是黑色，當前結(jié)點是其父結(jié)點的左子
3.1 插入修復情況1：當前結(jié)點的父結(jié)點是紅色且祖父結(jié)點的另一個子結(jié)點（叔叔結(jié)點）是紅色。
插入的偽代碼如下：
1 while color[p[z]] = RED
2 do if p[z] = left[p[p[z]]]
3 then y ← right[p[p[z]]]
4 if color[y] = RED
5 then color[p[z]] ← BLACK ? Case 1
6 color[y] ← BLACK ? Case 1
7 color[p[p[z]]] ← RED ? Case 1
8 z ← p[p[z]] ? Case 1
如下面兩個調(diào)整前的圖和調(diào)整之后的圖做對比。其中4為新添加的點。它的父節(jié)點為紅色，叔叔節(jié)點為紅色。那么調(diào)整就是把4的叔叔節(jié)點變?yōu)楹谏?節(jié)點），4的祖父節(jié)點變?yōu)榧t色，把當前結(jié)點指向祖父結(jié)點，從新的當前結(jié)點重新開始算法（7節(jié)點變?yōu)镹)。
3.2 插入修復情況2：當前結(jié)點的父結(jié)點是紅色,叔叔結(jié)點是黑色，當前結(jié)點是其父結(jié)點的右子
9 else if z = right[p[z]]
10 then z ← p[z] ? Case 2
11 LEFT-ROTATE(T, z) ? Case 2
調(diào)整之前的圖如3.1.2，經(jīng)過調(diào)整后得到如下的圖。過程是當前結(jié)點的父結(jié)點做為新的當前結(jié)點，以新當前結(jié)點為支點左旋.
3.3 插入修復情況3：當前結(jié)點的父結(jié)點是紅色,叔叔結(jié)點是黑色，當前結(jié)點是其父結(jié)點的左子
12 color[p[z]] ← BLACK ? Case 3
13 color[p[p[z]]] ← RED ? Case 3
14 RIGHT-ROTATE(T, p[p[z]]) ? Case 3
調(diào)整過程是把父結(jié)點變?yōu)楹谏?，祖父結(jié)點變?yōu)榧t色，在祖父結(jié)點為支點右旋。最后，把根結(jié)點涂為黑色，整棵紅黑樹便重新恢復了平衡。調(diào)整之前的圖如3.2.2，經(jīng)過調(diào)整后得到下圖。
3. 紅黑樹的刪除
在這里默認你熟悉二叉查找樹的刪除操作。
下面我們用一個分析技巧：我們從被刪結(jié)點后來頂替它的那個結(jié)點開始調(diào)整，并認為它有額外的一重黑色。這里額外一重黑色是什么意思呢，我們不是把紅黑樹的結(jié)點加上除紅與黑的另一種顏色，這里只是一種假設(shè)，我們認為我們當前指向它，因此空有額外一種黑色，可以認為它的黑色是從它的父結(jié)點被刪除后繼承給它的，它現(xiàn)在可以容納兩種顏色，如果它原來是紅色，那么現(xiàn)在是紅+黑，如果原來是黑色，那么它現(xiàn)在的顏色是黑+黑。有了這重額外的黑色，原紅黑樹性質(zhì)5就能保持不變?，F(xiàn)在只要恢復其它性質(zhì)就可以了，做法還是盡量向根移動和窮舉所有可能性。"--saturnman。
如果是以下情況，恢復比較簡單：
- 當前結(jié)點是紅+黑色
解法，直接把當前結(jié)點染成黑色，結(jié)束此時紅黑樹性質(zhì)全部恢復。 - 當前結(jié)點是黑+黑且是根結(jié)點， 解法：什么都不做，結(jié)束。
下面4中特殊情況
- 刪除修復情況1：當前結(jié)點是黑+黑且兄弟結(jié)點為紅色(此時父結(jié)點和兄弟結(jié)點的子結(jié)點分為黑)
- 刪除修復情況2：當前結(jié)點是黑加黑且兄弟是黑色且兄弟結(jié)點的兩個子結(jié)點全為黑色
- 刪除修復情況3：當前結(jié)點顏色是黑+黑，兄弟結(jié)點是黑色，兄弟的左子是紅色，右子是黑色
- 刪除修復情況4：當前結(jié)點顏色是黑-黑色，它的兄弟結(jié)點是黑色，但是兄弟結(jié)點的右子是紅色，兄弟結(jié)點左子的顏色任意
4.1 刪除修復情況1：當前結(jié)點是黑+黑且兄弟結(jié)點為紅色(此時父結(jié)點和兄弟結(jié)點的子結(jié)點分為黑)。
解法：把父結(jié)點染成紅色，把兄弟結(jié)點染成黑色，之后重新進入算法（我們只討論當前結(jié)點是其父結(jié)點左孩子時的情況）。此變換后原紅黑樹性質(zhì)5不變，而把問題轉(zhuǎn)化為兄弟結(jié)點為黑色的情況(注：變化前，原本就未違反性質(zhì)5，只是為了把問題轉(zhuǎn)化為兄弟結(jié)點為黑色的情況)。
4.2 刪除修復情況2：當前結(jié)點是黑加黑且兄弟是黑色且兄弟結(jié)點的兩個子結(jié)點全為黑色。
解法：把當前結(jié)點和兄弟結(jié)點中抽取一重黑色追加到父結(jié)點上，把父結(jié)點當成新的當前結(jié)點，重新進入算法。（此變換后性質(zhì)5不變）。偽代碼如下。
//調(diào)用RB-DELETE-FIXUP(T, x) 的9-11行代碼
9 if color[left[w]] = BLACK and color[right[w]] = BLACK
10 then color[w] ← RED ? Case 2
11 x p[x] ? Case 2
4.3 刪除修復情況3：當前結(jié)點顏色是黑+黑，兄弟結(jié)點是黑色，兄弟的左子是紅色，右子是黑色。
解法：把兄弟結(jié)點染紅，兄弟左子結(jié)點染黑，之后再在兄弟結(jié)點為支點解右旋，之后重新進入算法。此是把當前的情況轉(zhuǎn)化為情況4，而性質(zhì)5得以保持。偽代碼如下
//調(diào)用RB-DELETE-FIXUP(T, x) 的第12-16行代碼
12 else if color[right[w]] = BLACK
13 then color[left[w]] ← BLACK ? Case 3
14 color[w] ← RED ? Case 3
15 RIGHT-ROTATE(T, w) ? Case 3
16 w ← right[p[x]] ? Case 3
4.4 刪除修復情況4：當前結(jié)點顏色是黑-黑色，它的兄弟結(jié)點是黑色，但是兄弟結(jié)點的右子是紅色，兄弟結(jié)點左子的顏色任意。
解法：把兄弟結(jié)點染成當前結(jié)點父結(jié)點的顏色，把當前結(jié)點父結(jié)點染成黑色，兄弟結(jié)點右子染成黑色，之后以當前結(jié)點的父結(jié)點為支點進行左旋，此時算法結(jié)束，紅黑樹所有性質(zhì)調(diào)整正確。代碼如下
//調(diào)用RB-DELETE-FIXUP(T, x) 的第17-21行代碼
17 color[w] ← color[p[x]] ? Case 4
18 color[p[x]] ← BLACK ? Case 4
19 color[right[w]] ← BLACK ? Case 4
20 LEFT-ROTATE(T, p[x]) ? Case 4
21 x ← root[T] ? Case 4
以上就是紅黑樹的結(jié)構(gòu)和性質(zhì)，對于面試和源碼的理解很有幫助。
參考文章：
教你透徹了解紅黑樹
