Avaliação da eficácia da pesquisa de árvores AVL

́

Arvores

de Pesquisa

Amilton Rodrigues Nunes

DQE - Departamento de Qu ́ımica e Exatas

CSI - Colegiado de Sistemas de Informac ̧ a ̃ o

Universidade Estadual do Sudoeste da Bahia

Jequi ́e, Brasil

Email: [e-mail]

Abstract—This paper aims to show an evaluation of the

research performance of AVL tree. ou folha(de agora em diante n ̃ao haver ́a distinc ̧ a ̃ o entre esses

dois termos). Os outros n ́os s ̃ao chamados n ́os internos.

Abstract—Esse trabalho tem como objetivo mostrar uma

avaliac ̧ a ̃ o do desempenho de pesquisa da arvore AVL. Uma a ́ rvore bin ́aria de pesquisa e ́ uma a ́ rvore bin ́aria

em que todo n ́o interno cont ́em registro,e, para cada n ́o,

a seguinte propriedade e ́ verdadeira: todos os registro com

chaves menores est ̃ao na sub ́arvore esquerda e todos registros

om chaves maiores est ̃ao na sub ́arvore direita.

I.

̃

I NTRODUC ̧ AO

Esse trabalho foi proposto pela disciplina de algoritmos

e estrutura de dados 2 do curso de Sistemas de informac ̧ a ̃ o,

o trabalho consiste em um algoritmo de pesquisa de dados

(codificador/decodificador) usado estrutura de dados a ́ rvore

bin ́arias de pequisa com balanceamento( ́arvore AVL) para

armazenar as chaves contendo os conjuntos de caracteres do

codigo morse e do alfabeto.

II.

̃

I MPLEMENTAC ̧ AO

Pesquisa Bin ́aria A a ́ rvore de pesquisa e ́ uma estrutura

de dados muito eficiente para armazenar informac ̧ a ̃ o. Ela e ́

particularmente adequado quando existe necessidade de con-

siderar todos ou alguma combinac ̧ a ̃ o de requisitos, tais como:

(i) acessis direto e sequencial eficientes; (ii) facilidade de

inserc ̧ a ̃ o e retirada de registros; (iii) boa taxa de utilizac ̧ a ̃ o

de mem ́oria; (iv) utilizac ̧ a ̃ o de mem ́oria primaria e secundaria.

Se alg ́em considerar separadamente qualquer um dos requi-

sitos no par ́agrafo anterior, e ́ possivel encontrar uma estrutura

de dados que seja superior a ` a ́ rvore de pesquisa. Por exemplo,

tabelas hashing possuem tempos m ́edios de pesquisa melhores

e tabelas que usam posic ̧ o ̃ es cont ́ıguas de mem ́oria possuem

melhores taxas de utilizac ̧ a ̃ o de mem ́oria. Entretanto, uma

tabela que usa hashing precosa ser ordenada se existir neces-

sidade de provessar os registros sequencialmente em ordem

lexicogr ́afica, e a inserc ̧ a ̃ o/retirada de registros em tabelas

que usam posic ̧ o ̃ es cont ́ıguas de mem ́oria tem custo alto. As

a ́ rvores de pesquisa representam um compromisso entre esses

requisitos conflitantes.

́

Arvores

Bin ́arias de Pesquisa Sem Balanceamento de

acordo com Knuth(1997, p. 312), uma a ́ rvore bin ́aria e ́

definida como um conjunto finito de n ́os que ou est ́a vazio ou

consistem de um n ́o chamdo raiz mais os elementos de duas

a ́ rvores bin ́arias distintas chamadas de sub ́arvores esquerda e

direita do n ́o raiz. Emm uma a ́ rvore bin ́aria, cada n ́o tem no

m ́aximo duas sub ́arvores.

Existem referˆencias para as sub ́arvores esquerda e direita

em cada n ́o. O n ́umero de sub ́arvores de um n ́o e ́ chamado de

grau daquele n ́o. Um n ́o de grau zero e ́ chamado de n ́o externo

O n ́ıvel do n ́o raiz e ́ 0; se um n ́o est ́a no n ́ıvel i entc ̧ai a

raiz de suas sub ́arvores est ́a no n ́ıvel i + 1. A altura de um

n ́o e ́ o comprimento do caminho mais longe deste n ́o ate um

n ́o folha. A altura de uma a ́ rvore e ́ a altura do n ́o raiz.

Um m ́etodo de pesquisa para uma a ́rvore bin ́aroa de

pesquisa e ́ bastante simples. Para encontrar o registro que

cont ́em a chave de busca passada como parˆametro. Primeiro

compare a chave de busca com a chave do registro que est ́a

na raiz. S ́e e ́ menor, v ́a para a sub ́arvore esquerda; se e ́ maior,

v ́a para a sub ́arvore direita. Repita o processo recursivamente,

at ́e que a chave procurada seja encontrada ou ent ̃ao um n ́o

folha seja atingido. Se a pesquisa tiver sucesso, etn ̃ao o registro

contendo a chave passada e ́ o retorno.

Atingir uma referˆencia null em um processo de pesquisa

significa uma