Javaのスレッドコメントを表す最も効率的なデータ構造？

StackOverflow https://stackoverflow.com/questions/759208

質問

表現したい スレッドコメント Javaで。これは、コメントのスレッドに似ているように見えます reddit.com

hello
   hello
      hello
      hello
   hello
   hello
      hello

上記の例のように、回答は、以前のコメントとの関係を反映するために適切なインデンテーションを備えたHTMLにネストされています。

Javaでこれを表現する効率的な方法は何でしょうか？

ある種のことを考えています ツリーデータ構造 適切です。

しかし、特に1つはあります 最も効率的です ツリートラバーサルを最小限に抑えるには？

これは、各コメントに投票している場合に重要です。なぜなら、各投票の後にツリーを並べ替える必要があるからです。

ちなみに、Javaでこれを既存の実装をオープンソースに知っている場合、それも役立ちます。

役に立ちましたか？

解決

リンクされたリストのレベルを使用します。

message1
    message2
        message3
        message4
    message5
    message6
        message7

各ノードには次のポインターがあります。

- forward sibling  (2->5, 3->4, 5->6,                   1/4/6/7->NULL).
- backward sibling (4->3, 5->2, 6->5,                   1/2/3/7->NULL).
- first child      (1->2, 2->3, 6->7,                   3/4/5/7->NULL).
- parent           (2->1, 3->2, 4->2, 5->1, 6->1, 7->6,       1->NULL).

各レベル内で、メッセージは投票数（または使用したい他のスコア）によってリストに並べ替えられます。

これにより、物事を動かすための最大の柔軟性が得られ、サブツリー全体を動かすことができます（例えば、 message2）親とそのレベルのリンクを変更するだけです。

たとえば、たとえば message6 投票の流入を取得します。 message5. 。変更は（次の兄弟と以前の兄弟ポインターの両方を調整します）：

  • message2 -> message6
  • message6 -> message5
  • message5 -> NULL.

取得するため：

message1
    message2
        message3
        message4
    message6
        message7
    message5

それがより多くの票を獲得するまで継続する場合 message2, 、以下が発生します。

  • message6 -> message2
  • message2 -> message5

と の最初の子供のポインター message1 に設定されています message6 （そうだった message2）、まだ比較的簡単で、取得します。

message1
    message6
        message7
    message2
        message3
        message4
    message5

スコアの変更により、メッセージが上部兄弟よりも下の兄弟よりも少なくなる場合にのみ、順序付けが必要です。スコアが変更されるたびに再注文する必要はありません。

他のヒント

ツリーは正しい（GetLastsiblingとGetNextsiblingを使用して）が、データを保存/クエリしている場合は、おそらく各エントリの系統を保存するか、予約注文トラバーサルで番号を保存する必要があります。

http://www.sitepoint.com/article/hierarchical-data-database/2/

サブノードの正確な数を失うと、変更を最小限に抑えるためにギャップを残すことができます。それでも、これが毎回ツリーを横断するよりも著しく速くなるかどうかはわかりません。あなたの木がどれほど深く成長するかによってそれは異なると思います。

参照：

SQL-階層を保存およびナビゲートする方法は？ http://www.ibase.ru/devinfo/dbmstrees/sqltrees.html （このスキームはセルコツリーとも呼ばれます）

これは、各コメントに投票している場合に重要です。なぜなら、各投票の後にツリーを並べ替える必要があるからです。

私にとっては時期尚早の最適化のように聞こえますが、おそらく最適化に誤りがあります。

ツリーデータ構造は、データを表現するために論理的に聞こえます。私はそれに固執すると言います。パフォーマンスの問題が検出および測定され、代替と比較できる場合にのみ、後で最適化します。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top