C'è un modo migliore per trovare più basso antenato comune?

Question

Lo so domande simili sono stati chiesto prima, ma credo che la mia soluzione è molto più semplice. Soprattutto rispetto ai Wikipedia .

Si prega di dimostrare il torto!

Se si dispone di un albero con i nodi che hanno la data struttura dei dati:

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

Si potrebbe scrivere una funzione come questa:

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;
}

Questo codice è piuttosto semplice e caso peggiore è O (n), caso medio è probabilmente O (log n), in particolare se l'albero è bilanciato (dove n è il numero di nodi dell'albero).

Answer 1

Il vostro algoritmo guarda bene a me, almeno io non riuscivo a pensare a niente di meglio. Si noti che non è necessario il puntatore genitore; invece si può andare verso il basso l'albero a partire dalla radice, e trovare il primo nodo la cui chiave stabilisce tra le due chiavi iniziali.

Tuttavia, il problema non ha nulla a che fare con quello Tarjan risolto. Prima di tutto, si considera alberi binari e considera alberi n-ari; ma questo è probabilmente un dettaglio. Ancora più importante, si considera alberi di ricerca, mentre Tarjan considera alberi generali (nessun ordinamento sui tasti). Il tuo problema è molto più semplice, in quanto, a seconda del tasto, è possibile indovinare dove un certo nodo deve essere nella struttura.

Answer 2

No, mi dispiace. Ma l'algoritmo non è buona. prendere il seguente BST:

10
  \
   \
   15
  /  \
 14  16

you'r algoritmo restituirà 10 come la più bassa antenato comune.

In questo modo, si potrebbe scrivere un algoritmo che prendono, per esempio, il nodo di sinistra e che andare al suo genitore e correre in-order su di esso e che controllo se proprio era in uscita della a-ordine

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


}