Tests d’appartenance et d’unicité

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}:}

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}:}

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