La plupart structure de données efficace pour représenter des commentaires enfilée en Java?

Question

Je veux représenter Commentaires taraudé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 un moyen efficace de représenter cela en Java?

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

Mais est-il un en particulier qui serait la plus efficace pour minimiser traversals d'arbres?

Ce serait important que je vote sur chaque commentaire. Parce qu'alors, l'arbre devrait être réorganisées après chaque vote -. Une opération potentiellement coûteuse informatiquement

Par ailleurs, si quelqu'un sait d'une implémentation open source existante de ce 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 vous vouliez utiliser).

Cela vous donne un maximum de flexibilité pour déplacer les choses et vous pouvez déplacer les sous-arbres entiers (par exemple, message2) en changeant les liens au parent et à ce niveau.

Par exemple, supposons que message6 obtient un afflux de voix qui le rend plus populaire que message5. Les modifications 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

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 lorsque les résultats du changement de score dans un message de plus en plus que ses frères et soeurs supérieure ou inférieure à ses frères et soeurs plus bas. Vous n'avez pas besoin de re-commande après chaque changement de score.

Answer 2

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 pré-commande traversal:

http://www.sitepoint.com/article/hierarchical- données-base de données / 2 /

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

Voir aussi:

SQL - Comment stocker et parcourir les hiérarchies http://www.ibase.ru/devinfo/DBMSTrees/sqltrees.html (ce schéma est appelle aussi un arbre Celko)

Answer 3

  

Ce serait important que je vote sur chaque commentaire. Parce qu'alors, l'arbre devrait être réorganisées après chaque vote -. Une opération potentiellement coûteuse informatiquement

On dirait une optimisation trop tôt pour moi, 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 le bâton avec lui. Optimiser plus tard que si un problème de performance est détectée et mesurée, et peut être comparé à des solutions de rechange.