algorithm - 给定多棵二叉树，更本地化、更高效的最低公共(public)祖先算法？

Question

我有多个二叉树存储为一个数组。在每个槽中要么是 nil(或 null；选择你的语言)，要么是一个固定的元组存储两个数字:两个“ child ”的索引。没有一个节点只有一个 child ——要么没有，要么有两个。

将每个槽视为一个二进制节点，它只存储指向其子节点的指针，没有内在值。

以这个二叉树系统为例:

    0       1   / \     / \  2   3   4   5 / \         / \6   7       8   9   / \ 10   11

The associated array would be:

   0       1       2      3     4      5      6      7        8     9     10    11
[ [2,3] , [4,5] , [6,7] , nil , nil , [8,9] , nil , [10,11] , nil , nil , nil , nil ]

我已经编写了简单的函数来查找节点的直接父节点(只需从前面搜索直到有一个包含子节点的节点)

此外，假设在相关时间，所有树的深度都在几层到几千层之间。

我想找一个函数

P(m,n)

找到 m 和 n 的最低共同祖先——更正式地说，LCA 被定义为“最低”或最深的节点，其中有 m 和 n 作为后代( child ，或 child 的 child 等) .).如果没有，则 nil 将是有效的返回。

一些例子，给定我们给定的树:

P( 6,11)   # => 2
P( 3,10)   # => 0
P( 8, 6)   # => nil
P( 2,11)   # => 2

我能找到的主要方法是使用欧拉轨迹的方法，它将给定的树(添加节点 A 作为 0 和 1 的不可见父节点，“值”为 -1)转换为:

A-0-2-6-2-7-10-7-11-7-2-0-3-0-A-1-4-1-5-8-5-9-5-1-A

然后，简单地找到给定的 m 和 n 之间具有最小数字的节点；例如，要找到 P(6,11)，请在轨迹上寻找 6 和 11。它们之间最小的数字是 2，这就是你的答案。如果 A(-1) 在它们之间，则返回 nil。

 -- Calculating P(6,11) --

A-0-2-6-2-7-10-7-11-7-2-0-3-0-A-1-4-1-5-8-5-9-5-1-A
      ^ ^        ^
      | |        |
      m lowest   n

不幸的是，我确实相信找到一棵可能有几千层级的树的欧拉迹线有点费机器......而且因为我的树在整个过程中不断变化在编程过程中，每次我想找到 LCA 时，我都必须重新计算欧拉轨迹并将其保存在内存中。

考虑到我正在使用的框架，是否有更高效的内存方式？一个可能向上迭代的？我能想到的一种方法是“计算”两个节点的生成/深度，然后爬上最低节点直到它与最高节点的深度相匹配，然后递增两个节点直到找到相似的节点。

但是这会涉及到从级别(比如 3025)爬升到 0，两次，以计算这一代，并且首先使用效率极低的爬升算法，并且然后重新爬上去。

还有其他更好的方法吗？

---

说明

按照这个系统的构建方式，每个 child 的数字都会比他们的 parent 多。

这不保证如果 n 在第 X 代中，则第 (X-1) 代中没有节点大于 n。例如:

        0       / \      /   \     /     \    1       2        6   / \     / \      / \  2   3   9  10    7   8     / \              / \    4   5            11 12

是一个有效的树系统。

此外，树构建方式的一个特点是同一父项的两个直接子项将始终连续编号。

Answer 1

节点是否像您的示例中那样有序，其中子节点的 ID 大于父节点？如果是这样，您也许可以执行类似于合并排序的操作来找到它们。对于您的示例，6 和 11 的父树是:

6  -> 2 -> 0
11 -> 7 -> 2 -> 0

所以算法可能是:

left = left_start
right = right_start

while left > 0 and right > 0
    if left = right
        return left
    else if left > right
        left = parent(left)
    else
        right = parent(right)

它将运行为:

left    right
----    -----
 6        11    (right -> 7)
 6        7     (right -> 2)
 6        2     (left -> 2)
 2        2     (return 2)

这是正确的吗？