dasdsa

´
UM ESTUDO DAS ESTRUTURAS EM ARVORES E SEU
DESEMPENHO PARA DADOS DO TIPO STRING
Aluno: Henrique C´sar Silva e Orientador: Michel Pires da Silva

Resumo
´
Este trabalho apresenta um estudo sobre a estrutura de Arvores em algoritmos. Estas arvores foram implementadas na linguagem Pascal, onde foram realizados os testes de cada
´
estrutura em uma base de dados de palavras de um dicion´rio de inglˆs, todas dispostas no a e arquivo do tipo ”.txt”de forma aleat´ria e atrav´s dos m´todos, as palavras s˜o inseridas o e e a nas arvores, e realizados testes a fim de compararmos a complexidade de se pesquisar nestas
´
estruturas.

1. Introdu¸˜o ca Com fins de analizarmos a complexidade de uma estrutura em arvore foram estudados
´
4 tipos diferentes. Os testes de cada estrutura foram feitos atrav´s de um arquivo ”.txt”, e onde se encontram 1.000 palavras, essas palavras foram passadas para um vetor, e tamb´m e inseridas nas arvores. Foram buscadas 10 palavras no vetor, computado a quantidade de
´
compara¸oes para encontrar cada uma e feito uma m´dia. Atrav´s do m´todo de pesquisa c˜ e e e de cada ´rvore foram buscadas as mesmas 10 palavras, calculado o tempo de m´quina, e a a tamb´m calculado a m´dia de compara¸oes para encontrar as 10 palavras de cada estrutura e e c˜ em quest˜o. a ´
2. Contextualiza¸˜o sobre as Arvores ca ´
2.1. Arvore Bin´ria a Trata-se de uma estrutura onde os itens s˜o organizados atrav´s de um dado unico a a e
´
cada elemento(chave). Na inser¸ao de elementos na arvore bin´ria, o primeiro elemento da c˜ ´ a estrutura ´ chamado raiz, onde esta raiz pode possuir at´ dois filhos, esquerdo e direito. e e
O filho esquerdo ´ o item que tˆm chave menor e o item direito possui chave maior que a e e
´
raiz. As pr´ximas inser¸oes na Arvore s˜o feitas de forma respectiva.Todo item inserido na o c˜ a arvore ´ chamado de n´ ,cada n´ pode possuir at´ 2 filhos, e os itens mais abaixo e que
´
e o o