X Informatique MP 2010

Thème de l'épreuve Plus proche ancêtre commun
Principaux outils utilisés arbres, récursivité, opérations logiques bit à bit
Mots clefs plus proche ancêtre commun, arbre, logique binaire

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                       

Rapport du jury

(télécharger le PDF)
           

Énoncé obtenu par reconnaissance optique des caractères


MP

ÉCOLE POLYTECHNIQUE

FILIÈRE
OPTION INFORMATIQUE

CONCOURS D'ADMISSION 2010

COMPOSITION D'INFORMATIQUE
(Durée : 4 heures)
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête 
de la copie.

Plus proche ancêtre commun
Ce problème s'intéresse à la question suivante : étant donné un arbre et deux 
noeuds dans
cet arbre, quel est le plus proche ancêtre commun de ces deux noeuds ? Une 
solution efficace à ce
problème a de nombreuses applications, notamment en bio-informatique. Ainsi, 
dans l'arbre
0
1
2

4
3

5

(1)

6

7
8

9

le plus proche ancêtre commun des noeuds 5 et 8 est le noeud 4, et celui des 
noeuds 3 et 7 est la
racine 0. De manière générale, on se donne un arbre quelconque, sur lequel on 
s'autorise un prétraitement, puis on souhaite calculer le plus efficacement 
possible le plus proche ancêtre commun
pour des couples de noeuds dans cet arbre.
Les arbres que l'on considère ici ont des noeuds étiquetés par des entiers 
distincts. Chaque
noeud a un nombre fini de descendants immédiats, appelés ses fils. Un noeud 
sans descendant est
appelé une feuille. Dans l'exemple ci-dessus, le noeud 4 a trois fils, à savoir 
5, 6 et 7, et les feuilles
sont 2, 3, 5, 6, 8 et 9. Le sous-arbre du noeud i est défini récursivement de 
la manière suivante :
c'est l'ensemble de noeuds contenant i et l'union de tous les sous-arbres des 
fils de i. On écrira
simplement « sous-arbre i » pour désigner le sous-arbre du noeud i. Si un noeud 
j appartient
au sous-arbre i, on dit que i est un ancêtre de j. En particulier, chaque noeud 
est son propre
ancêtre.
Le plus proche ancêtre commun de deux noeuds i et j, noté PPAC(i, j), est 
défini formellement
de la manière suivante :
­ si i est un ancêtre de j, alors PPAC(i, j) = i ;
­ symétriquement, si j est un ancêtre de i, alors PPAC(i, j) = j ;
­ sinon, PPAC(i, j) est l'unique noeud a possédant au moins deux fils distincts 
f1 et f2 tels
que i appartient au sous-arbre f1 et j au sous-arbre f2 .
1

Les arbres seront représentés en Caml et en Pascal de la manière suivante :
(* Caml *)
type arbre =
| Noeud of
int * arbre list ; ;

{ Pascal }
type arbre = ^noeud ;
liste_arbre = ^element ;
noeud = record n :integer ; l :liste_arbre ; end ;
element = record a :arbre ; r :liste_arbre ; end ;

Dans l'ensemble de ce problème, on se fixe une constante entière n, avec n  1, 
et un arbre A
contenant n noeuds numérotés de 0 à n - 1. On suppose en outre que cette 
numérotation vérifie
la propriété suivante :
Pour tout i, les noeuds du sous-arbre i portent des numéros consécutifs à 
partir de i.

(P)

