Existe uma maneira melhor de encontrar o ancestral comum mais baixo?

Question

Sei que perguntas semelhantes já foram feitas antes, mas acho que minha solução é muito mais simples. Especialmente comparado a Wikipedia.

Por favor, prove que estou errado!

Se você tem uma árvore com nós que possuem a estrutura de dados fornecida:

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

Você pode escrever uma função 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;
}

Esse código é bastante direto e o pior caso é O (n), caso médio provavelmente é O (logn), especialmente se a árvore estiver equilibrada (onde n é o número de nós na árvore).

Answer 1

Seu algoritmo parece bom para mim, pelo menos eu não conseguia pensar em nada melhor. Observe que você não precisa do ponteiro pai; Em vez disso, você pode descer a árvore a partir da raiz e encontrar o primeiro nó cuja chave está entre as duas teclas iniciais.

No entanto, seu problema não tem nada a ver com o único Tarjan resolvido. Primeiro de tudo, você considera árvores binárias e ele considera árvores n-ary; Mas isso provavelmente é um detalhe. Mais importante, você considera árvores de pesquisa, enquanto Tarjan considera árvores em geral (sem pedidos nas chaves). Seu problema é muito mais simples, porque, dependendo da chave, você pode adivinhar onde um certo nó deve estar na árvore.

Answer 2

Não, eu sinto muito. Mas seu algoritmo não é bom. Pegue o seguinte BST:

10
  \
   \
   15
  /  \
 14  16

Seu algoritmo retornará 10 como o ancestral comum mais baixo.

Assim, você pode escrever algoritmo que toma, digamos, o nó esquerdo e depois ir para seus pais e correr em ordem nele e que verifique se a direita estava na saída da ordem

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


}