如何实施Patricia Trie的删除/删除功能？

Question

我已经部分实现了Patricia Trie，但它仍然不完整，因为它缺少用于从Trie中删除节点的函数删除/删除函数，我发现描述了结构，它随C++实现一起提供，有一个删除/删除功能，但我无法弄清楚实施背后的想法。

如何从Trie中删除一个节点并使Trie处于正确的状态？

Answer 1

我最近在C中实现了PATRICIA。为了删除一个节点，找到向下指向受害者的下行节点（这可能是受害者节点本身）。

一旦找到，如果受害者节点不是后向引用者，将受害者与其引荐者切换。这使得受害者接近成为“叶”节点，其向后引用将自己。那么去除非常简单。