在理解紅黑樹之前，先看一些二叉查找樹
二叉查找樹特性
- 左字?jǐn)?shù)上所有的節(jié)點(diǎn)的值都小于或等于他的根節(jié)點(diǎn)上的值
- 右子樹上所有節(jié)點(diǎn)的值均大于或等于他的根節(jié)點(diǎn)的值
- 左、右子樹也分別為平衡二叉樹
舉個(gè)二叉樹的例子：
可以看到如果要查詢10的話，10>9
因此到他的右子樹，右子樹根節(jié)點(diǎn)為13，10<13
因此到其左子樹，左子樹根節(jié)點(diǎn)為11>10
到其左子樹，為10，找到相應(yīng)的節(jié)點(diǎn)
不過二叉查找樹有一些問題，可能會出現(xiàn)不平橫的情況，即如下圖所示的情況
從這種情況可以看出，明顯存在左子樹和右子樹深度相差過多，在使用平衡情況下的二叉查找樹是時(shí)間復(fù)雜度為logn，而出現(xiàn)這種極端情況的話，想要查9的位置就需要每一次都遍歷下一個(gè)右子樹，很有可能時(shí)間復(fù)雜度變?yōu)閚(與數(shù)組普通查詢的時(shí)間復(fù)雜度相同)
紅黑樹
特性
- 節(jié)點(diǎn)是紅色或黑色
- 根節(jié)點(diǎn)一定是黑色
- 每個(gè)葉節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)(NIL節(jié)點(diǎn))
- 每個(gè)紅節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色的(從每個(gè)葉子到跟的所有路徑上不能有兩個(gè)連續(xù)的紅節(jié)點(diǎn))(即對于層來說除了NIL節(jié)點(diǎn)，紅黑節(jié)點(diǎn)是交替的，第一層是黑節(jié)點(diǎn)那么其下一層肯定都是紅節(jié)點(diǎn)，反之一樣)
- 從任一節(jié)點(diǎn)到其每個(gè)葉子節(jié)點(diǎn)的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)
正是由于這些原因使得紅黑樹是一個(gè)平衡二叉樹
紅黑樹的例子
向紅黑樹中插入節(jié)點(diǎn)14(一般默認(rèn)插入節(jié)點(diǎn)是紅色的)
在原樹上插入20
可以看到，插入以后樹已經(jīng)不是一個(gè)平衡的二叉樹，而且并不滿足紅黑樹的要求，因?yàn)?0和21均為紅色，這種情況下就需要對紅黑樹進(jìn)行變色，21需要變?yōu)楹谏?2就會變成紅色，如果22變成紅色，則需要17和25都變成黑色
而17變成黑色顯然是不成立的，因?yàn)槿绻?7變?yōu)楹谏?，那?3就會變?yōu)榧t色，不滿足二叉樹的規(guī)則，因此此處需要進(jìn)行另一個(gè)操作---------左旋操作
- 左旋：
下圖就是一個(gè)左旋的例子，一般情況下，如果左子樹深度過深，那么便需要進(jìn)行左旋操作以保證左右子樹深度差變小
對于上圖由于右子樹中17變?yōu)楹谏院笮枰?3變成紅色，因此進(jìn)行一次左旋，將17放在根節(jié)點(diǎn)，這樣既可保證13為紅色，左旋后結(jié)果
而后根據(jù)紅黑樹的要求進(jìn)行顏色的修改
進(jìn)行左旋后，發(fā)現(xiàn)從根節(jié)點(diǎn)17，到1左子樹的葉子節(jié)點(diǎn)經(jīng)過了兩個(gè)黑節(jié)點(diǎn)，而到6的左葉子節(jié)點(diǎn)或者右葉子節(jié)點(diǎn)要經(jīng)歷3個(gè)黑節(jié)點(diǎn)，很顯然也不滿足紅黑樹，因此還需要進(jìn)行下一步操作，需要進(jìn)行右旋操作
- 右旋：與左旋正好相反
由于是從13節(jié)點(diǎn)出現(xiàn)的不平衡，因此對13節(jié)點(diǎn)進(jìn)行右旋，得到結(jié)果
而后再對其節(jié)點(diǎn)進(jìn)行變色，得到結(jié)果
這便是紅黑樹的一個(gè)變換，它主要用途有很多，例如java中的TreeMap以及JDK1.8以后的HashMap在當(dāng)個(gè)節(jié)點(diǎn)中鏈表長度大于8時(shí)都會用到
