Property |
Value |
dbo:abstract
|
- En informatique théorique, 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 dans le pire des cas. L'insertion et la suppression nécessitent d'effectuer des rotations. La dénomination « arbre AVL » provient des noms respectifs de ses deux inventeurs, respectivement (en) et (en), 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 calculé à partir des hauteurs respectives 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). (fr)
- En informatique théorique, 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 dans le pire des cas. L'insertion et la suppression nécessitent d'effectuer des rotations. La dénomination « arbre AVL » provient des noms respectifs de ses deux inventeurs, respectivement (en) et (en), 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 calculé à partir des hauteurs respectives 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). (fr)
|
dbo:discoverer
| |
dbo:namedAfter
| |
dbo:thumbnail
| |
dbo:wikiPageExternalLink
| |
dbo:wikiPageID
| |
dbo:wikiPageLength
|
- 6645 (xsd:nonNegativeInteger)
|
dbo:wikiPageRevisionID
| |
dbo:wikiPageWikiLink
| |
prop-fr:fr
|
- Evgueni Landis (fr)
- Georgii Adelson-Velsky (fr)
- Evgueni Landis (fr)
- Georgii Adelson-Velsky (fr)
|
prop-fr:langue
| |
prop-fr:trad
|
- Evgenii Landis (fr)
- Evgenii Landis (fr)
|
prop-fr:wikiPageUsesTemplate
| |
dct:subject
| |
rdf:type
| |
rdfs:comment
|
- En informatique théorique, 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 dans le pire des cas. L'insertion et la suppression nécessitent d'effectuer des rotations. La dénomination « arbre AVL » provient des noms respectifs de ses deux inventeurs, respectivement (en) et (en), qui l'ont publié en 1962 sous le titre An Algorithm for the Organization of Information. (fr)
- En informatique théorique, 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 dans le pire des cas. L'insertion et la suppression nécessitent d'effectuer des rotations. La dénomination « arbre AVL » provient des noms respectifs de ses deux inventeurs, respectivement (en) et (en), qui l'ont publié en 1962 sous le titre An Algorithm for the Organization of Information. (fr)
|
rdfs:label
|
- AVL tree (en)
- AVL-Baum (de)
- AVL-träd (sv)
- AVL木 (ja)
- Albero AVL (it)
- Arbre AVL (fr)
- Cây AVL (vi)
- Árvore AVL (pt)
- АВЛ-дерево (ru)
- АВЛ-дерево (uk)
|
rdfs:seeAlso
| |
owl:sameAs
| |
prov:wasDerivedFrom
| |
foaf:depiction
| |
foaf:isPrimaryTopicOf
| |
is dbo:wikiPageDisambiguates
of | |
is dbo:wikiPageRedirects
of | |
is dbo:wikiPageWikiLink
of | |
is oa:hasTarget
of | |
is foaf:primaryTopic
of | |