最低的共同祖先-Java 学习之路

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

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

我查看了LCA using RMQ，但是我可以在树中使用数组来处理这么多节点 .

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

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

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

2 回答

Edit :-

Faster way to get the common_ancestor in O(log(logn)) :-

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;  

}

Explanation :-

获取表示x和y所需的位，其中使用二进制搜索是O（log（32））x和y的二进制表示法的公共前缀是共同的祖先，无论哪个由更大的位表示由k带到相同的位>> diff k = x ^ y擦除x和y的公共前缀，通过后缀位找到表示剩余后缀shift x或y的位，以获得作为共同祖先的公共前缀 .

Example :-

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

回复于 2024-04-19T19:01:28+08:00

2
如果用二进制表示两个索引，则可以通过两个步骤找到LCA：
- 向右移动较大的数字，直到前导1位与另一个数字位于同一位置 .
- 向右移两个数字直到它们相同 .
第一步可以通过获取数字的基数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的快速方法的信息，请参阅此问题：Fast computing of log2 for 64-bit integers
回复于 2024-04-19T19:01:28+08:00

最低的共同祖先

2 回答

相关问题