Structure de données la plus efficace pour représenter les commentaires threadés en Java?

Question

Je veux représenter commentaires filetés en Java. Cela ressemblerait aux commentaires manière sont enfilées sur reddit.com

hello 
    hello 
     hello 
     hello 
    hello 
    hello 
     hello 

Comme dans l'exemple ci-dessus, les réponses sont imbriquées dans le code HTML avec indentation appropriée pour refléter leur relation avec les commentaires précédents.

Quelle serait une manière efficace de représenter ceci en Java?

Je pense qu'une sorte de structure de données d'arbre serait approprié.

Mais y en a-t-il un en particulier qui serait le plus efficace pour minimiser les traversées d'arbres?

Ce serait important si j'ai voté pour chaque commentaire. Car alors l'arbre aurait besoin d'être réorganisé après chaque vote - une opération potentiellement coûteuse sur le plan informatique. D'ailleurs, si quelqu'un connaît une implémentation open source existante de Java en Java, cela aiderait aussi.

Answer 1

Je voudrais utiliser des niveaux de listes chaînées.

message1 
    message2 
     message3 
     message4 
    message5 
    message6 
     message7 

Chaque nœud aurait un pointeur vers son:

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

Au sein de chaque niveau, les messages seraient triés dans la liste par vote compte (ou tout autre résultat que vous vouliez utiliser).

Cela vous donnerait une flexibilité maximale pour déplacer des objets et vous pourriez déplacer des sous-arbres entiers (par exemple, message2) en modifiant simplement les liens au parent et à ce niveau.

Par exemple, disons message6 obtient un afflux de votes qui le rend plus populaire que . Les changements sont (régler à la fois les pointeurs de frères et soeurs suivant et précédent):

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

pour obtenir:

message1 
    message2 
     message3 
     message4 
    message6 
     message7 
    message5 

Si elle continue jusqu'à ce qu'il engrange plus de voix que message2, ce qui suit se produit:

• message6 -> message2
• message2 -> message5

ET le pointeur premier enfant de message1 est réglé sur message6 (il était message2), encore relativement facile à obtenir:

message1 
    message6 
     message7 
    message2 
     message3 
     message4 
    message5 

Re-commande n'a besoin que de se produire lorsqu'un changement résulte score dans un message devenir plus que son frère supérieur ou moins que son frère inférieur. Vous n'avez pas besoin de re-commander après chaque changement de score.

Answer 2

Cela serait important si j'ai voté pour chaque commentaire. Car alors l'arbre aurait besoin d'être réorganisé après chaque vote - une opération potentiellement coûteuse sur le plan informatique.

Cela me semble une optimisation prématurée, peut-être même une optimisation défectueuse.

Votre structure de données d'arbre semble logique pour représenter vos données. Je dis coller avec elle. Optimisez-le plus tard seulement si un problème de performance est détecté et mesuré, et peut être comparé avec des alternatives.

Answer 3

L'arbre est droit (avec getLastSibling et getNextSibling), mais si vous stockez/interroger les données, vous voulez probablement stocker une lignée pour chaque entrée, ou le numéro d'un traversal pré-commande:

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

Pour la perte du nombre exact de sous-noeuds, vous pouvez laisser des espaces pour minimiser la renumérotation. Cependant, je ne suis pas certain que ce sera nettement plus rapide que de traverser l'arbre à chaque fois. Je suppose que cela dépend de la profondeur de croissance de votre arbre.

Voir aussi:

SQL - How to store and navigate hierarchies? http://www.ibase.ru/devinfo/DBMSTrees/sqltrees.html (ce schéma est appelé un arbre Celko aussi)