On note que la racine de A est donc nécessairement le noeud 0.
La partie I propose une solution simple mais inefficace pour le problème du 
plus proche
ancêtre commun. La partie II propose ensuite une solution plus efficace, avec 
un pré-traitement
en O(n log n) et une réponse en temps constant. Les parties III et IV étudient 
le cas particulier
des arbres binaires complets. Enfin, la partie V étudie une application du 
calcul du plus proche
ancêtre commun.
Les parties peuvent être traitées indépendamment. Mais attention, chaque partie 
utilise des
notations et des fonctions introduites dans les parties précédentes. Les 
tableaux sont indexés à
partir de 0 et la notation t[i] est utilisée dans les questions pour désigner 
l'élément d'indice i
du tableau t, indépendamment du langage de programmation choisi. On appelle 
segment et on
note t[i..j] le sous-tableau du tableau t défini en considérant les indices 
compris entre i et j au
sens large.
I. Une solution simple
Dans cette partie, on considère une solution simple qui calcule le plus proche 
ancêtre commun
en temps O(n).
Question 1 On suppose avoir déclaré un tableau global taille de taille n. 
Écrire une procédure
remplir_taille qui stocke dans taille[i] le nombre de noeuds du sous-arbre i, 
pour tout i entre
0 et n - 1. On garantira une complexité O(n).
(* Caml *) remplir_taille : unit -> unit
{ Pascal } procedure remplir_taille ;
Par la suite, on suppose avoir appelé cette procédure.
Question 2 Écrire une fonction appartient qui prend en arguments deux noeuds i 
et j et
détermine, en temps constant, si i appartient au sous-arbre j.
(* Caml *) appartient : int -> int -> bool
{ Pascal } function appartient(i : integer ; j : integer) : boolean ;
2

Question 3 Écrire une fonction ppac1 qui prend en arguments deux noeuds i et j 
et détermine
PPAC(i, j) en temps O(n).
(* Caml *) ppac1 : int -> int -> int
{ Pascal } function ppac1(i : integer ; j : integer) : integer ;

II. Une solution plus efficace
Dans cette partie, on va effectuer un pré-traitement de l'arbre A qui permettra 
de déterminer
ensuite en temps constant le plus proche ancêtre commun pour tout couple de 
noeuds.
On commence par construire une séquence de noeuds en effectuant un tour 
Eulérien de
l'arbre A à partir de sa racine. D'une manière générale, le tour Eulérien à 
partir du noeud i est
défini comme agissant sur une séquence résultat, construite de la manière 
suivante :
1. ajouter le noeud i à la fin de la séquence résultat ;
2. pour chaque fils j de i,
(a) effectuer un tour Eulérien à partir de j,
(b) ajouter le noeud i à la fin de la séquence résultat.
Ainsi, sur l'exemple de l'arbre (1), on obtient la séquence suivante :
0, 1, 2, 1, 3, 1, 0, 4, 5, 4, 6, 4, 7, 8, 7, 9, 7, 4, 0
Question 4 Montrer que le tour Eulérien de A contient exactement 2 × n - 1 
éléments. Par la
suite, on appelle m cette valeur et on suppose avoir déclaré un tableau global 
euler de taille m
destiné à contenir le résultat du tour Eulérien.
Question 5 On suppose avoir déclaré un tableau global index de taille n. Écrire 
une procédure
remplir_euler qui remplit le tableau euler avec le résultat du tour Eulérien de 
A et, dans le
même temps, le tableau index de telle sorte que euler[index[i]] = i pour tout i 
entre 0 et n - 1
(s'il existe plusieurs valeurs possibles pour index[i], on pourra choisir 
arbitrairement).
(* Caml *) remplir_euler : unit -> unit
{ Pascal } procedure remplir_euler ;
Par la suite, on suppose avoir appelé cette procédure.
Question 6 Montrer que le plus proche ancêtre commun de i et j dans A est égal 
au plus petit
élément du tableau euler compris entre les indices index[i] et index[j].
Question 7 Écrire une fonction log2 qui prend en argument un entier n, avec n  
1, et calcule
le plus grand entier k tel que 2k  n.
(* Caml *) log2 : int -> int
{ Pascal } function log2(n : integer) : integer ;

3

Question 8 On pose k = log2(m). On suppose avoir déclaré une matrice globale M 
de taille
m × (k + 1). Écrire une procédure remplir_M qui remplit la matrice M de telle 
sorte que, pour
tout 0  j  k et tout 0  i  m - 2j , on ait
M[i][j] =

min euler[l]

il unit
{ Pascal } procedure remplir_M ;
Par la suite, on suppose avoir appelé cette procédure.

Question 9 Écrire une fonction minimum qui prend en arguments deux entiers i et 
j, avec
0  i  j < m, et qui détermine le plus petit élément du segment euler[i..j] en 
temps constant.
(* Caml *) minimum : int -> int -> int
{ Pascal } function minimum(i : integer ; j : integer) : integer ;

Question 10 Écrire une fonction ppac2 qui prend en arguments deux noeuds i et j 
et qui
détermine PPAC(i, j) en temps constant.
(* Caml *) ppac2 : int -> int -> int
{ Pascal } function ppac2(i : integer ; j : integer) : integer ;

