紅黑樹（Red Black Tree） 是一種自平衡二叉查找樹，是在計算機科學中用到的一種數據結構，

紅黑樹五大特性

1、所有節(jié)點非紅即黑

2、根節(jié)點是黑色

3、頁節(jié)點是黑色

4、不能有連續(xù)的紅色

5、任意節(jié)點到葉子節(jié)點路徑中有相同數量的黑色節(jié)點

變色

如果當前節(jié)點的父親節(jié)點和叔叔節(jié)點均是紅色，那么執(zhí)行以下變色操作：

父 --> 黑

叔 --> 黑

爺 --> 紅

開始分析爺爺是否滿足紅黑樹特性

左旋

條件：

父親是紅色

叔叔是黑色

當前是右子樹

執(zhí)行：

已父親進行旋轉

右旋

條件：

父親是紅色

叔叔是黑色

當前是左子樹

執(zhí)行：

父親節(jié)點 變?yōu)?黑色

爺爺節(jié)點變?yōu)榧t色

再已爺爺節(jié)點進行旋轉

流程

下面已一個具體的實例進行分析紅黑樹的執(zhí)行過程：

新插入一個節(jié)點6（所有新插入節(jié)點均為紅色），不滿足條件4（不能有連續(xù)的紅色），且當前節(jié)點父親和叔叔均為紅色 --> 則進行變色

此時5、12不滿足”不能有連續(xù)的紅色“，又因為12的父親是紅色，叔叔是黑色，且當前是右子樹 --> 已父親 5 左旋

此事5、12不滿足”不能有連續(xù)的紅色“，5的父親是紅色，叔叔是黑色，且在左子樹 —> 先父親變黑色、爺爺變紅色 —> 已爺爺節(jié)點 19 右旋

至此：一個紅黑樹就完成了