紅黑樹(shù)是avl樹(shù)的變種，通過(guò)滿足以下的四個(gè)條件來(lái)確保對(duì)所有的路徑震放，它的長(zhǎng)度不會(huì)超過(guò)其他路徑的兩倍椅野，從而達(dá)到接近平衡的目的氮发。
它要滿足的四條規(guī)則是：
1.每個(gè)節(jié)點(diǎn)不是黑色就是紅色
2.根節(jié)點(diǎn)為黑色
3.如果節(jié)點(diǎn)為紅色凡资，其子節(jié)點(diǎn)必須為黑色
4.任意一個(gè)節(jié)點(diǎn)到樹(shù)尾端（null）的任何路徑砸捏，所經(jīng)過(guò)的黑色節(jié)點(diǎn)數(shù)目必須相同
紅黑樹(shù)的增刪操作如果一但破壞了以上四條規(guī)則，就需要進(jìn)行一系列的調(diào)整讳苦，使樹(shù)經(jīng)過(guò)調(diào)整后滿足上述四個(gè)條件带膜。
一、? 紅黑樹(shù)的插入
當(dāng)我們插入一個(gè)結(jié)點(diǎn)節(jié)點(diǎn)時(shí)根據(jù)規(guī)則4鸳谜，為了保證黑色節(jié)點(diǎn)數(shù)相同，其必須是紅色的節(jié)點(diǎn)式廷。
在其插入后咐扭，為了調(diào)整樹(shù)使其重新滿足4條規(guī)則，我們需要分好幾種情況來(lái)討論
1.插入節(jié)點(diǎn)的父節(jié)點(diǎn)為黑色節(jié)點(diǎn)
如下圖所示滑废，當(dāng)插入節(jié)點(diǎn)的父節(jié)點(diǎn)為黑節(jié)點(diǎn)時(shí)蝗肪，二叉樹(shù)的4條規(guī)則一條也沒(méi)有打破。紅黑樹(shù)比AVL樹(shù)優(yōu)秀的地方之一在于黑父的情況比較常見(jiàn)蠕趁，從而使紅黑樹(shù)需要旋轉(zhuǎn)的幾率相對(duì)AVL樹(shù)來(lái)說(shuō)會(huì)少一些薛闪。
2.插入節(jié)點(diǎn)的父節(jié)點(diǎn)為紅色
由于規(guī)則3，新增節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色的俺陋，由于規(guī)則3豁延，則其祖父節(jié)點(diǎn)必然是黑色的。這時(shí)候樹(shù)肯定是不滿足的條件的腊状，需要對(duì)樹(shù)進(jìn)行變色或者旋轉(zhuǎn)等操作對(duì)樹(shù)進(jìn)行改變诱咏，而具體要進(jìn)行何種改變，需要根據(jù)新增節(jié)點(diǎn)的叔父節(jié)點(diǎn)的顏色的不同來(lái)決定缴挖。
（1）叔父節(jié)點(diǎn)為紅色
當(dāng)叔父節(jié)點(diǎn)為紅色時(shí)袋狞，如下圖所示
將父節(jié)點(diǎn)、叔父節(jié)點(diǎn)映屋、祖父節(jié)點(diǎn)的顏色進(jìn)行改變苟鸯，如果由于祖父節(jié)點(diǎn)變紅而引起了新的不滿足規(guī)則，則將祖父節(jié)點(diǎn)當(dāng)成新的新增節(jié)點(diǎn)棚点，進(jìn)行遞歸調(diào)用來(lái)滿足平衡即可早处。
（2）叔父節(jié)點(diǎn)為黑色
當(dāng)叔父節(jié)點(diǎn)為黑色時(shí)，對(duì)樹(shù)進(jìn)行旋轉(zhuǎn)操作即可乙濒，由于新增節(jié)點(diǎn)插入的位置不同陕赃，旋轉(zhuǎn)操作可分為以下4種：
a.
b.
c.
d.
以下為用java實(shí)現(xiàn)的紅黑樹(shù)插入的代碼：
