La complexité dans le pire des cas est peu satisfaisante. Insérons
dans un arbre des éléments par ordre croissant, et il seront disposés
en liste. Chaque opération se fera de la sorte en un temps
. Ces performances sont les mêmes qu'avec des listes
chaînées. On en conclut que dans le pire des cas, les ABR ne sont pas
plus performants que des vulgaires listes chaînées. Nous allons nous
intéresser, dans la suite de ce cours, à des arbres binaires de
recherche quelque peu particuliers, dans lesquels toute opération se
fera en temps
.