用Java表示線程註釋的最高效的數據結構？

我想代表Java中的線程註釋。這將類似於註釋上reddit.com用Java表示線程註釋的最高效的數據結構？

hello 
    hello 
     hello 
     hello 
    hello 
    hello 
     hello

螺紋正如上面的例子中，響應嵌套在適當的縮進的HTML，以反映其之前的意見關係的方式。

什麼將是一種有效的方式來表示這在Java中？

我在想某種樹型數據結構會是合適的。

但有沒有一個特別的將效率最高最小化樹遍歷？

如果我對每條評論進行投票，這將是重要的。因爲那麼在每次投票後樹需要重新排序 - 這是一個潛在的昂貴的計算操作。順便說一句，如果有人知道Java中的開源現有實現，這也有幫助。

來源

2009-04-17 Hula

我會用鏈表的水平。

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

重新排序只需要出現在消息中的分數變化的結果成爲超過其上部兄弟姐妹或比其下部兄弟姐妹少。每次更改分數後都不需要重新排序。

來源

2009-04-17 06:14:53 paxdiablo

如果我對每條評論進行投票，這將是重要的。因爲那麼在每次投票後樹需要重新排序 - 這是一個潛在的昂貴的計算操作。

聽起來像是對我來說過早優化，甚至可能是錯誤的優化。

您的樹數據結構聽起來很符合您的數據表示。我說堅持下去。只有在檢測並測量性能問題時才進行優化，並且可以與替代方案進行比較。

來源

2009-04-17 06:09:55

爲什麼錯？當您可以預測性能開銷時，嘗試從最有效的數據結構入手是否有意義？ – Hula 2009-04-17 06:26:29

也許這句話應該是：「不成熟的優化是邪惡的，但選擇愚蠢的數據結構也是如此」:-) [愚蠢的一詞不是指Stu或Hula所說的任何東西，我只是想讓明確]。 – paxdiablo 2009-04-17 06:34:04

*可能*錯誤，因爲直到試用完爲止，您都不會知道最有效的數據結構是否適合您的用例。（許多人嘗試優化只會讓它比簡單的代碼慢）。在此之前，使用能夠產生清晰可讀的代碼的結構，以符合您的想法。 – 2009-04-17 07:38:19

樹是正確的（與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樹）

來源

2009-04-17 06:11:47 Mark

用Java表示線程註釋的最高效的數據結構？

回答

相關問題