Gibt es eine bessere Art und Weise kleinste gemeinsame Vorfahren zu finden?

Question

Ich weiß, ähnliche Fragen haben, bevor gefragt worden, aber ich denke, dass meine Lösung ist viel einfacher. Vor allem im Vergleich zu Wikipedia .

Bitte beweisen mich nicht falsch!

Wenn Sie einen Baum mit Knoten, die die gegebenen Datenstruktur:

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

Sie können eine Funktion wie dieses schreiben:

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

Dieser Code ist ziemlich einfach und schlimmste Fall ist O (n), die durchschnittliche Fall ist es wahrscheinlich O (log n), vor allem, wenn der Baum ausgeglichen ist (wobei n die Anzahl der Knoten im Baum).

Answer 1

Ihr Algorithmus sieht für mich in Ordnung, zumindest konnte ich nicht besser an nichts denken. Beachten Sie, dass Sie den übergeordneten Zeiger nicht brauchen; stattdessen können Sie den Baum ausgehend von der Wurzel nach unten gehen, und finden Sie den ersten Knoten, dessen Schlüssel liegt zwischen den beiden Anfangs Tasten.

Allerdings Ihr Problem hat nichts mit den einem Tarjan gelöst zu tun. Zunächst einmal betrachten Sie Binärbäumen und er hält n-äre Bäume; aber das ist wahrscheinlich ein Detail. Noch wichtiger ist, sollten Sie suchen Bäume, während Tarjan allgemeine Bäume (auf den Tasten keine Reihenfolge) hält. Ihr Problem ist viel einfacher, denn je nach dem Schlüssel, können Sie erraten, wo ein bestimmte Knoten im Baum sein.

Answer 2

Nein, tut mir leid. Aber Ihr Algorithmus ist nicht gut. nehmen Sie die folgenden BST:

10
  \
   \
   15
  /  \
 14  16

you'r Algorithmus kehrt 10 als die kleinsten gemeinsamen Vorfahren.

So könnte man Algorithmus schreiben, dass nehmen, sagen wir, der linke Knoten und als unterwegs zu seinen Eltern und laufen auf es in Ordnung, und dass geprüft, ob direkt im Ausgang der in Ordnung war

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


}