III. Opérations sur les bits des entiers primitifs
Dans cette partie, on introduit des notations et des fonctions qui seront 
utiles pour la partie
IV. Il s'agit de fonctions opérant sur la représentation binaire des entiers 
primitifs (type int de
Caml ou integer de Pascal). On ne considère ici que des entiers positifs ou 
nuls, s'écrivant en
binaire sur un nombre de bits N dont la valeur est non précisée et non connue 
(mais inférieure
ou égale à 30). Un entier x s'écrivant en binaire sur N bits est noté (xN -1 . 
. . x1 x0 )2 où chaque
bit xi vaut 0 ou 1. Les chiffres les moins significatifs sont écrits à droite, 
de sorte que la valeur
P -1
i
de x est donc N
i=0 xi 2 .
On suppose que le langage fournit les trois opérations et_bits, ou_bits et 
ou_excl_bits
calculant respectivement les opérations ET, OU et OU-exclusif sur les 
représentations binaires de deux entiers, en temps constant. Plus précisément, 
si x = (xN -1 . . . x1 x0 )2 et
y = (yN -1 . . . y1 y0 )2 , alors et_bits(x, y) est l'entier z = (zN -1 . . . 
z1 z0 )2 défini par
zi = ET(xi , yi ) pour tout i ; de même pour les opérations ou_bits et 
ou_excl_bits. On rappelle
que les opérations ET, OU et OU-exclusif sont définies par les tables de vérité 
suivantes :
ET
OU
OU-exclusif
0 1
0 1
0 1
0 0 0
0 0 1
0 0 1
1 0 1
1 1 1
1 1 0
4

On suppose que le langage fournit également deux opérations decalage_gauche et
decalage_droite décalant respectivement les bits d'un entier vers la gauche et 
vers la droite, en
insérant des bits 0 respectivement à droite et à gauche. Plus précisément, si x 
= (xN -1 . . . x1 x0 )2
et si 0  k  N alors
decalage_gauche(x, k) = (xN -1-k . . . x1 x0 0| .{z
. . 0})2
k

