6 Arvore binaria

Prévia do material em texto

ÁRVORES BINÁRIAS
Árvores
ÁRVORES
Problemas de busca de dados armazenados na memória principal do computador: árvore binária de busca, árvores (quase) balanceadas como AVL, rubro-negra, etc.
Aplicações em Inteligência Artificial: árvores que representam o espaço de soluções, e.g. jogo de xadrez, resolução de problemas, etc.
No processamento de cadeias de caracteres: árvore de sufixos.
Na gramática formal: árvore de análise sintática.
APLICAÇÕES
DEFINIÇÃO
uma estrutura vazia,
 ou um elemento ou um nó chamado raiz com um número finito de árvores associadas, chamadas sub árvores da raiz.
RAIZ
SUB ÁRVORE DIREITA
SUB ÁRVORE ESQUERDA
NOMENCLATURA
PAI
FILHO
FOLHAS
NÓ INTERNO
NOMENCLATURA
NÍVEL 0
NÍVEL 1
NÍVEL 2
ALTURA DA ÁRVORE
É uma árvore ordenada de grau 2
ÁRVORE BINÁRIA
É uma árvore ordenada de grau 2 e os maiores valores se posicionam na sub árvore à direita e os menores à esquerda.
ÁRVORE BINÁRIA DE BUSCA
INSERÇÃO
A inserção acontece nas folhas.
Compare o elemento a ser inserido com a raiz da árvore.
Se elemento > raiz – insira na sub árvore da direita
Senão – insira na sub árvore da esquerda
INSERÇÃO - EXEMPLO
Inserir  4, 6, 2, 3, 1, 5 e 7.
ÁRVORE VAZIA
INSERÇÃO - EXEMPLO
Inserir  4, 6, 2, 3, 1, 5 e 7.
4
RAIZ
INSERÇÃO - EXEMPLO
Inserir  4, 6, 2, 3, 1, 5 e 7.
4
6
>
INSERÇÃO - EXEMPLO
Inserir  4, 6, 2, 3, 1, 5 e 7.
4
6
2
<
INSERÇÃO - EXEMPLO
Inserir  4, 6, 2, 3, 1, 5 e 7.
4
6
2
3
<
INSERÇÃO - EXEMPLO
Inserir  4, 6, 2, 3, 1, 5 e 7.
4
6
2
3
>
INSERÇÃO - EXEMPLO
Inserir  4, 6, 2, 3, 1, 5 e 7.
4
6
2
3
INSERÇÃO - EXEMPLO
Inserir  4, 6, 2, 3, 1, 5 e 7.
4
6
2
3
1
5
7
PERCURSO EM ÁRVORES
PRÉ ORDEM
Trata a raiz
Pré-ordem sub-árvore da esquerda
Pré-ordem sub-árvore da direita
Percurso: 4 - 2 - 1 - 3 - 6 - 5 - 7
4
6
2
3
1
5
7
1
IN ORDEM
Pré-ordem sub-árvore da esquerda
Trata a raiz
Pré-ordem sub-árvore da direita
4
6
2
3
1
5
7
PÓS ORDEM
Pré-ordem sub-árvore da esquerda
Pré-ordem sub-árvore da direita
Trata a raiz
4
6
2
3
1
5
7
REMOÇÃO
remoção de um nó folha 
os ponteiros esquerdo e direito do pai são marcados para NULL
se possui apenas um filho 
o ponteiro apropriado do pai passa a apontar para o filho 
se o nó possui dois filhos 
se um desses dois filhos não possui filhos, use esse nó para substituir o nó removido 
REMOÇÃO - EXEMPLO
Remover o nó 7
4
6
2
3
1
5
7
REMOÇÃO - EXEMPLO
Remover o nó 7
4
6
2
3
1
5
REMOÇÃO - EXEMPLO
Remover o nó 6
4
6
2
3
1
5
REMOÇÃO - EXEMPLO
Remover o nó 6
4
5
2
3
1
REMOÇÃO - EXEMPLO
Remover o nó 4
4
5
2
3
1
REMOÇÃO - EXEMPLO
Remover o nó 2
4
5
3
1
EXERCÍCIO
Insira em uma árvore binária de busca vazia, nesta ordem, os números:
1, 2, 3, 4, 5, 6, 7, 8
8
5
11
2
7
4
13