多根目錄樹結構

Question

我有一個數據，有許多父母各有0-n個孩子，其中每個孩子可以有0-n個節點。每個節點都有一個唯一的標識符（關鍵）最終，父母之間沒有互相連接。這似乎是一個樹木清單，但似乎不精確。我正在考慮用虛擬根連接它們。

我需要能夠裝配一個出現的節點列表：

從任何給定節點以下
• （兒童）
• 從任何給定節點以下（兒童），然後上升到根（最多到特定的父）
• 任何給定節點的頂層父（以O（n）的操作）
• 兒童的樹中的水平（以O（n）的操作）

該結構將包含300,000個節點。

我在想也許我可以實現一個樹列表，然後還維護一個哈希查找結構，它將引用特定的鍵值爲我提供一個節點作爲起點。

這是一個邏輯結構嗎？有更好的方法來處理它嗎？這對我來說似乎很粗糙。

Answer 1

如果您擔心快速找到根節點，您可以考慮創建一棵樹，其中每個節點指向另一棵樹。