decalage_droite(x, k) = (0
. . 0} xN -1 . . . xk+1 xk )2
| .{z
k

Question 11 Écrire une fonction bit_fort qui prend en argument un entier
x = (xN -1 . . . x1 x0 )2 , supposé non nul, et détermine le plus grand indice 
i tel que xi = 1,
c'est-à-dire la position du bit le plus significatif de x. On garantira une 
complexité O(N ).
(* Caml *) bit_fort : int -> int
{ Pascal } function bit_fort(n : integer) : integer ;
Question 12 Pour plus d'efficacité, on peut pré-calculer et ranger dans un 
tableau les valeurs
de bit_fort pour les 256 premiers entiers. Écrire une nouvelle version de 
bit_fort qui exploite
cette idée pour n'effectuer pas plus de deux décalages. (On rappelle qu'on a 
supposé N  30.)
IV. Cas particulier d'un arbre binaire complet
Dans cette partie, on considère le problème du plus proche ancêtre commun dans 
le cas
particulier où l'arbre A est un arbre binaire complet, c'est-à-dire que tout 
noeud de A a exactement
zéro ou deux fils et toutes les feuilles de A sont à la même distance de la 
racine. (On continue
cependant d'utiliser le même type arbre.) Voici un exemple d'arbre binaire 
complet de hauteur 2 :
0
1
2

4
3

5

6

D'une manière générale, si on note d la hauteur de A, alors A possède 2d 
feuilles et n = 2d+1 - 1
noeuds au total. La hauteur d'un noeud dans l'arbre A est définie comme sa 
distance aux feuilles.
Dans l'exemple ci-dessus, les feuilles 2, 3, 5, 6 ont pour hauteur 0, les 
noeuds 1 et 4 ont pour
hauteur 1 et la racine 0 a pour hauteur 2.
L'idée consiste alors à associer à chaque noeud i un entier B(i) dont la 
représentation en
binaire sur d + 1 bits encode sa position dans l'arbre. On procède ainsi : le 
chemin qui mène de
la racine au noeud est représenté par une suite de 0 et de 1, avec la 
convention que 0 représente
un déplacement vers le sous-arbre gauche et 1 un déplacement vers le sous-arbre 
droit. Pour un
noeud de hauteur h, on obtient donc un chemin de longueur d - h, soit xd . . . 
xh+1 . À ce chemin,
on concatène alors à droite la représentation binaire de 2h , c'est-à-dire un 
bit 1 suivi de h bits 0.
Au final, on a donc pour tout noeud i de hauteur h dans A :
B(i) = ( xd . . . xh+1 1 0| .{z
. . 0} )2
|
{z
}
chemin de 0 à i

h

On note que le chemin est vide pour la racine et que le suffixe de zéros est 
vide pour les feuilles.
Pour l'arbre ci-dessus, on obtient les valeurs suivantes de B(i), données en 
binaire :
5

(100)2
(010)2
(001)2

(110)2

(011)2

(101)2

(111)2

On note que les B(i) prennent toutes les valeurs entre 1 et n, et qu'il y a 
donc bijection entre les
noeuds et les valeurs que leur associe la fonction B.
Question 13 On suppose avoir déclaré deux tableaux globaux, B de taille n et 
Binv de taille
n + 1. Écrire une procédure remplir_B qui remplit le tableau B avec les valeurs 
de B et le
tableau Binv avec les valeurs de B -1 (l'élément d'indice 0 de Binv étant 
inutilisé). On garantira
une complexité O(n).
(* Caml *) remplir_B : unit -> unit
{ Pascal } procedure remplir_B ;
Par la suite, on suppose avoir appelé cette procédure.
Question 14 Soient i et j deux noeuds de A tels que i n'est pas un ancêtre de j 
et j n'est pas un
ancêtre de i. Soit x le résultat de ou_excl_bits(B(i), B(j)), puis k le 
résultat de bit_fort(x).
Que représente k ? Comment en déduire la valeur de B(a), où a est le plus 
proche ancêtre commun
de i et j dans A ?
Question 15 Déduire de la question précédente une fonction ppac3 qui prend en 
arguments
deux noeuds i et j et qui détermine PPAC(i, j) en temps constant. On prendra 
soin de traiter
différemment le cas où i est un ancêtre de j ou j un ancêtre de i ; on pourra 
réutiliser à cet effet
la fonction appartient de la question .
(* Caml *) ppac3 : int -> int -> int
{ Pascal } function ppac3(i : integer ; j : integer) : integer ;
V. Application
Dans cette partie, on considère une application du calcul du plus proche 
ancêtre commun au
problème suivant : étant donné un tableau T de n entiers, on souhaite calculer, 
pour des paires
d'indices i et j tels que 0  i  j < n, l'élément minimum du segment T[i..j]. 
Comme pour le
calcul du plus proche ancêtre commun, on s'autorise un pré-traitement du 
tableau T permettant
ensuite de répondre en temps constant pour tout segment. L'idée est de 
construire un arbre A
contenant les n éléments de T et de se ramener au problème du plus proche 
ancêtre commun.
D'une manière générale, on définit un arbre binaire à partir d'un segment non 
vide T[i..j] en
procédant récursivement de la manière suivante :
1. si i = j, l'arbre est réduit à la feuille T[i] ;
2. sinon, sa racine est le plus petit élément de T[i..j] ; soit T[m] cet 
élément, avec i  m  j
(s'il y a plusieurs valeurs possibles de m, on choisit arbitrairement). On 
distingue alors
trois cas :
6

(a) si m = i, on construit un unique sous-arbre à partir de T[m + 1..j],
(b) si m = j, on construit un unique sous-arbre à partir de T[i..m - 1],
(c) sinon, on construit deux sous-arbres, respectivement à partir de T[i..m - 
1] et de
T[m + 1..j].
L'arbre A est alors défini en partant du segment complet T[0..n - 1]. On note 
que les noeuds de
A ont directement pour valeurs les éléments de T, i.e. on ne se soucie pas ici 
de numéroter les
noeuds de A de 0 à n - 1 afin de vérifier la propriété (P).
On admet le résultat suivant : le plus proche ancêtre commun des noeuds 
correspondant à i
et j dans A est égal à l'élément minimum du segment T[i..j].

Question 16 Donner la complexité dans le pire des cas de l'algorithme récursif 
ci-dessus
construisant A à partir de T, en fonction de n (en supposant le minimum calculé 
en temps
linéaire).
On propose un algorithme plus efficace pour construire l'arbre A. Cet 
algorithme construit
incrémentalement l'arbre correspondant aux éléments de T[0..i], pour i allant 
de 0 à n - 1.
Initialement, l'arbre est réduit à l'unique noeud T[0]. Supposons avoir déjà 
construit l'arbre correspondant aux i premiers éléments de T, c'est-à-dire au 
segment T[0..i - 1]. Cet arbre a la forme
suivante
v
1

v2

t1

(2)
vk-1

t2

vk

tk-1
tk

avec une « branche droite » formée de k noeuds tels que v1  v2  . . .  vk-1  vk 
. Chaque arbre
ti est éventuellement vide et ne contient que des éléments strictement plus 
grands que vi . Pour
insérer l'élément suivant, soit v = T[i], on cherche la position de v dans la 
liste v1 , v2 , . . . , vk ,
c'est-à-dire le plus grand j tel que vj  v < vj+1 (si v < v1 on pose j = 0 et 
si vk  v on pose
j = k). On crée alors un nouveau noeud v que l'on insère à la place de vj+1 et 
le sous-arbre vj+1
est accroché sous le noeud v. On obtient le nouvel arbre
v1

vj

t1
tj

v
vj+1
vk

tj+1
tk

dont la nouvelle branche droite est donc v1 , . . . , vj , v. Si j = k, alors 
on ajoute v comme fils droit
de vk , et la nouvelle branche droite est simplement l'ancienne étendue par v 
(à la fin). On ne
demande pas de montrer la correction de cet algorithme.
7

Question 17 Écrire une fonction construire_A qui construit l'arbre A à partir 
du tableau T
en suivant ce nouvel algorithme.
(* Caml *) construire_A : int array -> arbre
{ Pascal } function construire_A(t : array[0..n-1] of integer) : arbre ;
Indication : on pourra représenter la branche droite par une liste d'arbre (du 
type arbre list
en Caml et liste_arbre en Pascal), dans l'ordre inverse, c'est-à-dire vk , . . 
. , v1 . Chacun de ces
arbres a une racine vi et au plus un fils ti .

