AVL tree

Arbre AVL

Page d'aide sur l'homonymie Pour les articles homonymes, voir AVL.
Un exemple d'arbre non-AVL.

En informatique, les arbres AVL 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 nœud diffèrent au plus de un. La recherche, l'insertion et la suppression sont toutes en O(ln n) dans le pire des cas. L'insertion et la suppression nécessitent d'effectuer des rotations.

La dénomination "arbre AVL" provient des noms de ses deux inventeurs, respectivement G.M. Adelson-Velsky et E.M. Landis, qui l'ont publié en 1962 sous le titre An algorithm for the organization of information.

Le facteur d'équilibrage d'un nœud est la différence entre la hauteur de son sous-arbre droit et celle de son sous-arbre gauche. Un nœud dont le facteur d'équilibrage est 1, 0, ou -1 est considéré comme équilibré. Un nœud avec tout autre facteur est considéré comme déséquilibré et requiert un rééquilibrage. Le facteur d'équilibrage est soit déduit des hauteurs des sous arbres, soit stocké dans chaque nœud de l'arbre (ce qui permet un gain de place, ce facteur pouvant être stocké sur deux bits, mais complexifie les opérations d'insertion et de suppression).

Le même arbre après un rééquilibrage.

Sommaire

Opérations

Les opérations de base d'un arbre AVL mettent en œuvre généralement les mêmes algorithmes que pour un arbre binaire de recherche, à ceci près qu'il faut ajouter des rotations de rééquilibrage nommées "rotations AVL".

Insertion

L'insertion dans un arbre AVL se déroule en deux étapes : Tout d'abord, on insère le nœud exactement de la même manière que dans un arbre binaire de recherche ; puis on remonte depuis le nœud inséré vers la racine en effectuant une rotation sur chaque sous-arbre déséquilibré. La hauteur de l'arbre étant en O(ln(n)), et les rotations étant à temps constant, l'insertion se fait finalement en O(ln(n)).

Suppression

La suppression dans un arbre AVL peut se faire par rotations successives du nœud à supprimer jusqu'à une feuille (en choisissant ces rotations de sorte que l'arbre reste équilibré), et ensuite en supprimant cette feuille directement. La suppression se fait aussi en O(ln(n)).

Recherche

La recherche dans un arbre AVL se déroule exactement de la même manière que pour un arbre binaire de recherche, et comme la hauteur d'un arbre AVL est en O(ln(n)), elle se fait donc en O(ln(n)). Contrairement aux arbres splay, la recherche ne modifie pas la structure de l'arbre.

Taille

Dans un arbre AVL de hauteur h, dans le pire des cas, en supposant que l'arbre est déséquilibré vers la gauche, le sous-arbre de gauche aura une hauteur de h-1, tandis que le sous-arbre de droite aura une hauteur de h-2.

Ceci donne une formule de récurrence pour connaître la taille minimale d'un arbre AVL de hauteur h. Cette formule de récurrence est la définition par récurrence des nombres de Fibonacci : f(n) = f(n − 1) + f(n − 2)

Inversement, dans le meilleur des cas, « le nombre de nœuds internes est égal au logarithme en base deux de la hauteur, diminué de un »[1],[2] : 
\dfrac{n}{\mathrm{fib}(n)} \longrightarrow \sqrt{2} \times \log_{2}{n}

Cela donne une formule pour calculer la hauteur, dans le pire des cas, pour un arbre AVL contenant n nœuds internes.

Cette grandeur est meilleure que pour les arbres rouge et noir, où on a[1],[3] : 2 \times \log{n}

Notes et références

  1. a  et b Cormen, Leiserson, Introduction à l'algorithmique, annexe B
  2. [pdf] http://www.engr.mun.ca/~theo/Courses/dm/pub/2004/dm-application5.pdf
  3. Pour des informations sur la taille, on pourra aussi consulter la page web {en} http://www.dyalog.dk/dfnsdws/n_avl.htm

Sources

  • G. Adelson-Velskii et E.M. Landis, « An algorithm for the organization of information ». Doklady Akademii Nauk SSSR, 146 : 263–-266, 1962.
  • Danièle Beauquier, Jean Berstel, Philippe Chrétienne : Éléments d’algorithmique. Masson, 1992. (ISBN 2-225-82704-4) Voir en particulier le chapitre 6 sur les « arbres et ensembles ordonnées ».
  • Donald Knuth. The Art of Computer Programming, volume 3 : « Sorting and Searching », 3e édition. Addison-Wesley, 1997. (ISBN 0-201-89685-0) Voir en particulier les pages 458 à 475 de la section 6.2.3 : « Balanced Trees », expression qui désigne les arbres AVL chez Knuth.

Voir aussi

Articles connexes

Liens externes

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Arbre AVL ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article AVL tree de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • AVL tree — In computer science, an AVL tree is a self balancing binary search tree, and it is the first such data structure to be invented. [Robert Sedgewick, Algorithms , Addison Wesley, 1983, ISBN 0 201 06672 6, page 199, chapter 15: Balanced Trees.] In… …   Wikipedia

  • AVL — can stand for any one of the following things:*AVL, the Austrian based (automotive) engineering consulting firm and research institute Anstalt für Verbrennungskraftmaschinen List *Acadèmia Valenciana de la Llengua (Valencian academy of the… …   Wikipedia

  • Tree rotation — A tree rotation is an operation on a binary search tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. They are used to change the shape of the tree …   Wikipedia

  • Tree (data structure) — A simple unordered tree; in this diagram, the node labeled 7 has two children, labeled 2 and 6, and one parent, labeled 2. The root node, at the top, has no parent. In computer science, a tree is a widely used data structure that emulates a… …   Wikipedia

  • Tree structure — A tree structure showing the possible hierarchical organization of an encyclopedia …   Wikipedia

  • AVL — abbr. Adelson, Veslkij and Laudis (tree) comp. abbr. AVL Tree (named after its founders: Adelson, Veiskii and Landis) …   United dictionary of abbreviations and acronyms

  • Red-black tree — A red black tree is a type of self balancing binary search tree, a data structure used in computer science, typically used to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer who called them symmetric… …   Wikipedia

  • Splay tree — A splay tree is a self balancing binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look up and removal in O(log(n)) amortized time. For many… …   Wikipedia

  • Binary search tree — In computer science, a binary search tree (BST) is a binary tree data structurewhich has the following properties: *each node (item in the tree) has a value; *a total order (linear order) is defined on these values; *the left subtree of a node… …   Wikipedia

  • T-tree — In computer science a T tree is a type of binary tree data structure that is used by main memory databases, such as DataBlitz, e X treme DB, MySQL Cluster, Oracle TimesTen and [http://www.kairosdbms.com Kairos] [http://www.emware.co.kr… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”