Как реализовать функцию удаления / удаления для Patricia Trie?

Question

Я частично реализовал Patricia Trie, он все еще не завершен, так как в нем отсутствует функция delete / remove , которая используется для удаления узлов из Trie. Я нашел эту статью описывающая структуру, которая поставляется с реализацией на C ++, есть функция удаления / удаления, но я не могу понять, в чем идея реализации.

Как мне удалить узел из Trie и оставитьТри в правильном состоянии?

Answer 1

Я недавно внедрил PATRICIA в C. Чтобы удалить узел, найдите нисходящий узел, который указывает на обратный ход вверх по дереву к жертве (это может быть сам узел жертвы).

Если найден узел жертвы, НЕ являющийся обратным реферером, поменяйте жертву своим реферером. Это ставит жертву близко к тому, чтобы быть «листовым» узлом, и ее обратная ссылка будет на себя. Удаление очень простое.