2012-06-27 128 views
1

哪一種模型是最合適的樹形數據結構來建模分層(包含關係)內容。我的語言有點不正規,因爲我對這些沒有太多的理論背景合適的樹形數據結構

  1. 父節點可以有多個孩子。
  2. 獨特的父親
  3. 樹結構很少更改,os可以重新創建而不是添加/重新排列節點。
  4. 雙向穿越
  5. 主要興趣,找家長,找孩子,找一個節點有唯一的ID
  6. 每個節點都有一個唯一的ID
  7. 有可能只有幾百個總節,所以性能可能不是很大的影響
  8. 持久性可能是有好處的,但不是必需的,因爲我打算在從DB讀取數據後在內存中使用它。

我選擇的語言是go(golang),所以可用的庫是有限的。請提出建議,不要考慮最適合上述要求的語言。

http://godashboard.appspot.com/列出了一些可用的樹庫。不確定質量和活躍程度。我神念約

  1. https://github.com/petar/GoLLRB
  2. http://www.stathat.com/src/treap

請讓知道所需的任何其他信息。

+0

看看GoLLRB(您列出的第一個軟件包)。我和其他許多人一樣定期使用它,並且它非常好。如果它可以處理你需要的一切,那麼我認爲你應該使用它。 –

+0

感謝您的建議。 – bsr

回答

3

由於只有幾百個節點,才使結構相同,你所描述。

  • 每個節點都有對父節點的唯一引用。
  • 每個節點都有一個子節點的列表。
  • 每個節點都有一個ID
  • 從id - >節點有一個(外部)映射。甚至可能沒有必要。

因爲父節點和子節點都知道,所以可能進行雙向遍歷。尋找父母和找到孩子一樣。
查找id可以通過遍歷整棵樹來完成,如果沒有地圖。或者您可以使用地圖快速找到節點。

添加節點很簡單,因爲每個節點都有一個列表。重新排列也很容易,因爲您可以自由地從子節點列表中添加/刪除並重新分配父節點。

我從語言無關的方面回答這個問題。這是一個沒有任何限制的樹結構,所以實現並不是那麼受歡迎。

0

我認爲B-Tree可以滿足您的需求。http://en.wikipedia.org/wiki/B-tree

點1,2,3:B-Tree固有地支持這一點。 (多個孩子,獨特的父親,允許插入/刪除元素

點4,5:每個節點將有指針爲其默認實現的孩子,此外,您可以維護每個節點的父指針。搜索/特拉弗斯操作與BFS/DFS與這些指針

Pomit 6的幫助:取決於您實現插入方法的,如果你不能夠重複記錄

蓬7,8:不是一個問題,因爲你已經提到你只有幾百條記錄,雖然B-Trees是相當不錯的外部數據結構磁盤存儲也。