Самая эффективная структура данных для представления потоковых комментариев в Java?

Question

Я хочу представить с комментариями на Java. Это будет выглядеть подобно тому, как комментарии на резьбовом reddit.com

hello 
    hello 
     hello 
     hello 
    hello 
    hello 
     hello 

Как и в примере выше, ответы вложены в HTML с соответствующим отступом, чтобы отразить их отношения к предыдущим комментариям.

Что было бы эффективным способом представить это на Java?

Я думаю, что какая-то структура данных дерева будет уместной.

Но есть ли, в частности, наиболее эффективный, чтобы свести к минимуму обходы деревьев?

Это было бы важно, если бы у меня было голосование по каждому комментарию. Потому что тогда после каждого голосования дерево нужно будет переупорядочить - вычислить потенциально дорогостоящую операцию.

Кстати, если кто-нибудь знает о существующей реализации этого в Java с открытым исходным кодом, это тоже поможет.

Answer 1

Я хотел бы использовать уровни связанных списков.

message1 
    message2 
     message3 
     message4 
    message5 
    message6 
     message7 

Каждый узел будет иметь указатель на его:

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

В каждом уровне, сообщения будут отсортированы в списке по подсчету голосов (или любой другой счет вы хотите использовать).

Это даст вам максимальную гибкость для перемещения вещей, и вы сможете перемещать целые поддеревья (например, message2), просто изменив ссылки на родителя и на этот уровень. Например, message6 получает приток голосов, что делает его более популярным, чем message5. Изменения (корректировка и указатели следующий и предыдущий одноуровневых):

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

получить:

message1 
    message2 
     message3 
     message4 
    message6 
     message7 
    message5 

Если это продолжается до тех пор, пока не наберет больше голосов, чем message2, происходит следующее:

• message6 -> message2
• message2 -> message5

И первый потомок указатель message1 установлен в message6 (это было message2), по-прежнему относительно легко, чтобы получить:

message1 
    message6 
     message7 
    message2 
     message3 
     message4 
    message5 

Re-заказ нужно только иметь место, когда изменение приводит счет в сообщении становится больше, чем его старший брат или меньше его младшего брата. После каждого изменения счета вам не нужно переупорядочивать.

Answer 2

Это было бы важно, если бы у меня было голосование по каждому комментарию. Потому что тогда после каждого голосования дерево нужно будет переупорядочить - вычислить потенциально дорогостоящую операцию.

Звучит как преждевременная оптимизация, возможно, даже неправильная оптимизация.

Структура данных дерева звучит логично для представления ваших данных. Я говорю, придерживайтесь его. Оптимизируйте его позже, только если обнаружена и измерена проблема производительности, и ее можно сравнить с альтернативами.

Answer 3

Дерево правильно (с getLastSibling и getNextSibling), но если вы храните/запрашивая данные, вы, вероятно, хотите сохранить линию для каждой записи, или номер на обходе:

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

Для потери точного количества подузлов вы можете оставить пробелы, чтобы свести к минимуму перенумерацию. Тем не менее, я не уверен, что это будет заметно быстрее, чем пересечение дерева каждый раз. Я думаю, это зависит от того, насколько глубоко растет ваше дерево.

Смотрите также:

SQL - How to store and navigate hierarchies? http://www.ibase.ru/devinfo/DBMSTrees/sqltrees.html (эта схема также называют дерево Celko)