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) :
|
1 |
type 'a arbre = | Vide | Noeud of ('a arbre) * 'a * ('a arbre);; |

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}.
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres