Informatica

Trabalho de algoritmo

Arvores balanceada e desbalanceada

Manaus 11 de novembro de 2010

Trabalho de algoritmo

Ciência da computação

Manaus 11 de novembro de 2010
Introdução

A abordagem deste trabalho é sobre árvores binárias “ Balanceada e Desbalanceada ’’,

o objetivo deste trabalho é comparar árvore balanceada e árvore desbalanceada, no

momento da Inserção, Busca e Remoção.

Comparado o tempo nos três quesitos ver se realmente é bom manter uma arvore

balanceada durante a inserção e remoção, ou se uma arvore desbalanceada tem mais

vantangem em relação a balanceada.

Árvores Binárias de Pesquisa sem Balanceamento

Conceito básico

A árvore de pesquisa é uma estrutura de dados muito eficiente para armazenar

informação.

A arvore binária é um método de pesquisa usado para memória primaria, muito usada

por que tem um custo muito bom sendo caso medio O(logn).

Operações

Inserção.

Na arvore binária tem um no raiz, e se for inserido mais elementos, e se o elemento

inserido for menor que a raiz, item inserido na esquerda, caso contrario na direita.

Conceito básico de arvore binária de busca.

Busca.

Compare o elemento de busca com a chave que estar na raiz, caso seja menor vai para a

subarvore esquerda, caso seja maior vai para a subarvore direita.

De forma recursiva repita a busca ate que o elemento seja encontrado ou um no folha,

Neste caso a pesquisa foi um sucesso. Caso contrario se encontrar um ponteiro nulo a

Pesquisa sem sucesso.

Remoção.

A retirada de um registro não é tão simples quanto a inserção.

Para a remoção de um nó de uma árvore deve-se levar em consideração que seus filhos

devem continuar na árvore e esta deverá continuar