紅黑樹是一棵自平衡二叉搜索樹，所以查找和二叉搜索樹的時間復(fù)雜度相同。插入和刪除操作稍微復(fù)雜一點，顏色變更很迅速，需要少量O(logN)的時間，旋轉(zhuǎn)不會超過三次，插入操作只需要兩次旋轉(zhuǎn)。因此，紅黑樹結(jié)點的插入和刪除只需要O(logN)的時間復(fù)雜度，即可恢復(fù)紅黑樹的性質(zhì)。

01插入

如何將結(jié)點插入紅黑樹？三步驟：

1、將紅黑樹當(dāng)成一棵二叉搜索樹，插入；

2、將新插入的結(jié)點著成紅色；

3、通過旋轉(zhuǎn)和重新著色，使其滿足紅黑樹的性質(zhì)。

這棵樹本身是一棵自平衡二叉搜索樹，插入結(jié)點后不改變二叉搜索樹的事實，不論是左旋、右旋還是著色，也不改變這個事實；

將新結(jié)點著成紅色，不會違背“從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑上包含相同數(shù)目的黑節(jié)點”的性質(zhì)，只會違背“如果一個節(jié)點是紅色的，則它的子節(jié)點必須是黑色的”這一條性質(zhì)，使違背的性質(zhì)最少化，減少了我們處理的工作量；

最后，通過一系列的旋轉(zhuǎn)和重新著色，使新樹滿足紅黑樹的所有性質(zhì)，重新成為一棵紅黑樹。

根據(jù)父結(jié)點的顏色，分為三種情況：

1）插入結(jié)點為根結(jié)點，將結(jié)點著成黑色，完成；

2）插入結(jié)點的父結(jié)點為黑色，無須處理；

3）插入結(jié)點的父結(jié)點為紅色，則插入結(jié)點一定存在祖父結(jié)點和叔叔結(jié)點（即使叔叔結(jié)點為空，也是一個黑色結(jié)點），我們根據(jù)叔叔結(jié)點的顏色，再分成三種情況。

1、當(dāng)前結(jié)點的父結(jié)點為紅色，叔叔結(jié)點也為紅色

1) 將“父節(jié)點”設(shè)為黑色。

2) 將“叔叔節(jié)點”設(shè)為黑色。

3) 將“祖父節(jié)點”設(shè)為“紅色”。

4) 將“祖父節(jié)點”設(shè)為“當(dāng)前節(jié)點”(紅色節(jié)點)；即，之后繼續(xù)對“當(dāng)前節(jié)點”進(jìn)行操作。

2、當(dāng)前結(jié)點的父結(jié)點為紅色，叔叔結(jié)點為黑色，且當(dāng)前結(jié)點為其父結(jié)點的右孩子

1) 將“父節(jié)點”作為“新的當(dāng)前節(jié)點”。

2) 以“新的當(dāng)前節(jié)點”為支點進(jìn)行左旋。

3、當(dāng)前結(jié)點的父結(jié)點為紅色，叔叔結(jié)點為黑色，且當(dāng)前結(jié)點為其父結(jié)點的左孩子

1) 將“父節(jié)點”設(shè)為“黑色”。

2) 將“祖父節(jié)點”設(shè)為“紅色”。

3) 以“祖父節(jié)點”為支點進(jìn)行右旋。