Javaでスレッド化されたコメントを表現する最も効率的なデータ構造ですか？

Question

スレッドのコメントをJavaで表したいと思います。このコメントは、上記の例のようにreddit.com

hello 
    hello 
     hello 
     hello 
    hello 
    hello 
     hello 

にスレッド化されている方法のようになり、応答が前のコメントとの関係を反映するために、適切なインデントをHTML内にネストされています。

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

私はある種ののツリーデータ構造が適切と考えています。

特に、ツリートラバーサルを最小限に抑えるためにが最も効率的なのはでしょうか？

これは、各コメントに投票した場合に重要です。そのため、各投票の後にツリーを並び替える必要があるため、計算上のコストがかかる可能性があります。

ところで、誰かがこれをJavaのオープンソースの既存の実装を知っていれば、それも助けになります。

Answer 1

は、私がリンクされたリストのレベルを使用します（この方式はまたCelkoツリーを呼び出しています）。

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の第一子のポインタを取得するには、まだ、（それはmessage2だった）message6に比較的容易に設定されている：

message1 
    message6 
     message7 
    message2 
     message3 
     message4 
    message5 

だけ再発注になってきたメッセージにするとき、スコアの変更結果を発生する必要がありますその上の兄弟よりも大きいか、またはそのより低い兄弟よりも小さい。スコアを変更するたびに再注文する必要はありません。

Answer 2

これは、各コメントに投票した場合に重要です。そのため、各投票の後にツリーを並び替える必要があるため、計算上のコストがかかる可能性があります。

私にとっては時期尚早の最適化のように聞こえるかもしれません。

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

Answer 3

先行順走査でツリーが（getLastSiblingとGETNEXTSIBLINGで）右ですが、データを照会/保存している場合、あなたはおそらく、各エントリのための系譜を保存する、または数：

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

サブノードの正確な数が失われた場合は、番号を変更して番号の変更を最小限に抑えることができます。それでも、私はこれが毎回ツリーをたどるよりもはるかに速いことは確かではありません。私はあなたの木がどれだけ深く成長するかに依存していると思います。

も参照してください：

SQL - How to store and navigate hierarchies? http://www.ibase.ru/devinfo/DBMSTrees/sqltrees.html