patricia-trie - 如何为 Patricia Trie 实现删除/删除功能？

Question

我已经部分实现了 Patricia Trie，它仍然不完整，因为它缺少用于从 Trie 中删除节点的删除/删除功能，我发现这篇描述结构的文章，它带有 C++ 中的实现，有一个删除/delete 函数，但我无法弄清楚实现背后的想法是什么。

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

Answer 1

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

一旦找到，如果受害者节点不是反向引用者，则将受害者与其引用者切换。这使受害者接近于一个“叶”节点，它的后向引用将指向它自己。那么删除就很简单了。