Existe-t-il un meilleur moyen de trouver le plus bas ancêtre commun?

Question

Je sais que des questions similaires ont déjà été posées, mais je pense que ma solution est beaucoup plus simple. Surtout par rapport à Wikipedia.

S'il vous plaît me prouver le contraire!

Si vous avez un arbre avec des nœuds qui ont la structure de données donnée:

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

Vous pouvez écrire une fonction comme ceci:

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

Ce code est assez simple et le pire des cas est O (n), cas moyen c'est probablement O (logn), surtout si l'arbre est équilibré (où n est le nombre de nœuds dans l'arbre).

Answer 1

Votre algorithme me semble correct, au moins je ne pouvais pas penser à quelque chose de mieux. Notez que vous n'avez pas besoin du pointeur parent; à la place, vous pouvez descendre dans l'arborescence à partir de la racine et trouver le premier nœud dont la clé se trouve entre les deux clés initiales.

Cependant, votre problème n'a rien à voir avec celui résolu par Tarjan. Tout d'abord, vous considérez les arbres binaires et il considère les arbres n-aires; mais c'est probablement un détail. Plus important encore, vous considérez les arbres de recherche, alors que Tarjan considère les arbres généraux (pas d'ordre sur les clés). Votre problème est beaucoup plus simple, car, selon la clé, vous pouvez deviner où un certain nœud doit être dans l'arbre.

Answer 2

Non, je suis désolé. Mais votre algorithme n'est pas bon. prendre la BST suivante:

 
10 
    \ 
    \ 
    15 
/\ 
14 16 

you'r algorithme retour 10 comme ancêtre commun le plus bas.

Ainsi, vous pouvez écrire algorithme prendre, par exemple, le nœud gauche et que d'aller à son parent et d'exécuter dans l'ordre sur elle et vérifier si le droit était dans la sortie du en ordre

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 


}