Plus petit ancêtre commun⚓︎
Dans cet exercice on considère une structure arborescente : un arbre (ici non ordonné) de taille \(n\) dont les nœuds sont étiquetés avec les entiers de \(0\) à \(n-1\). Les étiquettes sont des identifiants uniques des nœuds.
Arbre enraciné non ordonné
Il existe plusieurs définitions équivalentes. En voici une :
Un arbre enraciné non ordonné est un ensemble non vide de nœuds tel que :
- Un nœud particulier est nommé racine de l'arbre.
- Chaque nœud, sauf la racine, possède un unique nœud parent.
- Par cheminements successifs d'un nœud vers son parent, on arrive à la racine de l'arbre.
Le qualificatif « non ordonné » indique qu'il n'y a pas d'ordre pour les sous-arbres. Les deux représentations ci-dessous représentent donc le même arbre non ordonné.
graph TD
R(0) --> N1(1)
R --> N2(2)
R --> N3(3)
N2 --> N4(5)
N2 --> N5(4)
R2(0) --> M1(1)
R2 --> M2(3)
R2 --> M3(2)
M3 --> M4(4)
M3 --> M5(5)La liste des parents (voir ci-dessous) est ici
[None, 0, 0, 0, 2, 2]
Liste des parents
Si l'arbre est de taille \(n\), et que les étiquettes sont les entiers de \(0\) à \(n-1\), on peut donner la liste des étiquettes des parents des nœuds de l'arbre, à l'exception de la racine qui n'a pas de parent.
Par exemple avec
# indices 0 1 2 3 4
parents = [3, 4, 4, None, 3]
- le parent de \(0\) est \(3\)
- le parent de \(1\) est \(4\)
- le parent de \(2\) est \(4\)
- \(3\) n'a pas de parent
- le parent de \(4\) est \(3\)
Ce qui donne l'arbre ci-dessous :
graph TD
R(3) --> N1(4)
R --> N2(0)
N1 --> N3(2)
N1 --> N5(1)Un arbre non ordonné est entièrement défini par la liste des parents des nœuds.
Ancêtres d'un nœud
On définit les ancêtres d'un nœud \(N\) comme l'ensemble des nœuds rencontrés depuis le nœud \(N\) jusqu'à la racine en allant successivement de parent en parent.
- Un nœud est ancêtre de lui-même.
- La racine est un ancêtre de tout nœud.
- Les ancêtres d'un nœud \(N\) sont ordonnés du plus petit, le nœud \(N\), au plus grand, la racine.
Plus petit ancêtre commun à deux nœuds
Deux nœuds \(N_1\) et \(N_2\) étant donnés, on considère l'ensemble des ancêtres communs à \(N_1\) et \(N_2\). Cet ensemble est non vide ; la racine étant un ancêtre commun. Il existe un nœud \(N_0\), le plus petit parmi les ancêtres communs à \(N_1\) et \(N_2\), on l'appelle le plus petit ancêtre commun à \(N_1\) et \(N_2\).
Écrire une fonction telle que plus_petit_ancetre_commun(parents, noeud_a, noeud_b) renvoie le plus petit ancêtre commun à noeud_a et noeud_b dans l'arbre non ordonné décrit par sa liste des parents.
Exemples
graph TD
R(0) --> N1(1)
R --> N2(2)
R --> N3(3)
N2 --> N4(4)
N2 --> N5(5)
N2 --> N6(6)
N5 --> N7(7)
N5 --> N8(8)
N6 --> N9(9)
N6 --> N10(10)
N9 --> N11(11)
N9 --> N12(12)>>> parents = [None, 0, 0, 0, 2, 2, 2, 5, 5, 6, 6, 9, 9]
>>> plus_petit_ancetre_commun(parents, 8, 11)
2
>>> plus_petit_ancetre_commun(parents, 1, 10)
0
>>> plus_petit_ancetre_commun(parents, 12, 6)
6
def pluspy-undpetitpy-undancetrepy-undcommun(parents, noeudpy-unda, noeudpy-undb):bksl-nl ...bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlparents = [None, 0, 0, 0, 2, 2, 2, 5, 5, 6, 6, 9, 9]bksl-nlassert pluspy-undpetitpy-undancetrepy-undcommun(parents, 8, 11) == 2bksl-nlassert pluspy-undpetitpy-undancetrepy-undcommun(parents, 1, 10) == 0bksl-nlassert pluspy-undpetitpy-undancetrepy-undcommun(parents, 12, 6) == 6bksl-nlbksl-nldef ancetres(parents, noeud):bksl-nl ancetrespy-undnoeud = [noeud]bksl-nl while noeud is not None:bksl-nl noeud = parents[noeud]bksl-nl ancetrespy-undnoeud.append(noeud)bksl-nl return ancetrespy-undnoeudbksl-nlbksl-nlbksl-nldef pluspy-undpetitpy-undancetrepy-undcommun(parents, noeudpy-unda, noeudpy-undb):bksl-nl ancetrespy-unda = ancetres(parents, noeudpy-unda)bksl-nl ancetrespy-undb = ancetres(parents, noeudpy-undb)bksl-nlbksl-nl while (bksl-nl (ancetrespy-unda != []) and (ancetrespy-undb != []) and (ancetrespy-unda[-1] == ancetrespy-undb[-1])bksl-nl ):bksl-nl ppac = ancetrespy-unda.pop()bksl-nl ancetrespy-undb.pop()bksl-nl return ppacbksl-nlbksl-nl
A
Z
Indice 1
On peut construire une pile avec les ancêtres de noeud_a, une autre pile pour ceux de noeud_b. Ceci peut se faire via une fonction qui renvoie les ancêtres d'un nœud.
Indice 2
Le sommet de chaque pile sera commun : la racine de l'arbre.
Indice 3
On peut les dépiler tant que le sommet est identique.