a rvores Pesquisa Bin rias

Estruturas de Informação ----- Árvores Binárias de Pesquisa
_____________________________________________________________________________________

ÁRVORES BINÁRIAS DE PESQUISA
Árvores binárias de pesquisa são uma estrutura alternativa do tipo árvore binária, para guardar valores de tal forma que a recuperação dos mesmos pode ser efectuada de forma ordenada.
Assim, cada nó interno de uma árvore binária de pesquisa obedece aos seguintes critérios: -

Cada elemento tem uma chave, não existem chaves repetidas
As chaves da subárvore esquerda (também árvore binária de pesquisa), de um qualquer nó considerado como raiz, são menores do que a chave dessa raiz
- As chaves da subárvore direita (também árvore binária de pesquisa), de um qualquer nó considerado como raiz, são maiores do que a chave dessa raiz
Abaixo representa-se uma árvore binária de pesquisa de inteiros. Nessa árvore cada nó conterá, além dos dois apontadores respectivamente para a subárvore esquerda e subárvore direita, um campo informação, designado por info e que no exemplo é ao mesmo tempo a chave.

Como se vê cada um dos nós internos segue os critérios anteriormente enunciados.
Verificamos também que se percorrermos uma árvore deste tipo, utilizando uma visita simétrica, obteremos os valores das chaves ordenados de forma crescente.
Assim a árvore acima representada dará origem à seguinte lista de valores:
60 70 75 80 85 90 95.
Seguidamente desenvolveremos os algoritmos de manipulação deste tipo de estrutura, nomeadamente, o pesquisar, o inserir novo nó e eliminar um determinado nó dado pela chave. É evidente que os dois últimos algoritmos farão alterações à árvore , mas a nossa estrutura ter-se-á que manter binária de pesquisa

_____________________________________________________________________________________
Departamento de Engª Informática do ISEP
1

Estruturas de Informação ----- Árvores Binárias de Pesquisa
_____________________________________________________________________________________