254
6 Arbres binaires de recherche
Fig. 6.10 Un arbre récursif τ (ou plutôt son représentant planaire R(τ )) de taille 14, et l’arbre
binaire associé τ , de taille 13. Cet arbre binaire a été complété par 14 feuilles, correspondant aux
14 possibilités d’insérer un nouveau nœud dans l’arbre récursif ; nous en donnons 3 exemples
est le nombre de branches gauches entre la racine et ce nœud). Par conséquent la
hauteur de l’arbre récursif est (toujours à 1 près) la hauteur à gauche de l’arbre
binaire associé.
6 Arbres binaires de recherche
Fig. 6.10 Un arbre récursif τ (ou plutôt son représentant planaire R(τ )) de taille 14, et l’arbre
binaire associé τ , de taille 13. Cet arbre binaire a été complété par 14 feuilles, correspondant aux
14 possibilités d’insérer un nouveau nœud dans l’arbre récursif ; nous en donnons 3 exemples
est le nombre de branches gauches entre la racine et ce nœud). Par conséquent la
hauteur de l’arbre récursif est (toujours à 1 près) la hauteur à gauche de l’arbre
binaire associé.