Uma árvore splay (ou árvore queimada ) é uma árvore de busca binária de auto-equilíbrio com a propriedade adicional de que os elementos acessados recentemente (para adicionar, visualizar ou excluí-los) são rapidamente acessíveis. Eles, portanto, têm uma complexidade amortecida em O (log n) para operações comuns, como inserção, pesquisa ou exclusão. Assim, no caso em que as operações têm uma determinada estrutura, essas árvores constituem bancos de dados com bom desempenho, e isso permanece verdadeiro mesmo que essa estrutura seja a priori desconhecida. Essa estrutura de dados foi inventada por Daniel Sleator (in) e Robert Tarjan em 1985 .
Todas as operações comuns em estruturas de dados são seguidas por uma operação básica chamada flare ( splaying English). Alargar uma árvore ao redor de um determinado elemento envolve reorganizar a árvore de modo que esse elemento seja colocado na raiz, mantendo a estrutura ordenada da árvore. Uma maneira de conseguir isso é realizar uma pesquisa comum em uma árvore binária, memorizando o caminho seguido e, em seguida, executando uma série de rotações do eixo para trazer o elemento até a raiz. Outras implementações permitem que essas duas operações sejam realizadas em uma única passagem.
O desempenho das árvores queimadas baseia-se no fato de serem auto-otimizáveis, ou seja, os nós frequentemente utilizados ficarão mais próximos da raiz, onde podem ser acessados rapidamente. No pior caso, entretanto, a maioria das operações poderia ter complexidade linear; na prática, a maioria tem uma complexidade média logarítmica.
Trazer os nós usados com frequência para mais perto da raiz é vantajoso na maioria das situações práticas (uma propriedade chamada princípio de localidade ) e, em particular, para implementar algoritmos de cache ou coleta de lixo .
Finalmente, a ausência de dados secundários (como a altura das subárvores em árvores AVL ) permite o armazenamento de dados relativamente compacto.
A desvantagem mais óbvia dos eixos alargados é que eles podem, em alguns casos, terminar com uma altura linear em seu tamanho, o que pode afetar significativamente o desempenho de todas as operações. No entanto, uma variante aleatória permite atenuar esse defeito.
Mais sutilmente, o fato de uma simples leitura da árvore modificar sua estrutura pode representar sérias dificuldades no caso em que a base de dados representada deva ser acessada por vários clientes simultaneamente. Implementações concorrentes de adesão são então às vezes necessárias.
Para inserir um novo nó em uma árvore queimada:
Para excluir um nó, procedemos de maneira semelhante ao caso de uma árvore de pesquisa binária. Se o nó tem dois filhos, trocamos o valor deste último com seu sucessor direto em suas subárvores e tentamos deletar o nó cujo valor acabamos de trocar. Em todos os casos, iremos projetar a árvore no pai do nó excluído.
Para atingir o alargamento no nó , uma série de etapas de alargamento são realizadas, cada um aproximando- se da raiz. Para determinar qual etapa deve ser realizada, três fatores devem ser levados em consideração:
Após cada passo, terá tomado o lugar de (até terminar na raiz).
Duas operações, zig e zag, permitem então formar todas as combinações a realizar: zig, zig-zig, zig-zag, zag, zag-zag e zag-zig. Sendo os três últimos simétricos aos três primeiros, nos concentraremos neles.
ZigNo caso em que é a raiz, a árvore é girada no link entre e . Esta etapa existe apenas para gerenciar problemas de paridade e só será executada como a última operação (ou seja, após uma série de zig-zig e outros).
Zig-zigQuando e são filhos à direita (resp. Esquerda), a árvore é girada duas vezes: primeiro no link entre e , depois novamente no link entre e .
ZiguezagueQuando e são dois filhos diferentes (direito e esquerdo ou vice-versa), primeiro giramos no link entre e, em seguida, um segundo no link entre e .