¿Hay una mejor manera de encontrar ancestro común más bajo?

Question

Yo sé preguntas similares se han preguntado antes, pero creo que mi solución es mucho más sencilla. Especialmente en comparación con Wikipedia .

Por favor, demostrar que estoy equivocado!

Si usted tiene un árbol con nodos que tienen la estructura de datos dado:

struct node
{
    node * left;
    node * right;
    node * parent;
    int key;
}

Se puede escribir una función como esta:

node* LCA(node* m, node* n)
{
    // determine which of the nodes is the leftmost
    node* left = null;
    node* right = null;
    if (m->key < n->key)
    {
        left = m;
        right = n;
    }
    else
    {
        left = n;
        right = m;
    }
    // start at the leftmost of the two nodes,
    // keep moving up the tree until the parent is greater than the right key
    while (left->parent && left->parent->key < right->key)
    {
        left = left->parent;
    }
    return left;
}

Este código es bastante sencillo y el peor caso es O (n), caso promedio es probable que sea O (log n), sobre todo si se equilibra el árbol (donde n es el número de nodos en el árbol).

Answer 1

Su algoritmo se ve bien para mí, al menos yo no podía pensar en nada mejor. Tenga en cuenta que no es necesario el puntero de los padres; en su lugar se puede bajar el árbol a partir de la raíz, y encontrar el primer nodo cuya clave se establecen entre las dos claves iniciales.

Sin embargo, el problema no tiene nada que ver con el Tarjan resuelto. En primer lugar, se tiene en cuenta los árboles binarios y considera árboles n-arias; pero esto es probablemente un detalle. Más importante aún, se tiene en cuenta los árboles de búsqueda, mientras que Tarjan considera árboles generales (hay un orden en las teclas). Su problema es mucho más simple, ya que, dependiendo de la tecla, se puede adivinar que un cierto nodo tiene que estar en el árbol.

Answer 2

No, lo siento. Sin embargo, su algoritmo no es buena. tomar la siguiente BST:

10
  \
   \
   15
  /  \
 14  16

you'r algoritmo devolverá 10 como el ancestro común más bajo.

Por lo tanto, se podría escribir algoritmo que toma, por ejemplo, el nodo de izquierda y de ir a su matriz y se ejecutan en orden en él y que cheque si la derecha se encontraba en la salida de la orden en

Answer 3

Node* getAncestor( Node* root, Node* node1 , Node* node2 )
{
    if( root->val > node1->val && root->val > node2->val )
        getAncestor( root->left , node1 , node2 );
    //recursive call with left subtree

    if( root->val < node1->val && root->val < node2->val )
        getAncestor( root->right , node1 , node2 );
    //recursive call with right subtree

    return root ;
    //returning the root node as ancestor

    //initial call is made with the tree's root node
    //node1 and node2 are nodes whose ancestor is to be located


}