4

Java でスレッド化されたコメントを表現したい。これは、 reddit.comでコメントがスレッド化される方法に似ています。

hello
   hello
      hello
      hello
   hello
   hello
      hello

上記の例のように、応答は、前のコメントとの関係を反映する適切なインデントを使用して HTML にネストされます。

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

ある種のツリーデータ構造が適切だと思います。

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

各コメントに投票する場合、これは重要です。その場合、投票ごとにツリーを並べ替える必要があるため、計算的に高価な操作になる可能性があります。

ちなみに、これを Java で実装したオープンソースの既存の実装を誰かが知っていれば、それも役に立ちます。

4

3 に答える 3

10

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

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

ANDの最初の子ポインターは(以前は) にmessage1設定されていますが、それでも比較的簡単に取得できます。message6message2

message1
    message6
        message7
    message2
        message3
        message4
    message5

並べ替えは、スコアの変更によってメッセージが上位の兄弟よりも大きくなった場合、または下位の兄弟よりも小さくなった場合にのみ発生する必要があります。スコアが変わるたびに再注文する必要はありません。

于 2009-04-17T06:14:53.040 に答える
4

ツリーは (getLastSibling と getNextSibling を使用して) 正しいですが、データを保存/クエリしている場合は、各エントリの系統を保存するか、事前順トラバーサルによる番号を保存することをお勧めします。

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

サブノードの正確な数が失われる場合は、ギャップを残して再番号付けを最小限に抑えることができます。それでも、これが毎回ツリーをたどるよりも著しく速いかどうかはわかりません。木がどれだけ深くなるかにもよると思います。

以下も参照してください。

SQL - 階層を保存してナビゲートする方法は? http://www.ibase.ru/devinfo/DBMSTrees/sqltrees.html (このスキームは Celko ツリーとも呼ばれます)

于 2009-04-17T06:11:47.353 に答える
0

各コメントに投票する場合、これは重要です。その場合、投票ごとにツリーを並べ替える必要があるため、計算的に高価な操作になる可能性があります。

私には時期尚早の最適化のように聞こえますが、おそらく不完全な最適化でさえあります。

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

于 2009-04-17T06:09:55.937 に答える