Nous avons vu au début de ce chapitre la définition d'un arbre équilibré ainsi que les formules permettant d'évaluer la profondeur d'un tel arbre équilibré. Pour les arbres de tri, nous avons aussi vu que la forme finale de la structure dépendait non seulement des valeurs que l'on y mettait, mais aussi de l'ordre dans lequel on mettait ces valeur dans l'arbre. Par exemple, la suite de nombres 6, 3, 1, 9, 7, 5, 10 nous amènera à construire l'arbre de tri suivant :
Fig. 8.9. Données aboutissant à un arbre équilibré.
alors que la suite des mêmes nombres 9, 7, 6, 5, 10, 3, 1 produirait l'arbre suivant :
Fig. 8.9. Données aboutissant à un arbre très déséquilibré
Au pire, l'arbre peut dégénérer en une simple chaîne. Au vu de ces exemples, on se rend bien compte que l'intérêt d'utiliser une structure d'arbre reflétant une relation d'ordre pour diminuer le nombre de comparaisons à effectuer peut dépendre fortement de l'ordre dans lequel ces données sont traitées.
C'est la raison pour laquelle on envisage souvent d'appliquer des algorithmes de rééquilibrage aux structures d'arbres. Nous n'en verrons toutefois pas ici car il existe d'autres structures, telles que les b-arbres, qui ont des propriétés similaires aux structures d'arbres, mais qui, de par leurs algorithmes de manipulation, ont la propriété supplémentaire de rester assez équilibrées.
9. Structures récursives non linéaires : les
listes
Site Hosting: Bronco
Table des
matières.