紅黑樹：基于紅黑規(guī)則實現(xiàn)自平衡排序二叉樹

紅黑樹是一種自平衡的二叉查找樹，是計算機科學中用到的一種數(shù)據(jù)結(jié)構(gòu)。1972年出現(xiàn)，當時被稱之為平衡二叉B樹。1978年被修改為如今的"紅黑樹"。每一個節(jié)點可以是紅或者黑;紅黑樹不是通過高度平衡的，它的平衡是通過“紅黑規(guī)則”進行實現(xiàn)的。

紅黑規(guī)則：

每一個節(jié)點或是紅色的，或者是黑色的，根節(jié)點必須是黑色。

如果某一個節(jié)點是紅色，那么它的子節(jié)點必須是黑色(不能出現(xiàn)兩個紅色節(jié)點相連的情況)。

對每一個節(jié)點，從該節(jié)點到其所有后代葉節(jié)點的簡單路徑上，均包含相同數(shù)目的黑色節(jié)點。

添加的節(jié)點的顏色，可以是紅色的，也可以是黑色的。紅黑樹默認用紅色效率高。如下假設添加20、18、23三個元素，一共需要調(diào)整兩次。

根節(jié)點是黑色，添加20、18、23三個元素，一共需要調(diào)整一次。所以，添加節(jié)點時，默認為紅色，效率高。

當添加的節(jié)點為根節(jié)點時，根節(jié)點直接變成黑色就可以了

當父節(jié)點為黑色，則不需要做任何操作。其父節(jié)點為紅色，叔叔節(jié)點也是紅色。將“父節(jié)點23”設為黑色，將“叔叔節(jié)點18”設為黑色。將“祖父節(jié)點20”設為“紅色”。如果祖父節(jié)點為根節(jié)點，則將根節(jié)點再次變成黑色。

其父節(jié)點為紅色，叔叔節(jié)點也是紅色。

其父節(jié)點為黑色，則不需要做任何操作。

其父節(jié)點為紅色，叔叔節(jié)點也是紅色。將“父節(jié)點16”設為黑色，將“叔叔節(jié)點19”設為黑色，將“祖父節(jié)點18”設為“紅色”。如果祖父節(jié)點為根節(jié)點，則將根節(jié)點再次變成黑色。

將“父節(jié)點16”設為黑色，將“叔叔節(jié)點19”設為黑色，將“祖父節(jié)點18”設為“紅色”。如果祖父節(jié)點為根節(jié)點，則將根節(jié)點再次變成黑色。

將“父節(jié)點15”設為“黑色”，“祖父節(jié)點16”設為“紅色”，以祖父節(jié)點為支點進行旋轉(zhuǎn)，其父節(jié)點為紅色，叔叔節(jié)點也是黑色。

紅黑樹增刪改查的性能都很好，但紅黑樹不是高度平衡的，它的平衡是通過"紅黑規(guī)則"進行實現(xiàn)的。

規(guī)則如下：

每一個節(jié)點或是紅色的，或者是黑色的，根節(jié)點必須是黑色

如果一個節(jié)點沒有子節(jié)點或者父節(jié)點，則該節(jié)點相應的指針屬性值為Nil，這些Nil視為葉節(jié)點，每個葉節(jié)點(Nil)是黑色的;

如果某一個節(jié)點是紅色，那么它的子節(jié)點必須是黑色(不能出現(xiàn)兩個紅色節(jié)點相連的情況)

對每一個節(jié)點，從該節(jié)點到其所有后代葉節(jié)點的簡單路徑上，均包含相同數(shù)目的黑色節(jié)點。