最近公共祖先

Question

我正在寻找在完全二叉树中给定两个节点的最近公共祖先的常数时间实现（父节点为x，子节点为2*x和2*x+1）。

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

我研究了LCA using RMQ，但由于无法在这么多节点的树中使用数组，因此无法使用该技术。

有人能为我提供高效的算法实现，以便快速回答许多查询，知道它是完全二叉树，并且节点之间的关系如上所述。

我的方法是从两个给定节点开始，连续查找它们的父节点（node/2），并保留已访问节点的哈希列表。每当我们到达已经在哈希列表中的节点时，该节点将成为最近公共祖先。

但是当有很多查询时，这个算法非常耗时，最坏情况下可能需要遍历高度为30（树的最大高度）才能到达根节点（最坏情况）。

- coder hacker

---

请澄清树是如何表示的：听起来像是存储在数组中，其中索引为X的节点的子节点位于2X和2X+1的位置。 - Scott Hunter

@ScottHunter 他说那不是一个数组。 - ElmoVanKielmo

不需要存储树，因为节点按顺序编号，我们可以通过2x和2x+1获取子节点。 - coder hacker

因此，节点的编号就好像它们存储在数组中一样。 - Scott Hunter

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))

第二步可以通过对两个结果数字进行异或并将结果向右移动log2（结果加1）来完成：

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

以 2 为底的对数可以在 O(log(word_size)) 的时间内找到，所以只要使用固定位数的整数索引，这就等效于常数。

有关快速计算以 2 为底的对数的信息，请参见此问题： 64 位整数的对数运算的快速计算

- Vaughn Cato

---

我知道会有这样的东西，非常不错。 - Scott Hunter

这仍然是O(树的高度)，而不是常数。虽然它应该比遍历节点更快。唯一能被认为是常数的方式是，如果有某种神奇的方法可以在单个机器指令中获得以2为底的对数，而不考虑O(位数)操作。 - user2566092

@user2566092：是的，也许它在技术上并不是恒定时间，但是log base 2可以在log(log(n))时间内找到，并且对于任何特定的字长，这都是一个常数。 - Vaughn Cato

我正准备添加一个答案，解释如何在log（位数）操作中获得整数log base2。你可能想把它加入到你的答案中。 - user2566092

@VaughnCato 是的，伪代码非常有帮助，谢谢。 - coder hacker

Answer 2

编辑：

使用O(log(logn))更快地获取common_ancestor的方法：

int get_bits(unsigned int x) {
  int high = 31;
  int low = 0,mid;
  while(high>=low) {
    mid = (high+low)/2;
    if(1<<mid==x)
      return mid+1;
    if(1<<mid<x) {
      low = mid+1;
    }
    else {
      high = mid-1;
    }
  }
  if(1<<mid>x)
    return mid;
  return mid+1;
}

unsigned int Common_Ancestor(unsigned int x,unsigned int y) {

  int xbits = get_bits(x);
  int ybits = get_bits(y);
  int diff,kbits;
  unsigned int k;
  if(xbits>ybits) {
    diff = xbits-ybits;
    x = x >> diff;
  }
  else if(xbits<ybits) {
    diff = ybits-xbits;
    y = y >> diff;
  }
  k = x^y;
  kbits = get_bits(k);
  return y>>kbits;  

}

解释：

1. 使用二分查找获取表示 x 和 y 所需的位数，时间复杂度为 O(log(32))。
2. x 和 y 的二进制表示的公共前缀即为它们的公共祖先。
3. 将较多位数的值通过 k >> diff 移动到相同的位数上。
4. k = x^y 消除 x 和 y 的公共前缀。
5. 找到表示剩余后缀的位数。
6. 通过后缀位数向左移动 x 或 y 来获取公共前缀，这是它们的公共祖先。

示例：

x = 12 = b1100 
y = 8  = b1000

xbits = 4
ybits = 4
diff = 0
k = x^y = 4 = b0100
kbits = 3
res = x >> kbits = x >> 3 = 1

ans : 1

- Vikram Bhat

---

我尝试了相同的事情，但如果根是共同祖先，那么会花费很长时间。 - coder hacker

是的，这是完美的方法，但是上面的问题中已经给出了相同的解决方案。谢谢，你的解释更好，所以我接受了你的答案。 - coder hacker

@TejasPatel 没有注意到 :) - Vikram Bhat

太棒了！非常好！ - otaku