# OLA, TD7: Arbres binaires

## Exercice 1: Vrai ou Faux

1. Faux: l'arbre vide a bien zéro noeuds
2. Vrai: N(V,V)
3. Faux: N(N(V,V),V) et N(V,N(V,V))
4. Vrai: un fil

5. Vrai
6. Faux: on a le droit à 15 noeuds maximum
7. Nombre d'arbres binaires à 5 noeuds:

$C_{5}= C_{0}C_{4} + C_{1}C_{3} + C_{2}C_{2} + C_{3}C_{1} + C_{4}C_{0}
= 1*14 + 1*5 + 2*2 + 5*1 + 14*1 = 42$

8. $C_{n+1}=$ somme pour k allant de 0 à n des Ck* Cn-k
$C_{n+1} = C_{0}C_{n} + C_{1}C_{n-1} + ... + C_{k}C_{n-k} + ... + C_{k+1}C_{n-(k+1)} + ... + C_{n}C_{0} = \sum\limits_{\substack{0 \le k \le n}}{C_{k}C_{n-k}}$

## Exercice 2: Arbres binaires de recherche

1.
$in(n, V)=V$
$in (n, N(a_{1}, k, a_{2}))= k == n || in (n, a_{1}) || in (n, a_{2})$

2.

$infix(V)= \epsilon$
$infix(N(a_{1},n,a_{2}))=infix(a_{1}).n.infix(a_{2})$

3.

S(n) => oui
N (S(1),2,S(3)) => oui
N (V,2,N(S(1),3,V)) => non
4. 

5.
Cas de base:
$infix(V)=\epsilon$ qui est trié (le mot vide)
On suppose (hypothèse de récurrence) que les arbres $a_{1}$ et $a_{2}$
sont tels que $infix(a_{1})$ est trié et $infix(a_{2})$ est trié.
$infix(N(a{1}, n, a{2}))= infix(a_{1}).n.infix(a_{2})$
Soient deux entiers i et j consécutifs dans la suite constituée par
$infix(a_{1}).n.infix(a_{2})$
- Soit i et j sont dans $infix(a_{1})$ par hypothèse de récurrence i < j
- Soit i et j sont dans $infix(a_{2})$ par hypothèse de récurrence i < j
- Si on compare le dernier élément i de $infix(a_{1})$ avec n, alors comme a est un arbre binaire de recherche, on sait que i est inférieur à n car i est dans le fils gauche du noeud n.
- Si on compare le premier élément j de $infix(a_{2})$ avec n, alors comme a est un arbre binaire de recherche, on sait que n est inférieur à j car j est dans le fils droit du noeud n.

6. Si l'element x < n on cherchera dans les fils gauche et si l'élément > n on cherchera dans le fils droit.
7.
Cas de base : inabr (x, V) = faux
Cas récursif : inabr(x, N(a1, n, a2)) = si x = n on renvoie vrai
si x < n alors inabr(x, a1)
si x > n alors inabr(x, a2)

8. Cas de base: comme inabr(n, V) est faux pour tout n, la propriété est vraie
Cas récursif : on suppose que pour tout n, inabr(n, a1) => in (n, a1)
et inabr(n, a2) => in (n, a2)
On suppose que inabr(n, N(a1, k, a2)) est vrai
et on veut montrer qu'alors in(a, N(a1, k, a2)).
Si k = n alors on a aussi que in(n, N(a1, k, a2))
Si n < k alors on a inabr(n, a1) est vrai et on applique l'hypothèse de récurrence. On obtient que in(n, a1) est vrai donc aussi in(n, N(a1, k, a2)).
Si n > k on fait le même raisonnement mais avec a2.

si a = v -> faux
si a = N(a1,x,a2) :
si x=n -> vrai
si n< x :
inabr(a1,n)
si non :
inabr(a2,n)