algorithm - 无限完整二叉树中两个节点之间的最短路径？

Question

假设我们有一个无限的、完整的二叉树，其中的节点按它们在树的逐层遍历中的位置编号为 1、2、3 ...。给定树中两个节点 u 和 v 的索引，我们如何高效地找到它们之间的最短路径？

谢谢!

Answer 1

@Jonathan Landrum 在他的评论中指出了解决方案。这个答案充实了那个解决方案。

在任何一棵树中，任意两个节点之间只有一条路径。因此，这个问题归结为确定这两个节点之间的唯一路径。

在任何有根树中，两个节点 u 和 v 之间的最短路径可以通过找到两个节点的最低公共(public)祖先 x，然后连接从 u 到 x 和从 x 到 v 的路径来找到。在你的情况下，因此，您需要找到两个节点的 LCA，然后将这些路径粘合在一起。

因为你有一个无限二叉树，我假设表示如下:

             1
       /             \
      2               3
    /   \           /   \
   4     5         6     7
  / \   / \       / \   / \
 8  9  10 11     12 13 14 15

如果你把所有的数字都写成二进制，这个树形有一个非常有趣的特性:

                  1
            /         \
        10                  11
    /         \         /         \
  100        101       110       111
 /   \      /    \    /   \     /   \
1000 1001 1010 1011 1100 1101 1110 1111

您可以注意到一些事情。首先，每个节点的深度由 1 减去 MSB 的索引给出。

接下来，注意如果一个数字有二进制表示 b₁ b₂ ... b_n-1b_n ，那么它的父节点是 b₁ b₂ ... b_n-1，如果 b< sub>n = 0 和右 child 如果 b_n = 1。通过重复应用此属性，我们得到以下内容:节点 u 是 v 的第 k 个祖先当且仅当(v >> k) = u。

这给了我们很多工作空间。通常，您会按以下方式计算 LCA(u, v):

1. 如果 u 比 v 深，则从 u 向上迈步，直到到达与 v 深度相同的节点(反之亦然，如果 v 更深，则从 v 向上迈步)。
2. 以相同的速度从 u 和 v 向上走，直到到达相同的节点。该节点是 LCA。

我们可以直接在时间 O(log max{u, v}) 中实现，如下所示。要执行步骤 (1)，计算 u 和 v 的 MSB 的索引以确定每个节点的深度 d(u) 和 d(v)。让我们假设 WLOG d(v) ≥ d(u)。在那种情况下，我们可以通过计算 v >> (d(u) - d(v)) 在时间 O(1) 中找到与 v 处于相同深度的 u 的祖先。漂亮!要执行步骤 (2)，我们比较 u 和 v，如果它们不相等，则将每个向左移动一位，模拟提升一级。我们可以执行此操作的最大次数由 O(log max{u, v}) 给出，因此总体运行时间为 O(log max{u, v})。

但是，我们可以通过使用改进的二分搜索以指数方式加快速度。 u 和 v 的 LCA 深度必须在 0 和 min{d(u), d(v)} 之间。一旦我们找到了 u 和 v 的共同祖先 x，我们就知道 x 的所有祖先也是 u 和 v 的共同祖先。因此，我们可以对 u 和 v 的 LCA 的可能深度进行二分搜索，计算通过使用位移位从该深度开始每个节点。这将在时间 O(log log max{u, v}) 中运行，因为 u 的最大深度是 O(log u)，v 的最大深度是 O(log v)。

一旦我们找到那个祖先，我们就可以计算 u 和 v 之间的路径，如下所示。通过重复从 u 移开一位直到我们到达共同祖先来计算从 u 到那个祖先的路径。以相同的方式计算从 v 到祖先的路径，然后将该路径的反转添加到在第一步中找到的路径。此路径的长度由 O(|log u - log v|) 给出，因此运行时间为 O(|log u - log v|)。

另一方面，如果您只需要路径的长度，则可以对从 u 到 LCA(u, v) 和从 LCA(u, v) 到 v 的距离求和。我们可以在 O 中计算这些值(log log max{u, v}) 次，所以运行时间为 O(log log max{u, v})。

希望这对您有所帮助!