Question 18 Montrer que la complexité de cet algorithme est O(n).

Note : En 1984, Harel et Tarjan ont montré qu'il existe un pré-traitement de 
complexité linéaire sur un arbre qui permet d'obtenir ensuite le plus proche 
ancêtre commun en temps constant. On a donc le même résultat pour le problème 
du minimum
du segment.

8

Extrait du corrigé obtenu par reconnaissance optique des caractères



X Informatique MP 2010 -- Corrigé
Ce corrigé est proposé par Vincent Danjean (Enseignant-chercheur en école 
d'ingénieur) ; il a été relu par Olivier Levillain (École Polytechnique) et 
Benjamin Monmege
(ENS Cachan).

Ce problème s'intéresse au problème de la recherche du plus petit ancêtre commun
(PPAC en abrégé) dans un arbre. Ce thème possède de nombreuses applications,
notamment en bio-informatique.
Le sujet s'articule en cinq parties relativement indépendantes.
· La première propose une implémentation simple de la recherche du PPAC.
· La deuxième élabore une solution plus complexe mais plus efficace, à l'aide 
d'un
parcours eulérien de l'arbre.
· La troisième partie, qui ne comprend que deux questions, introduit des 
manipulations de bits ; il s'agit d'un préliminaire pour la partie suivante.
· La partie 4 reprend le problème initial, mais suppose cette fois que l'arbre 
est
binaire complet. Cela permet d'utiliser une méthode originale et efficace basée
sur des manipulations de bits.
· Enfin, la cinquième partie est une application de la recherche du PPAC dans
un arbre pour trouver des minimums sur les segments d'un tableau.
Ce sujet aborde bien évidemment les notions d'arbre, et donc la récursivité pour
leur parcours. La structure d'arbre imposée permet de manipuler des arbres 
d'arité
quelconque. Les parties 3 et 4 font également beaucoup intervenir les opérations
logiques bit à bit.
L'introduction du sujet est assez longue. Il faut cependant bien la lire 
puisqu'elle
présente des propriétés, en particulier sur la numérotation des arbres, qui 
seront
beaucoup utilisées dans tout le sujet. L'énoncé introduit également de 
nombreuses
variables globales, généralement des entiers ou des tableaux d'entiers. Il est 
demandé,
la plupart du temps, d'écrire le code nécessaire à leur utilisation.

Indications
1 Écrire une fonction récursive taille_liste_arbres qui calcule la somme des
tailles des arbres de la liste (en stockant au passage la taille du premier 
élément
de la liste dans le tableau taille).
2 Penser à utiliser la propriété P du sujet (et le tableau taille).
3 Traiter d'abord le cas où l'un des noeuds est ancêtre de l'autre ; sinon, 
descendre
dans l'arbre jusqu'à trouver le PPAC. On peut s'aider d'une fonction auxiliaire
pour chercher dans une liste d'arbres celui qui contient un noeud particulier.
4 Démontrer la propriété par récurrence sur la taille de l'arbre.
5 Utiliser une fonction récursive tour_eulerien qui prend en paramètre le noeud
pour lequel elle calcule le tour Eulérien ainsi que la position dans le tableau 
euler
à laquelle elle doit commencer à écrire et qui renvoie la prochaine position 
dans
le tableau euler où il faudra écrire.
6 Traiter d'abord le cas où un noeud est ancêtre de l'autre et utiliser la 
propriété P
de l'énoncé pour trouver le minimum. Si aucun noeud n'est ancêtre de l'autre,
écrire le tour Eulérien du PPAC, trouver le minimum de ce tour et montrer que
le segment délimité par index[i] et index[j] contient ce minimum.
7 Écrire une fonction auxiliaire récursive qui recherche la propriété inverse 
(premier
entier k tel que 2k > n).
8 Remplir M colonne par colonne en utilisant à chaque fois la colonne 
précédente.

9 Montrer que [ i ; j ] = i ; i + 2log2 (j-i+1) - 1  j - 2log2 (j-i+1) + 1 ; j 
. Précalculer les éléments nécessaires et utiliser M pour répondre en temps 
constant.
10 Utiliser la propriété de la question 6 et la fonction de la question 
précédente.
11 Écrire la fonction récursivement, le cas terminal étant la valeur 1 pour x.
12 Couper les 30 bits du nombre en deux et regarder si le premier groupe est 
entièrement nul ou pas. Rechercher le bit de poids fort uniquement dans le bon 
groupe.
Refaire la même chose une seconde fois. Conclure grâce au tableau pré-calculé.
13 Utiliser une fonction auxiliaire qui parcourt récursivement tout l'arbre en 
ayant
également en paramètre le chemin parcouru jusqu'au noeud courant. La hauteur
peut être pré-calculée ou elle peut être renvoyée par la fonction récursive.
14 B(i) et B(j) commencent par le chemin commun jusqu'à leur PPAC a, puis 
diffèrent juste à ce moment-là (par définition du PPAC).
Pour obtenir B(a), extraire le chemin jusqu'à a de B(i), puis compléter la 
valeur
comme indiquée dans l'énoncé pour tous les noeuds.
15 Traiter rapidement les cas triviaux, puis coder les résultats de la question 
précédente et utiliser Binv pour obtenir le résultat final.
16 Le pire cas est obtenu, par exemple, pour un tableau initial trié.
17 Écrire deux fonctions récursives cree_liste_vi et liste_vi_en_arbre. La 
fonction cree_liste_vi prend en paramètre une valeur v à insérer, une liste de
noeuds vi classée comme dans l'énoncé et une liste de noeuds qui représente les
fils de v après insertion. Elle renvoie la nouvelle liste de noeuds vi . La 
fonction
liste_vi_en_arbre prend en paramètre une liste de noeuds vi classée comme
dans l'énoncé et une liste d'arbres vide ou avec juste l'arbre final 
partiellement
reconstruit. Elle renvoie l'arbre final. Appeler ensuite cree_liste_vi pour 
chacune des valeurs et liste_vi_en_arbre à la fin.
18 Compter les insertions et suppressions de valeurs dans la liste des noeuds 
vi .

I. Une solution simple
1 Le calcul des tailles de tous les sous-arbres va être réalisé au cours d'un 
parcours
récursifs de tous les noeuds. Pour cela, on va utiliser une fonction auxiliaire 
récursive.
La fonction taille_liste_arbres prend en paramètre une liste d'arbres et 
calcule, récursivement par rapport à la liste, la taille totale cumulée de ces 
arbres.
Elle stocke dans le tableau taille la taille de l'arbre sous le premier noeud. 
La taille
d'un arbre est obtenue en s'appelant récursivement sur ses fils (ce qui stocke 
au
passage les tailles des fils dans le tableau taille).
Il suffit donc à la fonction principale d'appeler cette fonction en passant une 
liste,
dont l'unique élément est l'arbre complet.
let taille = make_vect n 0;;
let remplir_taille () =
let rec taille_liste_arbres liste_arbres =
match liste_arbres with
[] -> 0
| Noeud(i, fils)::suite ->
taille.(i) <- 1 + (taille_liste_arbres fils);
taille.(i) + (taille_liste_arbres suite)
in
let taille_totale = taille_liste_arbres [A] in
()
;;
Ce code parcourt l'arbre récursivement en passant une fois par chacun des 
noeuds.
Le traitement de chaque noeud se fait en temps constant (somme et affectation 
dans
le tableau). La complexité du code est donc proportionnelle à la taille de 
l'arbre.
remplir_taille a une complexité en O(n).
2 Comme les noeuds d'un sous-arbre sont numérotés consécutivement à partir du
numéro de sa racine, il est facile de connaître l'appartenance d'un noeud à un 
sousarbre. En effet, le sous-arbre i contient les noeuds j à j + taille[j] - 1 
(propriété P
de l'énoncé).
let appartient i j =
(j <= i) && (i <= j+taille.(j)-1)
;;
appartient a une complexité en temps constante.
3 Pour trouver le PPAC de deux noeuds, on utilise sa définition. Tout d'abord,
si l'un des deux noeuds est un ancêtre de l'autre, alors on peut conclure 
immédiatement (en temps constant) en appelant la fonction appartient de la 
question 2.
Sinon, le PPAC sera un noeud possédant deux fils distincts dont les sous-arbres
respectifs abritent les deux noeuds. Pour trouver le PPAC, on part de la racine.
Si les noeuds sont dans deux branches distinctes, cela signifie que le PPAC est 
trouvé.
Dans le cas contraire, la recherche est relancée dans le sous-arbre commun.
Pour trouver la branche à laquelle appartient un noeud, on fait une recherche
récursive dans les fils grâce à la fonction auxiliaire chercher_fils : int -> 
arbre

list -> arbre. Cette fonction prend en premier paramètre le noeud que l'on 
recherche dans la liste des sous-arbres passée en second paramètre. Elle 
retourne le
sous-arbre trouvé.
let rec chercher_fils i fils =
match fils with
[] -> failwith "noeud cherché absent !"
| (Noeud(v, _) as noeud)::suite ->
if appartient i v
then noeud
else chercher_fils i suite
;;
let ppac1 i j =
if appartient j i then i
else if appartient i j then j
else
let rec ppac1_rec arbre =
match arbre with
| Noeud(v, fils) ->
let a1 = chercher_fils i fils
and a2 = chercher_fils j fils
in
if a1 == a2
then ppac1_rec a1
else v
in
ppac1_rec A
;;

Lorsqu'on regarde si les deux noeuds trouvés sont les mêmes ou pas, on utilise
l'opérateur == et pas l'opérateur =. En effet, on veut savoir si les deux noeuds
sont physiquement les mêmes (ce qui se fait en temps constant). On ne veut
pas comparer récursivement la structure des deux sous-arbres de ces deux
noeuds (ça serait correct pour le résultat, puisque deux sous-arbres distincts
ne peuvent pas avoir la même numérotation, mais ça ne serait pas en temps
constant).
La fonction ppac1_rec effectue au pire un parcours de l'une des branches de
l'arbre. Son coût (en excluant celui des appels à chercher_fils pour l'instant) 
est
donc majoré par la hauteur de l'arbre.
La recherche dans un fils (fonction appartient) étant en temps constant, la
fonction chercher_fils a un coût proportionnel au nombre de fils du noeud de
recherche. Par conséquent, le coût global de toutes ces recherches est 
proportionnel à
deux fois la somme du nombre de fils des noeuds explorés (chercher_fils est 
appelé
deux fois pour chaque noeud exploré dans ppac1_rec). Il est majoré par deux 
fois le
nombre de noeuds total.
La fonction ppac1 a une complexité dans le pire des cas en O(n).