Arbre splay

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

Articles connexes[modifier | modifier le code]