?紅黑樹顧名思義就是節(jié)點(diǎn)是紅色或者黑色的平衡二叉樹，它通過顏色的約束來維持著二叉樹的平衡。

對(duì)于一棵有效的紅黑樹二叉樹而言我們必須增加如下規(guī)則：

???????1、每個(gè)節(jié)點(diǎn)都只能是紅色或者黑色

???????2、根節(jié)點(diǎn)是黑色

???????3、每個(gè)葉節(jié)點(diǎn)（NIL節(jié)點(diǎn)，空節(jié)點(diǎn)）是黑色的。

???????4、如果一個(gè)結(jié)點(diǎn)是紅的，則它兩個(gè)子節(jié)點(diǎn)都是黑的。也就是說在一條路徑上不能出現(xiàn)相鄰的兩個(gè)紅色結(jié)點(diǎn)。

???????5、從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

? ?圖解? http://www.sohu.com/a/201923614_466939