1

これは、階層（包含関係）コンテンツをモデル化するのに最も適したツリーデータ構造です。私はこれらについて理論的な背景があまりないので、私の言語は少し非公式です

  1. 親ノードは複数の子を持つことができます。
  2. ユニークな親
  3. ツリー構造が変更されることはめったにありません。ノードを追加/再配置するよりも再作成しても問題ありません。
  4. 双方向トラバーサル
  5. 主に興味がある、親を見つける、子を見つける、一意のIDを持つノードを見つける
  6. すべてのノードには一意のIDがあります
  7. 合計で数百のノードしかない可能性があるため、パフォーマンスは大きな影響を与えない可能性があります
  8. 永続性はあるとよいかもしれませんが、DBからデータを読み取った後にメモリで使用する予定なので、必須ではありません。

私が選んだ言語はgo（golang）なので、利用できるライブラリは限られています。上記の要件に最適な言語を考慮せずに、推奨事項を提供してください。

http://godashboard.appspot.com/には、利用可能なツリーライブラリの一部がリストされています。品質とそれらがどれほどアクティブであるかについてはわかりません。私は神について読んだ

  1. https://github.com/petar/GoLLRB
  2. http://www.stathat.com/src/treap

必要な追加情報があればお知らせください。

4

2 に答える 2

3

何百ものノードしかないので、説明したのと同じ構造にするだけです。

  • 各ノードには、親ノードへの一意の参照があります。
  • 各ノードには、子ノードのリストがあります。
  • 各ノードには ID があります
  • ID --> ノードからの (外部) マップがあります。必要ないかもしれません。

親ノードと子ノードが認識されているため、双方向のトラバーサルが可能です。親の検索と子の検索も同様です。
マップがない場合は、ツリー全体をトラバースすることで ID を検索できます。または、マップを使用してノードをすばやく見つけることができます。

各ノードにリストがあるため、ノードの追加は簡単です。子ノードのリストから自由に追加/削除し、親ノードを再割り当てできるため、再配置も簡単です。

私は言語にとらわれない側面からこの質問に答えています。これは制限のないツリー構造であるため、実装はあまり一般的ではありません。

于 2012-06-27T12:11:08.253 に答える
0

B-Tree はあなたの要件を満たす方法だと思います。http://en.wikipedia.org/wiki/B-tree

ポイント 1、2、3: B ツリーは本質的にこれをサポートします。(複数の子、一意の親、要素の挿入/削除が可能

ポイント 4,5: 各ノードには、デフォルトの実装によってその子へのポインターがあります。さらに、各ノードの親のポインターを維持できます。これらのポインターを使用して、BFS/DFS で検索/トラバー操作を実装できます。

Pomit 6: レコードの重複を許可しない場合は、挿入メソッドの実装に依存します

ポン 7,8: 何百ものレコードしかないとおっしゃっていたので問題ありません。B-Tree は、外部ディスク ストレージにとっても非常に優れたデータ構造ですが。

于 2012-06-27T12:11:34.900 に答える