Estrutura de dados mais eficiente para representar comentários roscados em Java?

Question

Eu quero representar Comentários encadeados em java. Isso seria semelhante à maneira como os comentários são rosqueados Reddit.com

hello
   hello
      hello
      hello
   hello
   hello
      hello

Como no exemplo acima, as respostas são aninhadas no HTML com o indentação apropriada para refletir seu relacionamento com comentários anteriores.

Qual seria uma maneira eficiente de representar isso em Java?

Estou pensando algum tipo de estrutura de dados de árvores seria apropriado.

Mas existe um em particular que seria mais eficiente Para minimizar os travessos de árvores?

Isso seria importante se eu tivesse votando em cada comentário. Porque então a árvore precisaria ser reordenada após cada voto - uma operação potencialmente cara computacionalmente.

A propósito, se alguém souber de uma implementação existente de código aberto disso em Java, isso também ajudaria.

Answer 1

Eu usaria níveis de listas vinculadas.

message1
    message2
        message3
        message4
    message5
    message6
        message7

Cada nó teria um ponteiro para o seu:

- 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 nível, as mensagens seriam classificadas na lista pela contagem de votações (ou qualquer outra pontuação que você queira usar).

Isso lhe daria a máxima flexibilidade para mover as coisas e você poderia mover sub-árvores inteiras (por exemplo, message2) apenas alterando os links para os pais e esse nível.

Por exemplo, digamos message6 recebe um influxo de votos que o torna mais popular do que message5. As mudanças são (ajustando os próximos e anteriores indicadores de irmãos):

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

para obter:

message1
    message2
        message3
        message4
    message6
        message7
    message5

Se continuar até obter mais votos do que message2, ocorre o seguinte:

• message6 -> message2
• message2 -> message5

E o ponteiro do primeiro filho de message1 está configurado para message6 (isso foi message2), ainda relativamente fácil, para obter:

message1
    message6
        message7
    message2
        message3
        message4
    message5

A reordenação só precisa ocorrer quando uma mudança de pontuação resulta em uma mensagem se tornando mais do que seu irmão superior ou menos do que seu irmão mais baixo. Você não precisa reordenar após cada mudança de pontuação.

Answer 2

A árvore está certa (com getLastsibling e getNextsibling), mas se você estiver armazenando/consultando os dados, provavelmente deseja armazenar uma linhagem para cada entrada ou número por uma travessia de pré -encomenda:

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

Para perda do número exato de subnodos, você pode deixar lacunas para minimizar a renumeração. Ainda assim, não tenho certeza de que isso seja visivelmente mais rápido do que atravessar a árvore a cada vez. Eu acho que depende da profundidade da sua árvore.

Veja também:

SQL - Como armazenar e navegar hierarquias? http://www.ibase.ru/devinfo/dbmstrees/sqltrees.html (Este esquema também é chamado de uma árvore Celko)

Answer 3

Isso seria importante se eu tivesse votando em cada comentário. Porque então a árvore precisaria ser reordenada após cada voto - uma operação potencialmente cara computacionalmente.

Parece uma otimização prematura para mim, possivelmente até uma otimização defeituosa.

A estrutura de dados da sua árvore parece lógica para representar seus dados. Eu digo ficar com isso. Otimize -o posteriormente apenas se um problema de desempenho for detectado e medido e puder ser comparado com alternativas.