Notions abordées : arbres triés, arbres équilibrés, arbres parfaits et tas.
On considère ici des arbres binaires triés, c.-à-d.
tels que pour tout sous-arbre non vide Enrac(g,r,d), tous
les éléments de g sont inférieurs ou égaux à r
et tous ceux de d sont strictement supérieurs à r.
est_trie(a) qui teste si un arbre
est trié (tester votre fonction).min(a) et max(a) qui
trouve le plus petit et le plus grand élément d'un arbre trié. rotgauche(a) et rotdroite(a)
qui effectue une rotation respectivement à gauche et à droite d'un arbre
trié.equilibre(a) qui équilibre un arbre
trié. Proposer deux versions : -- (a) une version qui crée un nouvel
arbre. -- (b) une version qui modifie l'arbre en argument.
Arbres parfaits.
On considère ici les arbres binaires parfaits vus en
TD, c.-à-d. dont les nœuds sont repérés par des adresses entre 0
et n-1 (où n est le nombre de nœuds) affectées
dans l'ordre d'un parcours en largeur à partir de la racine. On choisit de
définir les opérations spécifiques en procédant comme en TD, c-à-d. en
considérant Vide() et Ajout(a,x) (l'ajout
d'une nouveau noeud d'étiquette x) comme les seuls
constructeurs.
dernier(a) qui retourne
l'étiquette qui se trouve à l'adresse n-1 et debut(a)
qui retourne l'arbre sans son dernier élément.nb_noeuds(a) qui
renvoie le nombre de nœuds.nb_feuilles(a) qui
renvoie le nombre de feuilles.etiquette(a,k) qui
renvoie l'étiquette à l'adresse k.echange(a,k1,k2) qui échange les
étiquettes qui se trouvent aux adresses k1 et k2.
On choisit de représenter les arbres parfaits de taille bornée par N par un tableau où les étiquettes de l'arbre sont contiguës en mémoire (cf. figure ci-dessous).
Une telle représentation s'appelle un tas. Reprendre les définitions de chacune des opérations de base de l'exercice précédent en utilisant cette nouvelle représentation.