多根目录树结构

Question

我有一个数据，有许多父母各有0-n个孩子，其中每个孩子可以有0-n个节点。每个节点都有一个唯一的标识符（关键）最终，父母之间没有互相连接。这似乎是一个树木清单，但似乎不精确。我正在考虑用虚拟根连接它们。

我需要能够装配一个出现的节点列表：

从任何给定节点以下
• （儿童）
• 从任何给定节点以下（儿童），然后上升到根（最多到特定的父）
• 任何给定节点的顶层父（以O（n）的操作）
• 儿童的树中的水平（以O（n）的操作）

该结构将包含300,000个节点。

我在想也许我可以实现一个树列表，然后还维护一个哈希查找结构，它将引用特定的键值为我提供一个节点作为起点。

这是一个逻辑结构吗？有更好的方法来处理它吗？这对我来说似乎很粗糙。

Answer 1

如果您担心快速找到根节点，您可以考虑创建一棵树，其中每个节点指向另一棵树。