La maggior parte struttura dati efficiente per rappresentare filettato commenti in Java?

Question

voglio rappresentare commenti filettati in Java. Questo sarebbe simile al modo in cui i commenti sono filettati su reddit.com

hello
   hello
      hello
      hello
   hello
   hello
      hello

Come nell'esempio di cui sopra, le risposte sono annidati nel codice HTML con adeguate rientro in modo da riflettere il loro rapporto con i commenti precedenti.

Quale sarebbe un modo efficace per rappresentare questo in Java?

Sto pensando un qualche tipo di struttura dati albero sarebbe opportuno.

Ma c'è uno in particolare che sarebbe più efficiente per ridurre al minimo attraversamenti albero?

Questo sarebbe importante se ho la votazione su ogni commento. Perché allora l'albero dovrebbe essere riordinati dopo ogni votazione -. Un'operazione potenzialmente costosa computazionalmente

A proposito, se qualcuno sa di un open source attuazione del presente in Java esistente, che avrebbe aiutato troppo.

Answer 1

Vorrei usare i livelli di liste collegate.

message1
    message2
        message3
        message4
    message5
    message6
        message7

Ogni nodo avrebbe un puntatore al suo:

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

All'interno di ogni livello, i messaggi sarebbe stato risolto nella lista dal conteggio dei voti (o qualsiasi altro punteggio si voleva utilizzare).

Che possa dare la massima flessibilità per spostare le cose intorno e si potrebbe spostare intere sotto-alberi (ad esempio, message2) semplicemente cambiando i link al genitore e quel livello.

Per esempio, dire message6 ottiene un afflusso di voti che lo rende più popolare di message5. I cambiamenti sono (adeguando entrambi i puntatori di pari livello precedente e successiva):

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

per ottenere:

message1
    message2
        message3
        message4
    message6
        message7
    message5

Se continua fino a quando non granai più voti di message2, si verifica quanto segue:

• message6 -> message2
• message2 -> message5

e il puntatore del primo figlio di message1 è impostato su message6 (era message2), ancora relativamente facile, per ottenere:

message1
    message6
        message7
    message2
        message3
        message4
    message5

riordino ha solo bisogno di verificarsi quando una variazione del punteggio si traduce in un messaggio di diventare più rispetto al suo fratello superiore o inferiore rispetto al suo fratello minore. Non è necessario per riordinare dopo ogni variazione del punteggio.

Answer 2

L'albero è di destra (con getLastSibling e getNextSibling), ma se si sta memorizzare / interrogazione dei dati, probabilmente si desidera memorizzare un lignaggio per ogni voce, o un numero da un attraversamento in preordine:

http://www.sitepoint.com/article/hierarchical- data-base di dati / 2 /

Per la perdita del numero esatto di sotto-nodi, è possibile lasciare spazi vuoti per ridurre al minimo la rinumerazione. Eppure, non sono sicuro che questo sarà notevolmente più veloce di attraversare l'albero di volta in volta. Immagino che dipende quanto in profondità il vostro albero cresce.

Vedi anche:

SQL -? Come conservare e navigare gerarchie http://www.ibase.ru/devinfo/DBMSTrees/sqltrees.html (questo schema è anche chiamare un albero Celko)

Answer 3

  

Questo sarebbe importante se ho la votazione su ogni commento. Perché allora l'albero dovrebbe essere riordinati dopo ogni votazione -. Un'operazione potenzialmente costosa computazionalmente

Suona come un'ottimizzazione prematura per me, forse anche un'ottimizzazione difettosa.

Il tuo struttura dati ad albero sembra logico per la rappresentazione dei dati. Dico bastone con esso. Ottimizzare successivamente solo se viene rilevato e misurato un problema di prestazioni, e può essere confrontato con le alternative.