最低的共同祖先

Question

我要寻找一个在满二叉树一定的时间实现最低的共同祖先给出了两个节点(父X小于子2*x和2*X + 1).

我的问题是树中有大量节点和许多查询.是否有一个算法,它预处理,以便可以在恒定的时间内回答查询.

我使用RMQ查看了LCA,但我不能使用该技术,因为我不能在树中使用这个节点的数组.

有人可以给我快速回答许多查询的算法的有效实现,知道它是完整的二叉树,并且节点之间的关系如上所述.

我所做的是从两个给定节点开始,并连续找到它们的父节点(节点/ 2)保持被访问节点的哈希列表.当我们到达已经在哈希列表中的节点时,该节点将是最低的共同祖先.

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

Answer 1

如果用二进制表示两个索引,则可以通过两个步骤找到LCA:

第一步可以通过获取数字的基数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)

日志库2可以在O(log(word_size))时间内找到,因此只要您使用具有固定位数的整数索引,这实际上是常量.

有关计算日志基础的快速方法的信息,请参阅此问题2: 快速计算64位整数的log2