¿Cómo encontrar el primer ancestro común de un nodo en un árbol binario?

Question

El siguiente es mi algoritmo para encontrar el primer ancestro común. Pero no sé cómo calcular la complejidad del tiempo, ¿alguien puede ayudar?

public Tree commonAncestor(Tree root, Tree p, Tree q) { 
    if (covers(root.left, p) && covers(root.left, q)) 
     return commonAncestor(root.left, p, q); 
    if (covers(root.right, p) && covers(root.right, q)) 
     return commonAncestor(root.right, p, q); 
    return root; 
} 
private boolean covers(Tree root, Tree p) { /* is p a child of root? */ 
    if (root == null) return false; 
    if (root == p) return true; 
    return covers(root.left, p) || covers(root.right, p); 
} 

Answer 1

Bien, empecemos por identificar cuál sería el peor caso para este algoritmo. covers busca en el árbol de izquierda a derecha, por lo que obtendrá el peor de los casos si el nodo que está buscando es el extremo derecho, o no está en el subárbol. En este punto, habrá visitado todos los nodos en el subárbol, por lo que covers es O (n), donde n es la cantidad de nodos en el árbol.

Del mismo modo, el comportamiento commonAncestor exposiciones peor de los casos, cuando el primer antepasado común de p y q es el fondo a la derecha en el árbol. En este caso, primero llamará al covers dos veces, obteniendo el peor comportamiento horario en ambos casos. Luego se volverá a llamar a sí mismo en el subárbol derecho, que en el caso de un árbol equilibrado es del tamaño n/2.

Suponiendo que el árbol está equilibrado, podemos describir el tiempo de ejecución por la relación de recurrencia T(n) = T(n/2) + O(n). Usando el teorema maestro, obtenemos la respuesta T(n) = O(n) para un árbol equilibrado.

Ahora, si el árbol es no equilibrada, que podría en el peor de los casos sólo reducen el tamaño del subárbol en 1 por cada llamada recursiva, produciendo la recurrencia T(n) = T(n-1) + O(n). La solución a esta recurrencia es T(n) = O(n^2).

Sin embargo, puede hacer algo mejor que esto.

Por ejemplo, en lugar de simplemente determinar qué subárbol contiene p o q con cover, vamos a determinar la ruta completa y pq. Esto lleva O(n) al igual que cover, solo estamos guardando más información. Ahora, recorra esos caminos en paralelo y deténgase donde divergen. Esto siempre es O(n).

Si tiene punteros de cada nodo a sus padres incluso se puede mejorar en esta generando el caminos "de abajo hacia arriba", dándole O(log n) para un árbol de equilibrado.

Tenga en cuenta que esta es una solución de compromiso espacio-tiempo, ya que mientras el código de toma O(1) espacio, este algoritmo toma O(log n) espacio para un árbol de equilibrado, y O(n) espacio en general.

Answer 2

Como hammar’s answer demuestra, su algoritmo es bastante ineficiente ya que muchas operaciones se repiten.

Me gustaría hacer un enfoque diferente: en lugar de probar para cada nodo raíz potencial si los dos nodos dados no están en el mismo subárbol (por lo que es el primer ancestro común) Determinaría las rutas desde la raíz a los dos nodos dados y compara los nodos. El último nodo común en las rutas desde la raíz hacia abajo es también el primer ancestro común.

Aquí es una implementación (no probado) en Java:

private List<Tree> pathToNode(Tree root, Tree node) { 
    List<Tree> path = new LinkedList<Tree>(), tmp; 

    // root is wanted node 
    if (root == node) return path; 

    // check if left child of root is wanted node 
    if (root.left == node) { 
     path.add(node); 
     path.add(root.left); 
     return path; 
    } 
    // check if right child of root is wanted node 
    if (root.right == node) { 
     path.add(node); 
     path.add(root.right); 
     return path; 
    } 

    // find path to node in left sub-tree 
    tmp = pathToNode(root.left, node); 
    if (tmp != null && tmp.size() > 1) { 
     // path to node found; add result of recursion to current path 
     path = tmp; 
     path.add(0, node); 
     return path; 
    } 
    // find path to node in right sub-tree 
    tmp = pathToNode(root.right, node); 
    if (tmp != null && tmp.size() > 1) { 
     // path to node found; add result of recursion to current path 
     path = tmp; 
     path.add(0, node); 
     return path; 
    } 
    return null; 
} 

public Tree commonAncestor(Tree root, Tree p, Tree q) { 
    List<Tree> pathToP = pathToNode(root, p), 
       pathToQ = pathToNode(root, q); 
    // check whether both paths exist 
    if (pathToP == null || pathToQ == null) return null; 
    // walk both paths in parallel until the nodes differ 
    while (iterP.hasNext() && iterQ.hasNext() && iterP.next() == iterQ.next()); 
    // return the previous matching node 
    return iterP.previous(); 
} 

Tanto pathToNode y commonAncestor son en O (n).