紅黑樹的插入(紅黑樹添加)

小編：魅力更新時(shí)間：2022-09-06 00:27

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

01插入

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

紅黑樹的插入(紅黑樹添加)