type ('f, 'n) arbre =
| Feuille of 'f
| NoeudInterne of ('f, 'n) arbre * 'n * ('f, 'n) arbre
;;
let arbre =
NoeudInterne (Feuille 2, 1, NoeudInterne (Feuille 4, 3, Feuille 5))
;;
let rec symetrique arbre =
match arbre with
| Feuille _ -> arbre
| NoeudInterne (fils_gauche, noeud, fils_droit) ->
NoeudInterne (symetrique fils_droit, noeud, symetrique fils_gauche)
;;
symetrique arbre;;
1)
let rec initialise_complet n val_f val_n =
match n with
| 0 -> Feuille val_f
| _ -> let arbre = initialise_complet (n - 1) val_f val_n in
NoeudInterne (arbre, val_n, arbre)
;;
initialise_complet 2 1 0;;
2) Un arbre complet de hauteur $h$ a $2^h$ feuilles de profondeur $h$ chacune. Son cheminement est donc de $h\cdot 2^h$.
1)
let rec strahler arbre =
match arbre with
| Feuille _ -> 1
| NoeudInterne(fils_gauche, _, fils_droit) ->
let s_g = strahler fils_gauche in
let s_d = strahler fils_droit in
if s_g = s_d then
s_g + 1
else
max s_g s_d
;;
let arbre2 =
let sous_arbre = initialise_complet 2 0 0 in
NoeudInterne(
NoeudInterne(
sous_arbre,
0,
NoeudInterne(
sous_arbre,
0,
Feuille 0
)
),
0,
Feuille 0
)
;;
strahler arbre2;;
2) Par récurrence sur $h\in\mathbb N$.
3) Un arbre de hauteur $h\neq0$ possède au moins un noeud interne, donc au moins un noeud avec deux feuilles qui aura $2$ comme nombre de Strahler. Comme le nombre de Strahler d'un noeud est toujours au moins aussi grand que ceux de ses fils, un arbre de hauteur $h\neq0$ a bien un nombre de Strahler au moins égal à $2$.
De plus, ce nombre sera égal à $2$ si et seulement si tous les noeuds internes ont un nombre de Strahler de $2$ (toujours vu la propriété de croissance). Cela signifie que chaque noeud interne doit avoir un fils dont le nombre de Strahler vaut $1$ et un fils dont le nombre de Strahler vaut $2$, ce qui correspond bien au type d'arbre décrit dans la question.
1) et 2) Notons que cette relation n'a de sens que pour un arbre non vide.
0
|
1
|
2
|
...
|
n - 1
On a donc toujours $h\leqslant n-1$.
0
/ \
1 2
/ \ /
3 4 5
On a alors $1+2+\dotsb+2^{h-1}<n\leqslant1+2+\dotsb+2^h$ soit $2^{h}-1<n\leqslant2^{h+1}-1$, donc $2^h\leqslant n<2^{h+1}$ soit $h\leqslant\log_2 n< h+1$ et donc $h=\lfloor\log_2 n\rfloor$.
On a donc toujours $h\geqslant\lfloor\log_2 n\rfloor$.
Autre preuve possible : par induction structurelle.
3) Voir ci-dessus.
4) Par récurrence d'ordre $2$ sur $h\in\mathbb N$.
Initialisation : $N_0=1=\mathcal F_2-1$ avec $\mathcal F_2=2$ et $N_1=2=\mathcal F_3-1$ avec $\mathcal F_3=3$ (la racine et une feuille).
Hérédité : Si $h\in\mathbb N^*$ tel que $N_{h-1}=\mathcal F_{h+1}-1$ et $N_{h-2}=\mathcal F_{h}-1$, on considère un arbre équilibré de hauteur $h$. Sa racine a un fils, disons le gauche, de hauteur $h-1$ et un fils droit de hauteur $h_d\in\{h-1, h-2\}$. Par hypothèse de récurrence, le fils gauche a au minimum $N_{h-1}=\mathcal F_{h+1}-1$ noeuds. Le nombre de noeuds du fils droit est au moins égal à $N_{h-2}=\mathcal F_{h}-1$. Et donc $N_h\geqslant 1+N_{h-1}+N_{h-2}=F_{h+1}+F_{h}-1\geqslant F_{h+2}-1$ ce qui établit la récurrence.
5) On a alors $N_h\sim C\cdot\varphi^h$ où $C$ est une constante et $\varphi$ le nombre d'or.
Donc, avec les règles usuelles (on n'est pas au voisinage de $1$), $h\log\varphi\sim \log N_h.$ Or $N_h\leqslant n$ d'où $h=O(\log n)$.
Par ailleurs, on a $n<2^{h+1}$ donc $\log n<h+1$ donc $h=\Omega(\log n)$.
On en déduit que $h=\Theta(\log n)$.
type ('f, 'n) noeud = F of 'f | NI of 'n;;
1) NoeudInterne code à l'arbre (triplet (fils gauche, étiquette, fils droit)) issu du noeud alors que NI code seulement à l'étiquette du noeud.
2)
[NI 1; F 2; NI 3; F 4; F 5][F 2; NI 1; F 4; NI 3; F 5][F 2; F 4; F 5; NI 3; NI 1][NI 1; NI 3; F 5; F 4; F 2][F 5; NI 3; F 4; NI 1; F 2][F 5; F 4; NI 3; F 2; NI 1]3)
let rec parcours_prefixe arbre =
match arbre with
| Feuille f -> [F f]
| NoeudInterne(fils_gauche, noeud, fils_droit) ->
(NI noeud) :: (parcours_prefixe fils_gauche) @ (parcours_prefixe fils_droit)
;;
parcours_prefixe arbre;;
parcours_prefixe (symetrique arbre);;
4) Dans le pire cas, l'arbre est complet et la complexité vérifie, pour une hauteur $h$, $T(0)=O(1)$ et $T(h)=2\cdot T(h-1)+O(2^h)$. Soit $\frac{T(h)}{2^h}=O(h)$ ou encore $T(h)=O\left(h2^h\right)$.
En fonction du nombre $n$ de noeuds, on obtient $T(n)=O\left(n\log n\right)$. Remarquons qu'un parcours visite toujours chaque noeud une et une seule fois, d'où un coût linéaire en le nombre de noeuds, auquel il faut ajouter un éventuel traitement à chaque noeud (ici, la concaténation des listes).
5)
let rec parcours_infixe arbre =
match arbre with
| Feuille f -> [F f]
| NoeudInterne(fils_gauche, noeud, fils_droit) ->
(parcours_infixe fils_gauche) @ ((NI noeud) :: parcours_infixe fils_droit)
;;
parcours_infixe arbre;;
parcours_infixe (symetrique arbre);;
let rec parcours_suffixe arbre =
match arbre with
| Feuille f -> [F f]
| NoeudInterne(fils_gauche, noeud, fils_droit) ->
(parcours_suffixe fils_gauche) @ (parcours_suffixe fils_droit) @ [NI noeud]
;;
parcours_suffixe arbre;;
parcours_suffixe (symetrique arbre);;
6)
let parcours_prefixe arbre =
let rec parcours_aux arbre accu =
match arbre with
| Feuille f -> (F f) :: accu
| NoeudInterne(fils_gauche, noeud, fils_droit) ->
(NI noeud) :: parcours_aux fils_gauche (parcours_aux fils_droit accu)
in
parcours_aux arbre []
;;
parcours_prefixe arbre;;
La complexité est bien linéaire (chaque noeud est parcouru une seule fois, les opérations pour chaque noeud sont à coût constant) mais la fonction auxiliaire n'est pas récursive terminale. En voici une version avec des fonctions auxiliaires récursives terminales.
let parcours_prefixe arbre =
let rec parcours_envers arbre accu =
match arbre with
| Feuille f -> (F f) :: accu
| NoeudInterne(fils_gauche, noeud, fils_droit) ->
parcours_envers fils_droit (parcours_envers fils_gauche ((NI noeud) :: accu))
in
List.rev (parcours_envers arbre [])
;;
parcours_prefixe arbre;;
7)
1
/ \
2 4
/ \
4 5
8)
let reconstruire_prefixe liste =
(* aux prend en argument une liste et renvoie un couple constitué de l'arbre construit
sur le début de la liste et de la liste des éléments restants. *)
let rec aux liste =
match liste with
| (F f1) :: q -> (Feuille f1, q)
| (NI n) :: q ->
let fils_gauche, liste1 = aux q in
let fils_droit, liste2 = aux liste1 in
(NoeudInterne (fils_gauche, n, fils_droit), liste2)
| _ -> failwith "Cette liste ne correspond pas à un parcours prefixe."
in
let arbre, liste1 = aux liste in
match liste1 with
| [] -> arbre
| _ -> failwith "Cette liste ne correspond pas à un parcours prefixe."
;;
reconstruire_prefixe [NI 1; F 2; NI 3; F 4; F 5];;
reconstruire_prefixe [NI 1; NI 3; F 5; F 4; F 2];;
reconstruire_prefixe [F 5; F 4; NI 3; F 2; NI 1];;
9) Les arbres suivants ont même parcours infixe.
1 2
/ \ / \
2 5 et 3 1
/ \ / \
3 4 4 5