¿Por qué la complejidad del espacio de este algoritmo es O (1)

Question

Hola a todos: leí el algoritmo siguiente para encontrar el ancestro común más bajo de los dos nodos en un árbol binario de búsqueda.

 /* A binary tree node has data, pointer to left child
   and a pointer to right child */
 struct node
 {
  int data;
  struct node* left;
  struct node* right;
 };

 struct node* newNode(int );

/* Function to find least comman ancestor of n1 and n2 */
int leastCommanAncestor(struct node* root, int n1, int n2)
{
 /* If we have reached a leaf node then LCA doesn't exist
 If root->data is equal to any of the inputs then input is
 not valid. For example 20, 22 in the given figure */
 if(root == NULL || root->data == n1 || root->data == n2)
 return -1;

 /* If any of the input nodes is child of the current node
 we have reached the LCA. For example, in the above figure
 if we want to calculate LCA of 12 and 14, recursion should
 terminate when we reach 8*/
 if((root->right != NULL) &&
  (root->right->data == n1 || root->right->data == n2))
  return root->data;
 if((root->left != NULL) &&
 (root->left->data == n1 || root->left->data == n2))
 return root->data;   

 if(root->data > n1 && root->data < n2)
   return root->data;
 if(root->data > n1 && root->data > n2)
  return leastCommanAncestor(root->left, n1, n2);
 if(root->data < n1 && root->data < n2)
  return leastCommanAncestor(root->right, n1, n2);
}    

Tenga en cuenta que la función anterior supone que n1 es menor que n2. Complejidad de tiempo: O (n) Espacio complejidad: O (1)

este algoritmo es recursivo, sé que cuando se invoca una llamada de función recursiva, los argumentos de la función y otros registros relacionados se empuja a la pila, por lo que se necesita espacio adicional, por otro lado, la profundidad recursiva está relacionado con el tamaño o la altura del árbol, por ejemplo N, ¿tiene más sentido para ser o (n)?

Gracias por las explicaciones aquí!

Answer 1

A pesar de que tiene razón al decir que esa implementación recursiva del algoritmo requiere O espacio (n) a causa del espacio de pila es necesario, que sólo utiliza la recursión de cola, lo que significa que puede ser reimplantado para uso O (1) espacio con un bucle :

int leastCommanAncestor(struct node* root, int n1, int n2)
    while (1)
    {
     /* If we have reached a leaf node then LCA doesn't exist
     If root->data is equal to any of the inputs then input is
     not valid. For example 20, 22 in the given figure */
     if(root == NULL || root->data == n1 || root->data == n2)
     return -1;

     /* If any of the input nodes is child of the current node
     we have reached the LCA. For example, in the above figure
     if we want to calculate LCA of 12 and 14, recursion should
     terminate when we reach 8*/
     if((root->right != NULL) &&
      (root->right->data == n1 || root->right->data == n2))
      return root->data;
     if((root->left != NULL) &&
     (root->left->data == n1 || root->left->data == n2))
     return root->data;   

     if(root->data > n1 && root->data < n2)
       return root->data;
     if(root->data > n1 && root->data > n2)
      root = root->left;
     else if(root->data < n1 && root->data < n2)
      root = root->right;
    }
}

(Tenga en cuenta que else tiene que ser añadido en mantener sin cambios la semántica.)

Answer 2

Este algoritmo implica la recursión de cola. En el contexto de su pregunta, el marco de pila de la persona que llama puede ser reutilizado por el destinatario de la llamada. En otras palabras, toda la secuencia anidada de invocaciones de función se va a hacer es pasar el resultado como una brigada de paquetes. En consecuencia, se requiere realmente sólo un marco de pila.

Para más lectura, ver cola de llamadas en la Wikipedia.