Arbre splay
- Arbre splay
-
Un arbre splay est une structure de données inventée par Sleator et Tarjan en 1985.
Cette structure de données est essentiellement un arbre binaire avec des règles spéciales de mise à jour et d'accès. L'opération splay sur une valeur fait remonter le nœud visé à la racine de l'arbre tout en conservant son ordonnancement.
De plus, m opérations sur un arbre de n nœuds prennent un temps O (n ln (n) + m ln (n)).
Voir aussi
Articles connexes
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Arbre splay de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Arbre Splay — Un arbre splay est une structure de données inventée par Sleator et Tarjan en 1985. Cette structure de données est essentiellement un arbre binaire avec des règles spéciales de mise à jour et d accès. L opération splay sur une valeur fait… … Wikipédia en Français
Arbre Andelson-Velskii et Landis — Arbre AVL Pour les articles homonymes, voir AVL. Un exemple d arbre non AVL. En informatique, les arbres AVL ont été his … Wikipédia en Français
Arbre avl — Pour les articles homonymes, voir AVL. Un exemple d arbre non AVL. En informatique, les arbres AVL ont été his … Wikipédia en Français
Arbre Bicolore — Un arbre bicolore ou arbre rouge et noir est un type particulier d arbre binaire de recherche, qui est une structure de données utilisée en informatique théorique. Les arbres bicolores ont été inventés en 1972 par Rudolf Bayer qui les nomma… … Wikipédia en Français
Arbre rouge-noir — Arbre bicolore Un arbre bicolore ou arbre rouge et noir est un type particulier d arbre binaire de recherche, qui est une structure de données utilisée en informatique théorique. Les arbres bicolores ont été inventés en 1972 par Rudolf Bayer qui… … Wikipédia en Français
Arbre rouge et noir — Arbre bicolore Un arbre bicolore ou arbre rouge et noir est un type particulier d arbre binaire de recherche, qui est une structure de données utilisée en informatique théorique. Les arbres bicolores ont été inventés en 1972 par Rudolf Bayer qui… … Wikipédia en Français
Arbre Binaire De Recherche — Exemple représentant un arbre binaire de recherche En informatique, un arbre binaire de recherche (ABR) est un arbre binaire dans lequel chaque nœud possède une clé, telle que chaque nœud du sous arbre gauche ait une clé inférieure ou égale à… … Wikipédia en Français
Arbre AVL — Pour les articles homonymes, voir AVL. Un exemple d arbre non AVL. En informatique théorique, les arbres AVL ont été historiquement les premiers arbre … Wikipédia en Français
Arbre binaire de recherche — Pour les articles homonymes, voir Arbre (homonymie). Exemple représentant un arbre binaire de recherche En informatique, un arbre binaire de recherche (ABR) est un … Wikipédia en Français
Arbre bicolore — Un arbre bicolore ou arbre rouge et noir est un type particulier d arbre binaire de recherche, qui est une structure de données utilisée en informatique théorique. Les arbres bicolores ont été inventés en 1972 par Rudolf Bayer qui les nomma… … Wikipédia en Français