1

Patricia Trieを部分的に実装しましたが、Trieからノードを削除するために使用される削除/削除機能がないため、まだ完了していません。C++での実装に付属する構造について説明しているこの記事を見つけました。削除があります。 / delete関数ですが、実装の背後にある考え方がわかりません。

Trieからノードを削除し、Trieを適切な状態のままにするにはどうすればよいですか？

4

1 に答える 1

0

最近、C で PATRICIA を実装しました。ノードを削除するには、トライを逆方向にビクティムに向けるダウン トライ ノードを見つけます (これはビクティム ノード自体である可能性があります)。

見つかったら、被害者ノードが後方リファラーでない場合は、被害者をそのリファラーに切り替えます。これにより、被害者は「リーフ」ノードに近づき、その後方参照はそれ自体になります。削除は非常に簡単です。

于 2012-08-15T18:57:24.937 に答える