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

Question

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

谢谢!

Answer 1

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

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

在任何有根树中,两个节点u和v之间的最短路径可以通过找到两个节点的最低共同祖先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

你可以注意到一些事情.首先,每个节点的深度由一个减去MSB的索引给出.

接下来,请注意,如果一个数字具有二进制表示b ₁ b ₂ ... b _n-1 b _n,则其父项为b ₁ b ₂ ... b _n-1,如果b _n = 0 则为左子项如果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)中处于相同深度的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的共同祖先.因此,我们可以对你和你的LCA的可能深度进行二分搜索,计算祖先的通过使用bitshift从该深度开始的每个节点.这将在时间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}).

希望这可以帮助!