Arbre splay

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant l’informatique
Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Un arbre splay est une structure de données inventée par Daniel Sleator (en) et Robert 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)).

Bibliographie[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]