次の仕様でツリー/グラフトラバーサルの問題にアプローチするためのガイダンスを探しています:
- ルートノードは 1 つです。
- ルート ノードは潜在的に無限の子ノードを持つことができます。
- 各子ノードは親を 1 つだけ持つことができますが、それ自体が潜在的に無限の子ノードの親になることもできます。
- これは、現実のシナリオでは、ほとんどの場合、小さな構造になります。ただし、トラバーサルと削除に関しては、大規模な構造でも機能するはずです。
- ノードを削除すると、ノードの子、孫など、および親で削除されたノードへの参照を削除する必要があるため、私は削除に最も関心があります。
効率を念頭に置いて、この問題にどのようにアプローチしますか。Javascript/JQuery で何かを実装しようとしています。これが十分な情報であることを願っています。アドバイスをいただければ幸いです。
ありがとうございました。
*編集/更新* 上記の構造は有向グラフに最もよく似ており、各レベルで潜在的に無限の子ノードがあるため、バイナリツリーにはなりません。また、これを正しく表現しているかどうかはわかりませんが、実際の HTML コードでは、ノードの関係に従って構造がレイアウトされていません。つまり、構造のビジュアル/コード設計は、たとえば JSON 表現に存在するさまざまな親子関係と一致しません。これは他の誰かが選択したものですが、トラバーサル、挿入、および削除を実装するのは私の仕事です。
SOについてさらに調べてみたところ、次のリンクが見つかりました。
networkxを使用して有向グラフ内のすべての関連ノードを削除する方法は?
上記のリンクの最初の回答は、これまでに見つけた解決策に最も近いものです。しかし、最初の回答で言及されている「ワークリストアルゴリズム」が最初のレベルよりも深くなる方法がわかりませんか?
繰り返しますが、どんな助けでも大歓迎です。