Splay Tree
Eu resolvi estudar essa estrutura de dados porque ela foi utilizada pelo Daniel Zerbino no Velvet e segundo ele: "Although theoretically less efficient, they are much easier to implement and have proven in practice as efficient as other forms of binary search trees. This solution, although memory costly, proved robust even with very large datasets. The processing of reads was thus greatly accelerated and large datasets (up to 500.000.000 Illumina reads) could be hashed in a matter of hours instead of days." Fonte: ZERBINO (2009, Genome assembly and comparison using de Bruijn graphs). Vantagens São mais fáceis de implementar que outras técnicas de árvores binárias (BST); Requer menor espaço de memória que as Vermelha e Preto ou AVL (quando não for necessário informação de balanceamento). Desvantagens maior número de ajustes locais, durante a busca Após o acesso a todos os elementos da árvore, a ordem reduz a uma lista encadeada O(n), o que corresponde ao pior ...