紅黑樹的插入與删除

一、紅黑樹的删除

情況一：删除的結點D（黑色）不存在左右孩子

被删除的結點分為其父結點的左孩子和右孩子，然後再分為下面這5種情況：

1.1.兄弟結點為紅色(一定存在兩個黑侄子)：

1.2兄弟結點為黑色，近侄子為紅色：

1.3兄弟結點為黑色，遠侄子為紅色：

1.4兄弟結點為黑色，兩個紅色侄子：

1.5兄弟結點為黑色，沒有侄子：

情況二：删除的結點D（紅色）不存在左右孩子：直接删除（最簡單的情況）

情況三：删除的結點D隻有一個左孩子（結點一定是黑色，孩子一定是紅色）：左孩子替換掉D,删除左孩子。

情況四：删除的結點D隻有一個右孩子（結點一定是黑色，孩子一定是紅色）：右孩子替換掉D，删除右孩子。

情況五：删除的結點D有左右孩子（紅黑都可以，一樣分析）：找到左子樹的最大值，用該值替換要被删除的值，然後删除這個找到的最大值，這個最大值要麼有一個左孩子，要麼沒有子結點，是以可以轉換成上面的四種情況。

寫代碼的時候這樣分：左右孩子都存在（情況五），隻有一個孩子（情況三和情況四），左右孩子都不存在（2*10+1種情況，見上面的情況一和情況二）

插入比删除的情況少很多。

插入位置的父結點如果為紅色，就需要進行修複。

先分顔色，然後在判斷父親，叔叔，自己的位置。

叔叔為紅。叔叔為黑（或者不存在)。

父左，自己左。父左，自己右。父右，自己左。父右，自己右。

其實插入和删除最主要的是在插入和删除之後對紅黑樹的修複，因為在插入和删除操作之後，有可能會破壞紅黑樹的特性，找到需要修複的那幾種情況，其他的正常删除和插入就好了。