Comment trouver l'ancêtre commun le plus bas de deux nœuds dans un arbre binaire ?

Question

L'arbre binaire n'est pas nécessairement un arbre de recherche binaire.
La structure peut être considérée comme -

struct node {
    int data;
    struct node *left;
    struct node *right;
};

La solution maximale que j'ai pu trouver avec un ami était de l'ordre de -
Considérer cet arbre binaire :

Le parcours dans l'ordre donne - 8, 4, 9, 2, 5, 1, 6, 3, 7

Et la traversée post-ordre donne - 8, 9, 4, 5, 2, 6, 7, 3, 1

Ainsi, par exemple, si nous voulons trouver l'ancêtre commun des nœuds 8 et 5, nous dressons une liste de tous les nœuds situés entre 8 et 5 dans l'ordre de parcours de l'arbre, qui, dans ce cas, est [4, 9, 2]. Ensuite, nous vérifions quel nœud de cette liste apparaît en dernier dans le parcours post-ordre, qui est 2. Par conséquent, l'ancêtre commun de 8 et 5 est 2.

La complexité de cet algorithme est, je crois, de O(n) (O(n) pour les traversées dans l'ordre/post-ordre, le reste des étapes étant à nouveau de O(n) puisqu'il ne s'agit que de simples itérations dans des tableaux). Mais il y a de fortes chances que ce soit faux :-)

Mais il s'agit d'une approche très rudimentaire, et je ne suis pas sûr qu'elle ne fonctionne pas dans certains cas. Existe-t-il une autre solution (éventuellement plus optimale) à ce problème ?

Answer 1

À partir de root et en se déplaçant vers le bas si l'on trouve un nœud qui possède l'une ou l'autre des caractéristiques suivantes p o q comme son enfant direct, il s'agit alors de l'ACL. (edit - ceci devrait être si p o q est la valeur du nœud, elle est renvoyée. Sinon, il échouera si l'un des éléments suivants p o q est un enfant direct de l'autre).

Sinon, si vous trouvez un nœud avec p dans son sous-arbre de droite (ou de gauche) et q dans son sous-arbre gauche (ou droit), il s'agit alors de l'ACL.

Le code fixé se présente comme suit :

treeNodePtr findLCA(treeNodePtr root, treeNodePtr p, treeNodePtr q) {

        // no root no LCA.
        if(!root) {
                return NULL;
        }

        // if either p or q is the root then root is LCA.
        if(root==p || root==q) {
                return root;
        } else {
                // get LCA of p and q in left subtree.
                treeNodePtr l=findLCA(root->left , p , q);

                // get LCA of p and q in right subtree.
                treeNodePtr r=findLCA(root->right , p, q);

                // if one of p or q is in leftsubtree and other is in right
                // then root it the LCA.
                if(l && r) {
                        return root;
                }
                // else if l is not null, l is LCA.
                else if(l) {
                        return l;
                } else {
                        return r;
                }
        }
}

Le code ci-dessous échoue si l'un des deux est l'enfant direct de l'autre.

treeNodePtr findLCA(treeNodePtr root, treeNodePtr p, treeNodePtr q) {

        // no root no LCA.
        if(!root) {
                return NULL;
        }

        // if either p or q is direct child of root then root is LCA.
        if(root->left==p || root->left==q || 
           root->right ==p || root->right ==q) {
                return root;
        } else {
                // get LCA of p and q in left subtree.
                treeNodePtr l=findLCA(root->left , p , q);

                // get LCA of p and q in right subtree.
                treeNodePtr r=findLCA(root->right , p, q);

                // if one of p or q is in leftsubtree and other is in right
                // then root it the LCA.
                if(l && r) {
                        return root;
                }
                // else if l is not null, l is LCA.
                else if(l) {
                        return l;
                } else {
                        return r;
                }
        }
}

Le code en action

Answer 2

Nick Johnson a raison de dire qu'un algorithme de complexité temporelle O(n) est le meilleur que l'on puisse faire si l'on n'a pas de pointeurs parents). Pour une version récursive simple de cet algorithme, voir le code dans Poste de Kinding qui s'exécute en O(n) temps.

