Plus petit ancêtre commun
🧓 Cet exercice utilise une modélisation d'arbre non ordonné, avec la liste des parents.
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 de l'arbre.
- 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. Cet ensemble est totalement ordonné par la relation de parenté. Il existe donc un unique 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\).
Exercice
Coder une fonction telle que plus_petit_ancêtre_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(6) --> N1(5)
R --> N2(12)
R --> N3(10)
N2 --> N4(4)
N2 --> N5(1)
N2 --> N6(0)
N5 --> N7(7)
N5 --> N8(3)
N6 --> N9(9)
N6 --> N10(8)
N9 --> N11(11)
N9 --> N12(2)>>> # Indices 0 1 2 3 4 5 6 7 8 9 10 11 12
>>> parents = [12, 12, 9, 1, 12, 6, None, 1, 0, 0, 6, 9, 6]
>>> plus_petit_ancêtre_commun(parents, 0, 11)
0
>>> plus_petit_ancêtre_commun(parents, 1, 10)
6
>>> plus_petit_ancêtre_commun(parents, 4, 2)
12
Indice
- On peut construire une pile avec les ancêtres de
noeud_a, une autre pile pour ceux denoeud_b. Ceci peut se faire via une fonction auxiliaire qui renvoie tous les ancêtres d'un nœud. - Le sommet de chaque pile sera commun : la racine de l'arbre.
- On peut les dépiler tant que le sommet est identique.
Guide
def plus_petit_ancêtre_commun(parents, noeud_a, noeud_b):
"Renvoie le ppac de `noeud_a` et `noeud_b` dans l'arbre défini avec `parents`"
def ancêtres(parents, noeud):
"Renvoie les ancêtres du `noeud` dans l'arbre défini par `parents`"
ancêtres_noeud = ...
[...]
return ancêtres_noeud
[...]
return ppac
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)