如何實施Patricia Trie的刪除/刪除功能？

Question

我已經部分實現了Patricia Trie，但它仍然不完整，因爲它缺少用於從Trie中刪除節點的函數刪除/刪除函數，我發現描述了結構，它隨C++實現一起提供，有一個刪除/刪除功能，但我無法弄清楚實施背後的想法。

如何從Trie中刪除一個節點並使Trie處於正確的狀態？

Answer 1

我最近在C中實現了PATRICIA。爲了刪除一個節點，找到向下指向受害者的下行節點（這可能是受害者節點本身）。

一旦找到，如果受害者節點不是後向引用者，將受害者與其引薦者切換。這使得受害者接近成爲「葉」節點，其向後引用將自己。那麼去除非常簡單。