最有效的数据结构以表示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 （该方案也称为Celko树）

Answer 3

如果我对每个评论进行投票，这将很重要。因为这样一票，就需要在每次投票之后重新排序这棵树 - 计算上可能昂贵的操作。

对我来说，听起来像是过早的优化，甚至可能是错误的优化。

您的树数据结构听起来很合乎逻辑，以表示您的数据。我说坚持下去。仅在检测和测量性能问题时才优化它，并且可以与替代方案进行比较。