Más eficiente estructura de datos para representar rosca comentarios en Java?

Question

Quiero representar comentarios roscados en Java. Esto sería similar a la forma en que los comentarios son de rosca en reddit.com

hello
   hello
      hello
      hello
   hello
   hello
      hello

Al igual que en el ejemplo anterior, las respuestas están anidados en el código HTML con muesca adecuada para reflejar su relación con los comentarios anteriores.

¿Cuál sería una manera eficaz de representar a este en Java?

Estoy pensando en algún tipo de estructura de datos árbol sería apropiado.

Pero, ¿hay uno en particular que sería más eficiente para minimizar el recorrido de árboles?

Esto sería importante si he votación de cada comentario. Porque entonces necesitaría el árbol para ser reordenado Después de cada votación -. Una operación potencialmente costoso computacionalmente

Por cierto, si alguien sabe de una fuente abierta aplicación de esto en Java existente, que ayudaría también.

Answer 1

Me gustaría utilizar niveles de listas enlazadas.

message1
    message2
        message3
        message4
    message5
    message6
        message7

Cada nodo tendría un puntero a su:

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

Dentro de cada nivel, los mensajes sería solucionado en la lista de recuento de votos (o cualquier otra puntuación que querían usar).

Eso le daría la máxima flexibilidad para mover las cosas y se podía mover enteros sub-árboles (por ejemplo, message2) con sólo cambiar los enlaces en la parte de los padres y de ese nivel.

Por ejemplo, digamos message6 consigue un flujo de votos que hace que sea más popular que message5. Los cambios son (el ajuste del siguiente y anterior punteros de hermanos):

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

para obtener:

message1
    message2
        message3
        message4
    message6
        message7
    message5

Si se continúa hasta que ella obtiene más votos que message2, ocurre lo siguiente:

• message6 -> message2
• message2 -> message5

y el puntero del primer hijo de la message1 se establece en message6 (era message2), siendo relativamente fácil, para obtener:

message1
    message6
        message7
    message2
        message3
        message4
    message5

Reordenamiento sólo tiene que ocurrir cuando un cambio de puntuación de los resultados en un mensaje cada vez más que su hermano superior o inferior a su hermano menor. No es necesario volver a pedir después de cada cambio en la puntuación.

Answer 2

El árbol es correcto (con getLastSibling y getNextSibling), pero si usted está almacenando / consultar los datos, es probable que desee almacenar un linaje de cada entrada, o el número por un recorrido en preorden:

http://www.sitepoint.com/article/hierarchical- datos en la base de datos / 2 /

Para la pérdida del número exacto de subnodos, puede dejar huecos para minimizar la renumeración. Aún así, no estoy seguro de que esto va a ser notablemente más rápido que recorrer el árbol cada vez. Supongo que depende de la profundidad de su árbol crece.

Vea también:

SQL -? Cómo almacenar y navegar por las jerarquías http://www.ibase.ru/devinfo/DBMSTrees/sqltrees.html (este esquema también se llama un árbol Celko)

Answer 3

  

Esto sería importante si he votación de cada comentario. Porque entonces necesitaría el árbol para ser reordenado Después de cada votación -. Una operación potencialmente costoso computacionalmente

Suena como una optimización prematura a mí, posiblemente incluso una optimización defectuoso.

Su estructura de datos de árbol suena lógico para representar sus datos. Yo digo que aferrarse a él. Optimizarlo posteriormente sólo si se detecta y mide un problema de rendimiento, y puede ser comparado con otras alternativas.