數據結構-為什麼紅黑樹中所有的葉子結點為NIL結點且顏色為黑,而不是NULL?NIL結點存在的意義是什麼?

為什麼紅黑樹中所有的葉子結點為NIL結點且顏色為黑,而不是NULL?NIL結點存在的意義是什麼?

我是這麼想的.
在紅黑樹的刪除算法中,有這麼一種情況
這種情況下,S的左孩子與右孩子必為NIL,否則原來的紅黑樹就不平衡.
那麼在對P的向上遞歸過程中,也會出現這種情況,即對應的S及S的孩子全為黑色.
NIL結點的意義之一是不是就在於:向上遞歸的過程中識別出這種情況?
又或者?
期待您的回答.
圖片來自:http://dongxicheng.org/structure/red-black-tree/

最佳回答：

是的，你的理解完全正確