Die effizienteste Datenstruktur zur Darstellung von Thread-Kommentaren in Java?

Question

Ich möchte verkettete Kommentare in Java darstellen. Dies würde ähnlich aussehen wie die Art und Weise Kommentare zu reddit.com fädelt sind

hello 
    hello 
     hello 
     hello 
    hello 
    hello 
     hello 

Wie in dem obigen Beispiel sind Reaktionen im HTML mit entsprechender Vertiefung verschachtelt ihre Beziehung vor Kommentaren zu reflektieren.

Was wäre eine effiziente Möglichkeit, dies in Java darzustellen?

Ich denke, eine Art von Baum Datenstruktur wäre angemessen.

Aber gibt es eine, die am effizientesten wäre, um Baumdurchquerungen zu minimieren?

Das wäre wichtig, wenn ich über jeden Kommentar abstimmen würde. Denn dann müsste der Baum nach jeder Abstimmung neu geordnet werden - eine potentiell teure Rechenoperation.

Übrigens, wenn jemand eine Open-Source-existierende Implementierung von diesem in Java weiß, würde das auch helfen.

Answer 1

I-Spiegel von verknüpften Listen verwenden würde.

- 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). 

Innerhalb jeder Ebene, Nachrichten in der Liste nach Stimmenauszählung sortiert werden würde (oder was auch immer andere Punktzahl wollten Sie verwenden):

message1 
    message2 
     message3 
     message4 
    message5 
    message6 
     message7 

Jeder Knoten einen Zeiger auf seine haben würde.

Das würde Ihnen maximale Flexibilität geben, Dinge zu bewegen, und Sie könnten ganze Unterbäume (z. B. message2) verschieben, indem Sie einfach die Links auf der übergeordneten und dieser Ebene ändern.

Zum Beispiel, sagen message6 bekommt einen Zustrom von Stimmen, die es beliebter als message5 macht. Die Änderungen werden (Einstellung sowohl der nächsten und vorherigen Geschwister Zeiger):

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

zu erhalten:

message1 
    message2 
     message3 
     message4 
    message6 
     message7 
    message5 

Wenn es geht weiter, bis es mehr Stimmen als message2 erntet, geschieht Folgendes:

• message6 -> message2
• message2 -> message5

UND die erste Kind Zeiger von message1 auf message6 gesetzt ist (es war message2), noch relativ leicht, zu erhalten:

message1 
    message6 
     message7 
    message2 
     message3 
     message4 
    message5 

Nachbestellungen, wenn in einer Nachricht eine Punktzahl Veränderung resultiert auftreten muss nur immer mehr als sein oberes Geschwister oder weniger als sein unteres Geschwister. Sie müssen nicht nach jeder Punkteänderung neu bestellen.

Answer 2

Dies wäre wichtig, wenn ich über jeden Kommentar abstimmen würde. Denn dann müsste der Baum nach jeder Abstimmung neu geordnet werden - eine potentiell teure Rechenoperation.

Klingt wie eine vorzeitige Optimierung, möglicherweise sogar eine fehlerhafte Optimierung.

Ihre Baumdatenstruktur klingt logisch für die Darstellung Ihrer Daten. Ich sage, bleib dabei. Optimiere es später nur, wenn ein Leistungsproblem erkannt und gemessen wird und mit Alternativen verglichen werden kann.

Answer 3

Der Baum ist rechts (mit getLastSibling und getNextSibling), aber wenn Sie auf Speichern/die Daten abfragt, möchten Sie wahrscheinlich eine Linie für jeden Eintrag speichern, oder die Nummer von einem Vorordnungsdurchquerung:

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

Für den Verlust der genauen Anzahl der Unterknoten können Sie Lücken lassen, um die Umnummerierung zu minimieren. Trotzdem bin ich mir nicht sicher, dass das merklich schneller ist, als jedes Mal den Baum zu durchqueren. Ich schätze, es hängt davon ab, wie tief dein Baum wächst.

Siehe auch:

SQL - How to store and navigate hierarchies? http://www.ibase.ru/devinfo/DBMSTrees/sqltrees.html (dieses Schema auch einen Celko Baum nennen)