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

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

紅黑規(guī)則：

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

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

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

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

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

當(dāng)添加的節(jié)點(diǎn)為根節(jié)點(diǎn)時(shí)，根節(jié)點(diǎn)直接變成黑色就可以了

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

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

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

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

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

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

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

規(guī)則如下：

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

如果一個(gè)節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)或者父節(jié)點(diǎn)，則該節(jié)點(diǎn)相應(yīng)的指針屬性值為Nil，這些Nil視為葉節(jié)點(diǎn)，每個(gè)葉節(jié)點(diǎn)(Nil)是黑色的;

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

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