Algorithmique dans les arbres

On définit une bijection $cle$ entre les noeuds de $A$ et un ensemble $(E, >)$ totalement ordonné. On note $cle(x)$ la clé du noeud $x$. En général, on prend $E = \mbox{I\hspace{-.15em}N}$.

Nous représenterons chaque noeud d'un arbre binaire avec une structure $ABR$ contenant les champs suivants :

• $cle$
• $g$
• $d$

Si $a$ est une variable de type AB alors $a.cle$ est la clé de la racine de l'arbre $a$, $a.d$ est un pointeur vers le sous-arbre droit, $a.g$ est un pointeur vers le sous-arbre gauche. Si un pointeur ne pointe vers aucune valeur, on dira qu'il prend la valeur $null$. On fera une allocation dynamique en utilisant la fonction $AB(f_g, c, f_d)$ pour créer un noeud de clé $c$ et de sous-arbre gauche (resp. droit) $f_g$ (resp. $f_d$) de type AB.