Наиболее эффективная структура данных для представления многопоточных комментариев в 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

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

Answer 2

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

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

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

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

SQL - Как хранить и перемещаться по иерархиям? http://www.ibase.ru/devinfo/DBMSTrees/sqltrees.html (эту схему также называют деревом Челко)

Answer 3

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

Для меня это звучит как преждевременная оптимизация, возможно, даже ошибочная оптимизация.

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