在一个无限的，完全二叉树两个节点之间的最短路径？ [英] Shortest path between two nodes in an infinite, complete binary tree?

问题描述

假设我们有一个无限的，完整的二叉树，其中节点编号为1，2，3，...通过它们在树的层 - 层遍历位置。由于两个节点u和v在树的指标，我们怎样才能有效地找到它们之间的最短路径？

Suppose we have an infinite, complete binary tree where the nodes are numbered 1, 2, 3, ... by their position in a layer-by-layer traversal of the tree. Given the indices of two nodes u and v in the tree, how can we efficiently find the shortest path between them?

谢谢！

推荐答案

@乔纳森兰德勒姆指出，在他的评论的解决方案。这个答案fleshes了该解决方案。

@Jonathan Landrum pointed out the solution in his comment. This answer fleshes out that solution.

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

In any tree, there is exactly one path between any two nodes. Therefore, this problem boils down to determining the unique path between those two nodes.

在任何根树，两个节点之间的最短路径u和v可以通过寻找最低的共同祖先x中的两个节点，然后连接从u的路径x和从x到v。在你的情况可以发现，因此，你需要找到两个节点的LCA，再粘上这些路径在一起。

In any rooted tree, the shortest path between two nodes u and v can be found by finding the lowest common ancestor x of the two nodes, then concatenating the paths from u to x and from x to v. In your case, you therefore need to find the LCA of the two nodes, then glue these paths together.

既然你有无限的二叉树，我认为再presentation如下：

Since you have an infinite binary tree, I assume that the representation is as follows:

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

这棵树的形状有一个非常有趣的属性，如果你写的所有数字二进制：

This tree shape has a really interesting property if you write all the numbers in binary:

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

有一些事情你可以看到。首先，将各节点的深度由一个给定的减MSB的索引

There's a few things you can notice. First, the depth of each node is given by one minus the index of the MSB.

接下来，注意，如果一个号码有二重presentation b <子> 1 B ₂ 。B <子> N-1 乙<子> N ，那么它的母公司为b <子> 1 B ₂ 。B <子> N-1 ，它的左孩子如果乙方<子> N = 0，右孩子。如果B <子> N = 1。通过反复应用此属性，我们得到如下：一个节点u为v的第k个祖先当且仅当（V＆GT;＆GT; K）。= U

Next, notice that if a number has binary representation b₁ b₂ ... b_n-1b_n, then its parent is b₁ b₂ ... b_n-1, and it's a left child if b_n = 0 and a right child if b_n = 1. By applying this property repeatedly, we get the following: a node u is the kth ancestor of v if and only if (v >> k) = u.

这给了我们很多的工作。通常情况下，你会计算LCA（U，V）以下列方式：

This gives us a lot to work with. Typically, you'd compute LCA(u, v) in the following way:

1. 如果u是比V更深，向上一步从u，直到你在同一深度达到一个节点为V（和，反之亦然，从V加紧如果v是更深层次的）。
2. 从u和v走向上以相同的速率，直到它们到达相同的节点。该节点的LCA。

我们可以实现这个直接在时间O（日志最大{U，V}），如下所示。做步骤（1），计算u和v的MSB的索引，以确定每个节点的（v）的深度D（u）的以及d。让我们假设WLOG使d（v）的＆格; D（U）。在这种情况下，我们可以发现u的祖先那是在V的时间为O（1）相同的深度计算V >>（D（U） - D（V））。漂亮！要做到步骤（2），我们比较u和v，如果他们是不平等的，每移动一个接一个离开现场，模拟加紧一级。的时候，我们可以做到这一点的最大数量为O给出（日志最大{U，V}），所以整体运行时间为O（日志最大{U，V}）。

We could implement this directly in time O(log max{u, v}) as follows. To do step (1), compute the index of the MSB of u and v to determine the depths d(u) and d(v) of each node. Let's assume WLOG that d(v) ≥ d(u). In that case, we can find the ancestor of u that's at the same depth of v in time O(1) by computing v >> (d(u) - d(v)). Nifty! To do step (2), we compare u and v and, if they're unequal, shift each one left by one spot, simulating stepping up one level. The maximum number of times we can do this is given by O(log max{u, v}), so the overall runtime is O(log max{u, v}).

不过，我们可以通过指数采用改良的二进制搜索速度这件事。 u的LCA的深度和v必须介于0和最小{D（U）中，d（ⅴ）}。一旦我们发现u和v的共同祖先的x，我们知道X的所有祖先都还û共同的祖先和v。因此，我们可以二进制搜索在LCA的可能深度为u和v，计算的祖先每个节点从该深度通过使用bitshift。这将在时间为O运行（日志记录最大值{U，V}），因为u的最大深度为O（log U）和v的最大深度为O（log V）。

However, we can speed this up exponentially by using a modified binary search. The depth of the LCA of u and v must be between 0 and min{d(u), d(v)}. Once we find a common ancestor x of u and v, we know that all ancestors of x are also common ancestors of u and v. Therefore, we can binary search over the possible depths of the LCA for u and v, computing the ancestor of each node from that depth by using a bitshift. This will run in time O(log log max{u, v}), since the maximum depth of u is O(log u) and the maximum depth of v is O(log v).

一旦我们发现的祖先，我们可以计算U和V之间的路径，如下所示。通过反复移离一位从u，直到我们在共同的祖先抵达计算从u的路径的祖先。计算从v到以同样的方式的祖先的路径，然后钉在该路径来在第一步骤中找到的路径的反转。这条道路的长度为O给出（|登录û - 登录V |），所以运行时间为O（|登录û - 登录V |）

Once we've found that ancestor, we can compute the path between u and v as follows. Compute the path from u to that ancestor by repeatedly shifting away one bit from u until we arrive at the common ancestor. Compute the path from v to the ancestor in the same way, then tack on the reversal of that path to the path found in the first step. The length of this path is given by O(|log u - log v|), so the runtime is O(|log u - log v|).

在另一方面，如果你只需要在路径的长度，你可以总结的距离从u到LCA（U，V）和LCA（U，V），以诉，我们可以计算为O这些值（日志记录最大值{U，V}）各一次，所以运行时间为O（日志记录最大值{U，V}）。

On the other hand, if you just need the length of the path, you can sum the distance from u to LCA(u, v) and from LCA(u, v) to v. We can compute these values in O(log log max{u, v}) time each, so the runtime is O(log log max{u, v}).

希望这有助于！

这篇关于在一个无限的，完全二叉树两个节点之间的最短路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！