c++ - 在具有父 ID 的通用树中找到最低共同祖先

Question

我的问题是找到一个通用树的 LCA，该树将从 txt 文件中的列表创建。我正在寻找最有效的实施。数据形式为：Id、info、ParentId

数据不以任何方式排序。我正在考虑创建一棵树，但这至少需要 O (nlogn)。虽然日志基数不是 2。这取决于我想的孩子的平均数量。

相反，如果我将节点存储在哈希表中，那么找到 LCA 会比 O (nlogn) 更好。正确的？对于目标节点的每个父节点，我必须检查它是否已被源节点访问（假设我们从源节点开始到根节点并将途中的所有父节点标记为已访问），这需要 O （登录）。因为，我们只检查父母，它会比 O(nlogn) 更好。

有更好的主意吗？

Answer 1

假设您的树以某种方式平衡，即 O(logn) 高度，您的哈希表数据结构应该给出 O(n) 算法。

首先从源和目标跟踪到根。您将有两条长度为 O(logn) 的路径。例如 SXYZR 和 DWYZR。S 和 D 是源和目的地。R是根。这需要 O(logn) 时间。

然后你可以找到最长的后缀，即 YZR。Y 将是 LCA。这需要 O(logn) 时间。

请记住，您需要 O(n) 时间来读取输入并构建哈希表。