「稽古】左偏紅黑樹 IV 如若能刪除最小值就好了

我們已經能夠向左偏紅黑樹中插入節點了,但在考慮刪除指定的節點之前,讓我們先考慮一下如何刪除樹中持有最小值的節點。

Intro

刪除操作基於這樣的思想:我們不能刪除黑色的節點,因為這樣會破壞黑高。所以我們需要保證我們最後刪除的節點是紅色的。
怎么才能保证最后删除的节点是红色的呢?我们需要在向下递归的过程中保证一个性质:如果当前节点是q,那么需要保证q是红色,或者q->lchild是红色。

需要保證的性質可以這樣來理解:q為紅色節點意味著連接q與其母親節點的邊為紅邊,q->lchild為紅色節點意味著連接q與其左孩子的邊為紅邊。
這樣一來在刪除的時候,斬斷與q相連的紅邊,然後讓與q相連的黑邊接管被斬斷紅邊連接的另一個節點即可。

但對於持有最小值的節點q而言,它并不具有左孩子,因此不存在q->lchild為紅色的情況,此時必須保證q為紅色,亦即連接其與母親節點的邊為紅色。

我們把想要刪除的節點染紅,刪除,再按照插入節點時的方法進行修復即可。

Minimum Deletion

爲了達到這一點,我們所采取的辦法便是, 臨時地 破壞左偏紅黑樹的某些性質,在遞歸返回時再進行恢復。

References

OI-Wiki