Mais gardez à l'esprit que si vos nœuds ont des pointeurs de parent, un algorithme amélioré est possible. Pour les deux nœuds en question, construisez une liste contenant le chemin de la racine au nœud en commençant par le nœud et en insérant le parent à l'avant.

Ainsi, pour 8 dans votre exemple, vous obtenez (en montrant les étapes) : {4}, {2, 4}, {1, 2, 4}

Faites de même pour l'autre nœud en question, ce qui donne (étapes non indiquées) : {1, 2}

Comparez maintenant les deux listes que vous avez créées en recherchant le premier élément où les listes diffèrent, ou le dernier élément de l'une des listes, selon ce qui arrive en premier.

Cet algorithme nécessite un temps O(h) où h est la hauteur de l'arbre. Dans le pire des cas, O(h) équivaut à O(n), mais si l'arbre est équilibré, ce temps n'est que O(log(n)). Il nécessite également O(h) d'espace. Il existe une version améliorée qui n'utilise qu'un espace constant, dont le code est présenté dans le document Poste du CEGRD

---

Indépendamment de la manière dont l'arbre est construit, si cette opération doit être effectuée plusieurs fois sur l'arbre sans le modifier entre-temps, vous pouvez utiliser d'autres algorithmes qui nécessitent une préparation en temps O(n) [linéaire], mais la recherche d'une paire ne prend que O(1) [constant]. Pour des références à ces algorithmes, voir la page du problème du plus petit ancêtre commun sur Wikipedia (en anglais) . (Crédit à Jason pour avoir posté ce lien à l'origine)

Answer 3

Voici le code de travail en JAVA

public static Node LCA(Node root, Node a, Node b) {
   if (root == null) {
       return null;
   }

   // If the root is one of a or b, then it is the LCA
   if (root == a || root == b) {
       return root;
   }

   Node left = LCA(root.left, a, b);
   Node right = LCA(root.right, a, b);

   // If both nodes lie in left or right then their LCA is in left or right,
   // Otherwise root is their LCA
   if (left != null && right != null) {
      return root;
   }

   return (left != null) ? left : right; 
}

Answer 4

Les réponses données jusqu'à présent utilisent la récursivité ou stockent, par exemple, un chemin en mémoire.

Ces deux approches peuvent échouer si l'arbre est très profond.

Voici mon point de vue sur cette question. Lorsque nous vérifions la profondeur (distance par rapport à la racine) des deux nœuds, si elle est égale, nous pouvons en toute sécurité remonter des deux nœuds vers l'ancêtre commun. Si l'un des nœuds est plus profond, nous devons nous déplacer vers le haut à partir du nœud le plus profond tout en restant dans l'autre nœud.

Voici le code :

findLowestCommonAncestor(v,w):
  depth_vv = depth(v);
  depth_ww = depth(w);

  vv = v; 
  ww = w;

  while( depth_vv != depth_ww ) {
    if ( depth_vv > depth_ww ) {
      vv = parent(vv);
      depth_vv--;
    else {
      ww = parent(ww);
      depth_ww--;
    }
  }

  while( vv != ww ) {
    vv = parent(vv);
    ww = parent(ww);
  }

  return vv;    

La complexité temporelle de cet algorithme est la suivante O(n). La complexité en espace de cet algorithme est : O(1).

En ce qui concerne le calcul de la profondeur, nous pouvons d'abord rappeler la définition : Si v est Racine, profondeur(v) = 0 ; Sinon, profondeur(v) = profondeur(parent(v)) + 1. Nous pouvons calculer la profondeur comme suit :

depth(v):
  int d = 0;
  vv = v;
  while ( vv is not root ) {
    vv = parent(vv);
    d++;
  }
  return d;

Answer 5

Cela dépend de la structure de votre arbre binaire. Vous avez probablement un moyen de trouver le nœud feuille désiré en fonction de la racine de l'arbre - appliquez simplement cette méthode aux deux valeurs jusqu'à ce que les branches que vous choisissez divergent.

Si vous ne disposez pas d'un moyen de trouver la feuille souhaitée à partir de la racine, votre seule solution - tant pour le fonctionnement normal que pour trouver le dernier nœud commun - consiste à effectuer une recherche brute dans l'arbre.