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

Share the article and excerpts

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