Splay Trees

Uma árvore splay é uma árvore de busca binária auto-ajustável de tal forma que os elementos acessados ​​mais recentemente, serão mais rapidamente acessados em seguida em função um rearranjo da estrutura da árvore.

Podemos executar sobre os elementos da árvore splay as seguinte operações básicas: inserção, pesquisa e remoção em tempo amortizado de O (log n).

A árvore splay foi inventado por Daniel Domingos Sleator e Robert Endre Tarjan em 1985.

Uma introdução teórica sobre as árvores Splay

No próximo post veremos a classe que implementa