Paginaçao

Um Algoritmo para Paginação de Árvores Binárias
Baseado em Empacotamento Unidimensional

Ricardo Toledo Dias
Rodrigo Toledo Dias
Universidade Federal do Rio de Janeiro
Escola Politécnica – MBA em Engenharia de Software
EEL 650 – Análise e Implementação de Algoritmos
Turma ENGSOFT07 – Prof. Heraldo L. S. Almeida

Resumo
Este trabalho apresenta um novo algoritmo para paginação de árvores binárias de pesquisa que frequentemente ocorrem em biologia computacional. O algoritmo visa reduzir o número de páginas visitadas em pesquisas e aumentar a taxa de preenchimento das páginas utilizadas. O algoritmo constrói a paginação ótima quando possível e, utilizando empacotamento unidimensional, apresenta uma política eficiente para o preenchimento das páginas de árvores binárias desbalanceadas. A complexidade computacional do algoritmo é apresentada. O algoritmo foi implementado e resultados experimentais, comparativos com outras estratégias de paginação são apresentados. A comparação mostrou que a abordagem proposta é a única que apresenta, simultaneamente, a quantidade média de páginas acessadas em pesquisas e a taxa de preenchimento das páginas próximas do ótimo.

Introdução
As árvores binárias são estruturas de dados que permitem a realização de busca ou pesquisa de forma eficiente [1]. Uma árvore binária pode atingir grandes dimensões, bem como ser utilizada para armazenar dados em memória secundária ou distribuídos pelos nodos de uma rede de computadores.
Muitas aplicações em biologia computacional envolvem o processamento de strings utilizando árvores binárias não balanceadas [2]. Tais árvores são originadas de seqüências biológicas que não podem ser balanceadas, por isso, árvores B não podem ser aplicadas [3]. Nestes casos, é necessário definir uma estratégia eficiente para o acesso aos dados da árvore, que são organizados em páginas. Uma página é utilizada para a transferência de dados em blocos da memória secundária para a primária, além do acesso