Plus ancien ancêtre commun de l’arbre binary (arbre de recherche non binary)

L’algorithme LCA essaie de faire une chose simple: Déterminez les chemins des deux nœuds en question à la racine. Maintenant, ces deux chemins auront un suffixe commun (en supposant que le chemin se termine à la racine). Le LCA est le premier noeud où commence le suffixe.

Considérez l’arbre suivant:

r * / \ s * * / \ u * * t / / \ * v * * / \ * * 

Pour trouver l’ACV (u, v), procédez comme suit:

• Chemin de u à la racine: Chemin (u, r) = usr
• Chemin de v à la racine: Chemin (v, r) = vtsr

Maintenant, nous vérifions le suffixe commun:

• Suffixe commun: ‘sr’
• Donc LCA (u, v) = premier noeud du suffixe = s

Notez que les algorithmes réels ne vont pas jusqu’à la racine. Ils utilisent des structures de données Disjoint-Set pour s’arrêter quand ils atteignent s.

Un excellent ensemble d’approches alternatives est expliqué ici .

Puisque vous avez parlé des entretiens d’embauche, j’ai pensé à la variation de ce problème où vous êtes limité à l’utilisation de la mémoire O (1).

Dans ce cas, considérez l’algorithme suivant:

1) Parcourez l’arbre du nœud u jusqu’à la racine, en recherchant la longueur du chemin L (u)

2) Parcourez l’arborescence du nœud v à la racine, en recherchant la longueur du chemin L (v)

3) Calculez la différence de longueur du trajet D = | L (u) -L (v) |

4) Ignorer les nœuds D dans le chemin le plus long à partir de la racine

5) Montez l’arbre en parallèle à partir des deux nœuds, jusqu’à atteindre le même nœud

6) Renvoyer ce noeud en tant que LCA

En supposant que vous n’ayez besoin de résoudre le problème qu’une seule fois (par dataset), une approche simple consiste à collecter l’ensemble des ancêtres d’un noeud (avec lui-même), puis à parcourir la liste des ancêtres de l’autre jusqu’à ce que vous trouviez un membre de l’ensemble ci-dessus, qui est nécessairement l’ancêtre commun le plus bas. Un pseudocode pour cela est donné:

 Let A and B begin as the nodes in question. seen := set containing the root node while A is not root: add A to seen A := A's parent while B is not in seen: B := B's parent B is now the lowest common ancestor. 

Une autre méthode consiste à calculer l’intégralité du chemin d’access à la pièce pour chaque nœud, puis à scanner de la droite à la recherche d’un suffixe commun. Son premier élément est la LCA. Lequel de ces parameters est le plus rapide dépend de vos données.

Si vous avez besoin de trouver des LCA pour plusieurs paires de nœuds, vous pouvez faire différents compromis entre espace et temps:

Vous pouvez, par exemple, pré-calculer la profondeur de chaque nœud, ce qui vous permettrait d’éviter de recréer chaque fois les ensembles (ou chemins) en marchant d’abord du nœud le plus profond à la profondeur du nœud le moins profond, puis en marchant. les deux nœuds vers la racine en phase verrouillée: lorsque ces chemins se rencontrent, vous obtenez le LCA.

Une autre approche consiste à annoter les nœuds avec leur ancêtre suivant profondeur-mod-H, de sorte que vous résolviez d’abord un problème semblable mais inférieur à H fois, puis à une instance de taille H du premier problème. Cela convient aux arbres très profonds et H est généralement choisi comme racine carrée de la profondeur moyenne de l’arbre.