更本地化的，高效的最低公共祖先的算法给定的多个二叉树？ [英] More localized, efficient Lowest Common Ancestor algorithm given multiple binary trees?

问题描述

我有一个数组存储多个二进制树。在每个插槽或者是零（或空;选择你的语言）或固定元组存储两个数字：两个孩子的指标。任何节点都只有一个孩子 - 这是无或两个

I have multiple binary trees stored as an array. In each slot is either nil (or null; pick your language) or a fixed tuple storing two numbers: the indices of the two "children". No node will have only one child -- it's either none or two.

想每个插槽为二进制节点只存储指向它的孩子，并没有内在价值。

Think of each slot as a binary node that only stores pointers to its children, and no inherent value.

取二叉树的这个系统：

    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 ]

我已经写简单的功能来查找节点的直接父（只需从前面搜索，直到有一个包含子节点的节点）

I've already written simple functions to find direct parents of nodes (simply by searching from the front until there is a node that contains the child)

此外，我们可以说，在有关时期，既所有的树木是几个之间的任何地方到几千级。

Furthermore, let us say that at relevant times, both all trees are anywhere between a few to a few thousand levels deep.

我想找到一个函数

P(m,n)

要找到m和n最低的共同祖先 - 让更正式，LCA的定义为具有米最低，或最深的节点和n为后代（子女，或子女的子女，等）。如果没有，一个零将是一个有效的回报。

to find the lowest common ancestor of m and n -- to put more formally, the LCA is defined as the "lowest", or deepest node in which have m and n as descendants (children, or children of children, etc.). If there is none, a nil would be a valid return.

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

Some examples, given our given tree:

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

主要方法，我已经能够找到的是一个使用欧拉跟踪，果然给定的树（添加节点A为0无形的家长和1，着有价值-1），进

The main method I've been able to find is one that uses an Euler trace, which turns the given tree (Adding node A as the invisible parent of 0 and 1, with a "value" of -1), into:

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。

And from that, simply find the node between your given m and n that has the lowest number; For example, to find P(6,11), look for a 6 and an 11 on the trace. The number between them that is the lowest is 2, and that's your answer. If A (-1) is in between them, return 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的时候，我不得不重新计算欧拉跟踪并保持在内存中的每一次。

Unfortunately, I do believe that finding the Euler trace of a tree that can be several thousands of levels deep is a bit machine-taxing...and because my tree is constantly being changed throughout the course of the programming, every time I wanted to find the LCA, I'd have to re-calculate the Euler trace and hold it in memory every time.

有没有更多的内存有效的方式，因为我使用的框架？其中，也许迭代向上？我能想到的一个办法是计数两个节点的生成/深度，勇攀最低的节点，直到它符合最高的深度，并增加双方直到他们找到类似的人。

Is there a more memory efficient way, given the framework I'm using? One that maybe iterates upwards? One way I could think of would be the "count" the generation/depth of both nodes, and climb the lowest node until it matched the depth of the highest, and increment both until they find someone similar.

但是，这会涉及从水平，也就是说，3025爬上，回到0，两次的，要计算的产生，并在第一时间使用非常低效攀登行动的算法，和然后再爬回来了。

But that'd involve climbing up from level, say, 3025, back to 0, twice, to count the generation, and using a terribly inefficient climbing-up algorithm in the first place, and then re-climbing back up.

是否还有其他更好的办法？

Are there any other better ways?

在此系统的构建方式，每一个孩子会比他们的父母大的数字

In the way this system is built, every child will have a number greater than their parents.

这做的不可以的保证，如果n是代X，也有一代没有节点（X-1）是大于n。例如：

This does not guarantee that if n is in generation X, there are no nodes in generation (X-1) that are greater than n. For example:

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

是一个有效的树系统。

is a valid tree system.

另外，树的构建方式神器是同父的两个直接的孩子总是会连续编号。

Also, an artifact of the way the trees are built are that the two immediate children of the same parent will always be consecutively numbered.

推荐答案

是为了节点就像在你的例子，孩子们有一个更大的ID比亲？如果是的话，你也许可以做类似于合并排序有事找他们。对于你的榜样，6和11父树是：

Are the nodes in order like in your example where the children have a larger id than the parent? If so, you might be able to do something similar to a merge sort to find them.. for your example, the parent tree of 6 and 11 are:

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

因此​​，或许算法是：

So perhaps the algorithm would be:

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)

这将是运行：

Which would run as:

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

这是正确的？

Is this correct?

这篇关于更本地化的，高效的最低公共祖先的算法给定的多个二叉树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！