algorithm - Ancestro común más bajo

optimization tree

Question

Estoy buscando la implementación constante del ancestro común más bajo dado dos nodos en el árbol binario completo (padre x que niño 2 * x y 2 * x + 1).

Mi problema es que hay una gran cantidad de nodos en el árbol y muchas consultas. ¿Hay algún algoritmo que preproceses para que las consultas puedan responderse en tiempo constante?

Miré en LCA usando RMQ , pero no puedo usar esa técnica ya que no puedo usar una matriz para estos muchos nodos en el árbol.

¿Puede alguien darme una implementación eficiente del algoritmo para responder muchas consultas rápidamente, sabiendo que es un árbol binario completo y la relación entre los nodos es como la dada anteriormente?

Lo que hice fue comenzar con dos nodos dados y sucesivamente encontrar a sus padres (nodo / 2) mantener la lista hash de los nodos visitados. cada vez que llegamos a un nodo que ya está en la lista hash, entonces ese nodo sería el ancestro común más bajo.

Pero cuando hay muchas consultas, este algoritmo consume mucho tiempo, ya que en el peor de los casos tendré que atravesar una altura de 30 (altura máxima del árbol) para llegar a la raíz (el peor de los casos).

Answer 1

Editar: -

Forma más rápida de obtener el common_ancestor en 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;  

}

Explicación:

1. Obtiene los bits necesarios para representar xey, que usando la búsqueda binaria es O (log (32))
2. el prefijo común de la notación binaria de x y y es el ancestro común
3. lo que esté representado por un mayor número de bits se lleva al mismo bit por k >> diff
4. k = x ^ y borra el prefijo común de x & y
5. encontrar bits que representan el sufijo restante
6. desplaza x o y por los bits de sufijo para obtener el prefijo común que es el ancestro común.

Ejemplo: -

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

Answer 2

Si representa los dos índices en binario, entonces el LCA se puede encontrar en dos pasos:

1. Desplaza a la derecha el número más grande hasta que el primer bit esté en el mismo lugar que el otro número.
2. Cambia ambos números a la derecha hasta que sean iguales.

El primer paso se puede hacer obteniendo la base de registro 2 de los números y cambiando el número más grande por la diferencia:

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

El segundo paso puede realizarse haciendo una XOR de los dos números resultantes y desplazándolos a la derecha por la base de registro 2 del resultado (más 1):

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

La base de registro 2 se puede encontrar en el tiempo O (log (word_size)), por lo que siempre que use índices enteros con un número fijo de bits, esta será efectivamente constante.

Consulte esta pregunta para obtener información sobre formas rápidas de calcular la base de registro 2: Computación rápida de log2 para enteros de 64 bits