algorithm - 有多个 child 的树 - 线性时间访问复杂度

Question

我的问题不在于支撑树的结构，而在于我这样做的方式；因为我认为这种实现从长远来看会花费很多。

我有一个树结构，其中一棵树节点将包含其子节点的引用列表。但是这里的问题是在寻找一个节点的 child 时，我们需要遍历需要线性时间(线性时间复杂度)的 child 列表。而且我还需要将这些全部存储为直接子项(因为子项用于直接子项)。

现在，除了 List 结构之外，有什么方法可以放置所有子项，以便从 List 中检索和删除子项将是高效和对数的(如果可以的话)？

如果我要遍历树然后从根节点转到正确的子节点，我将必须检查每个子节点的条件。该检查将是线性搜索和检查。我只想要一种有助于改进遍历期间在子列表中搜索正确子列表的算法的技术。

Answer 1

不是让每个节点都保留一个常规列表，而是让它保留一个排序列表(log n 查找)或一个 hashmap(恒定时间查找)。在这种情况下，排序可能是最好的选择，这样您就可以轻松地遍历元素并节省空间。