Fonctions de base sur un ABR

On dit qu’un arbre binaire un arbre binaire de recherche (en abrégé un ABR) quand l’étiquette portée par un noeud {N} est toujours supérieure (ou égale) aux étiquettes du sous-arbre gauche de {N} et inférieure (ou égale) aux étiquettes du sous-arbre droite de {N.}

L’arbre ci-dessous est précisément un ABR.

On rappelle la définition du type arbre dont les noeuds portent une étiquette de type 'a (le premier élément du triplet est le sous-arbre gauche) :

Figure du chapitre 11, page 1

Soit {\mathcal{A}} un ABR de taille {n} et de hauteur {h}, comptée en arêtes. L’arbre vide a pour hauteur {-1}. L’arbre cité en exemple possède dix nœuds et sa hauteur est quatre. Pour un arbre non vide, on a {h+1\le n\le 2^{h+1}-1}, soit {\log_2(n+1)-1\le h\le n-1}.

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :