On évalue ici le nombre de comparaisons entre étiquettes dans le pire cas, lorsque les recherches ne s’arrêtent pas prématurément. La hauteur est comptée en arêtes : l’arbre vide a pour hauteur {-1}. Un arbre parfait de hauteur {h\ge0} possède {n=2^{h+1}-1} nœuds. Le terme « complet » employé ci-dessous désigne ces arbres parfaits.
10.4.1 Appartenance d'un élément à un arbre
La fonction element teste si une étiquette {x} apparaît dans un arbre {\mathcal{A}:}
|
1 2 3 4 |
let rec element x a = match a with | Vide -> false | Noeud(g, e, d) -> x = e || element x g || element x d;; val element : 'a -> 'a arbre -> bool = <fun> |
Notons {E_{h}} la complexité de element (en fonction de la hauteur {h,} sachant que l’arbre est complet).
En ne comptant que les comparaisons entre étiquettes, on a {E_{-1}=0} et {E_h=1+2E_{h-1}} pour {h\ge0}. Par récurrence, {E_h=2^{h+1}-1=n} : chaque étiquette est comparée une fois à la valeur recherchée.
La fonction occurences dit combien de fois une étiquette {x} apparaît dans un arbre {\mathcal{A}:}
|
1 2 3 4 |
let rec occurences x a = match a with | Vide -> 0 | Noeud(g, e, d) -> (if x = e then 1 else 0) + occurences x g + occurences x d;; val occurences : 'a -> 'a arbre -> int = <fun> |
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres