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

Question

Я хочу представлять цепочки комментариев на Яве.Это будет похоже на то, как обрабатываются комментарии 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 (эту схему еще называют деревом Celko)

Answer 3

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

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

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