通過將每個節點的「父」存儲在紅黑樹中來簡化哪些操作？

Question

一些紅黑樹實現爲每個節點存儲父項。

哪些常見操作（insert，remove，pop_min，pop_max，iteration ...等）可以簡化使用這些額外的信息？

Answer 1

有一位家長幫助任何可能需要加強樹的操作，這些包括迭代和刪除（包括彈出最小/最大）。

找到下一個祖先（可能是祖父母或更遠）似乎是有或沒有父指針的O（log n）操作，但它們並不相同，因爲大多數節點位於具有父級的樹意味着在典型情況下只需要一步升級（並且該步驟已經是已知的），而在沒有父級的情況下，在大多數情況下必須降級大部分樹。基本上有一個父指針反轉了祖先搜索問題。從一個實現方面（而不是算法）我也發現插入更容易與父 - 我喜歡實現重新平衡插入和刪除作爲迭代循環，而不是遞歸尾部調用。