java - 四分木除去

Question

四分木の除去方法を書いています。

これで、ノード内のアイテムを削除するときに、その兄弟をチェックして、ノードを折りたたんで1つにマージする必要があるかどうかを確認する必要があります。

兄弟をチェックするために、親ノードへのポインターを格納する必要がありますか、それともこれを再帰的かつより適切に行う方法がありますか？

ありがとう

Answer 1

四分木で削除するには、基本的に次のことを行う必要があります。

1. オブジェクトの葉を見つけて、そのリスト (葉を含むノード) から削除します。
2. リーフを削除してもノードが空のままかどうかを確認し、空の場合はノード自体を削除します。
3. 周囲のノードも空であるかどうかを確認し、空である場合は、このノードを「非分割」によって親に折りたたみます (これは再帰的に行うのが難しい場合があります)。秘訣は、隣接するノードに何かがあるかどうかを確認することです。そうでない場合は、象限全体を捨てて、1 レベル上げても安全です。これを再帰的に行うと、葉のある隣接ノードが存在する場所までツリーが折りたたまれます。

ステップ 1 の後、基本的には完了です。メモリを節約し、ツリーの効率を維持したい場合は、手順 2 と 3 を実行する必要があります。

はい、逆トラバーサルを効率的にするために、親ノードの参照を保持する必要があります。