Autor: Bruno Armond Braga
Orientadora: Cristina Gomes Fernandes
Universidade de São Paulo - Instituto de Matemática e Estatística
Resumo
Árvores Binárias de Busca (ABBs) são estruturas de dados que armazenam um conjunto de chaves de um universo estático, que possui uma ordem total, e dão suporte a buscas neste conjunto. Essas estruturas são fundamentais para o universo da computação.
Padrões de acesso do mundo real muitas vezes possuem estruturas repetitivas, como por exemplo bancos de dados que recebem solicitações frequentes para um pequeno número de elementos de alto tráfego. Nesse estudo estaremos interessados em explorar as delimitações de custo dos algoritmos de busca em ABBs.
Apesar de existirem ABBs muito bem documentadas com tempo por busca logarítmico no número de chaves armazenadas, essas estruturas normalmente não conseguem alcançar uma eficiência superior a isso independentemente da entrada.
ABBs online são ABBs que apenas possuem informações sobre os acessos passados. Ou seja, ao fazer a busca, o algoritmo de busca não tem conhecimento das próximas buscas, nem mesmo de quantas buscas ocorrerão.
Seja OPT(X) o menor custo possível de algum algoritmo de busca em ABB que acessa todas as chaves da entrada X. Uma ABB online é dinamicamente ótima se, para todas as sequências X, seu algoritmo de busca tem custo O(OPT(X)). Considera-se que não estão ocorrendo inserções ou remoções no conjunto durante estes acessos.
Todo esse estudo é feito para tentar responder à pergunta: "Existe uma ABB online dinamicamente ótima?"
Uma das tentativas de responder tal pergunta foi a árvore splay de Sleator e Tarjan. Árvores splay são ABBs que seguem a heurística "move to front". Assim, após cada acesso, a árvore se reestrutura de uma maneira particular, trazendo o nó da chave que foi acessada para a raiz da árvore.
Há uma conjectura não resolvida que diz que as árvores splay são dinamicamente ótimas. Essa conjectura ficou conhecida como a Conjectura da Otimalidade Dinâmica.