algorithm - 最低共同祖先

Question

我在给定完整二叉树中的两个节点(父 x 比子 2*x 和 2*x+1)寻找最低共同祖先的恒定时间实现。

我的问题是树中有大量节点和许多查询。是否有一种算法可以进行预处理，以便可以在恒定时间内回答查询。

我调查了 LCA using RMQ ，但我不能使用该技术，因为我不能为树中的这么多节点使用数组。

知道它是完整的二叉树并且节点之间的关系如上所示，有人能给我高效的算法实现来快速回答许多查询吗？

我所做的是从两个给定的节点开始，然后依次找到它们的父节点 (node/2) 并保留已访问节点的哈希列表。当我们到达一个已经在哈希列表中的节点时，该节点将是最低的共同祖先。

但是当有很多查询时，这个算法非常耗时，因为在最坏的情况下，我可能必须遍历 30(树的最大高度)的高度才能到达根(最坏的情况)。

Answer 1

如果用二进制表示两个索引，则可以分两步找到 LCA:

1. 右移较大的数字，直到前导 1 位在与另一个号码相同的地方。
2. 右移两个数字直到它们相同。

第一步可以通过获取数字的对数基数 2 并将较大的数字右移差值来完成:

if a>b:
    a = shift_right(a,log2(a)-log2(b))
else:
    b = shift_right(b,log2(b)-log2(a))

第二步可以通过对结果的两个数字进行异或并将结果的对数基数 2 右移(加 1)来完成:

if a==b:
    return a
else:
    return shift_right(a,log2(xor(a,b))+1)

Log base 2 可以在 O(log(word_size)) 时间内找到，所以只要您使用具有固定位数的整数索引，这实际上是常量。

有关计算对数基数 2 的快速方法的信息，请参阅此问题: Fast computing of log2 for 64-bit integers