Arbre splay
Un article de Wikipédia, l'encyclopédie libre.
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 prend un temps O (n ln (n) + m ln (n)).
Cette structure est très performante si les accès aux données ne sont pas uniformes.
