Arbres binaires de recherche

Arbre AVL

L'ordre d'insertion des noeuds dans un arbre binaire de recherche est significatif pour la forme finale de l'arbre. Ainsi, par exemple, l'insertion des étiquettes [1, 2, 3, 4, 5] produira un arbre déséquilibré dont la recherche d'un élément s'avérera ne pas être plus efficace que la recherche séquentielle sur une liste triée.

Afin d'éviter un tel phénomène, il est possible de recourir aux arbres AVL, qui ont été historiquement les premiers arbres binaires de recherche automatiquement équilibrés. Dans un arbre AVL, les hauteurs des deux sous-arbres d'un même noeud diffèrent au plus d'une unité. La recherche, l'insertion et la suppression se font ainsi toutes en un temps logarithmique dans le pire des cas.

Le facteur d'équilibrage d'un noeud est la différence entre la hauteur de son sous-arbre droit et celle de son sous-arbre gauche. Un noeud dont le facteur d'équilibrage est de +1, 0 ou -1 est considéré comme équilibré.

Chaque fois qu'un noeud d'un arbre AVL est inséré ou supprimé, le facteur d'équilibrage de chaque noeud situé le long du chemin depuis la racine jusqu'au noedu inséré ou supprimé doit être recalculé. Si l'arbre reste équilibré, il n'y a rien à faire. Si ce n'est pas le cas, il convient d'effectuer des rotations d'équilibrage de manière à obtenir un arbre AVL.

Rotations d'équilibrage

Une rotation est une modification locale d'un arbre binaire. Elle consiste à échanger un noeud avec l'un des ses fils. Dans la rotation droite, un noeud devient le fils droit du noeud qui étais son fils gauche. Dans la rotation gauche, un noeud devient le fils gauche du noeud qui était son fils droit.

Une rotation simple droite est utilisée quand un noeud a un facteur d'équilibrage inférieur à -1 et que son fils gauche a un facteur d'équilibrage de -1.

Une rotation double droite est utilisée quand un noeud a un facteur d'équilibrage inférieur à -1 et que son fils gauche a un facteur d'équilibrage de +1. La double rotation droite est une rotation simple gauche du sous-arbre gauche, suivi d'une rotation simple droite du noeud déséquilibré. Cette opération est aussi appelée parfois rotation gauche-droite.

Une rotation simple gauche est utilisée quant un noeud a un facteur d'équilibrage supérieur à +1 et que son fils droit a un facteur d'équilibrage de +1.

Une rotation double gauche est utilisée quand un noeud a un facteur d'équilibrage supérieur à +1 et que son fils gauche a un facteur d'équilibrage de -1. La double rotation gauche est une rotation simple droite du sous-arbre droit, suivi d'une rotation simple gauche du noeud déséquilibré. Cette opération est aussi appelée parfois une rotation droite-gauche.

Recherche

La recherche dans un arbre AVL se déroule exactement comme pour un arbre binaire de recherche, et comme la hauteur d'un arbre AVL est en log(n), la recherche se fait donc en un temps logarithmique.

Insertion

L'insertion dans un arbre AVL se déroule en deux étapes:

1. On insère le noeud exactement de la même manière que dans un arbre binaire de recherche;
2. On remonte depuis le noeud inséré vers la racine en effectuant une rotation sur chaque sous-arbre déséquilibré.

Il est possible de montrer qu'il suffit d'une rotation simple ou d'une double rotation pour rééquilibrer un arbre AVL après une insertion.

La hauteur de l'arbre étant en log(n) et les rotations s'effectuant en un temps constant, l'insertion se fait finalement en un temps logarithmique.

Suppression

Pour supprimer un noeud dans un arbre AVL, on procède comme avec un arbre binaire de recherche. On remonte ensuite le chemin depuis le parent du noeud enlevé jusqu'à la racine pour rééquilibrer les noeuds qui en ont besoin. La suppression se fait également en un temps logarithmique.

Afficher la solution | Masquer la solution