Árvore Binária e Hash

Árvores
Árvore
Árvore Binária
Árvore Binária de Pesquisa
1

Árvores – Conceito


Um conjunto finito de um ou mais nós, em que:  Existe

um nó especial chamando raiz
 Os nós restantes são particionados em n conjuntos disjuntos T0, T1 … TN que são chamados de sub-árvores da raiz.

2

Árvores – Conceito
Raiz

T1

T2

3

Árvores – Motivação
ADT (Abstract Data Types)
 Filas de prioridade ou Dicionários
 Suportam operações de Pesquisa,
Mínimo, Máximo, Predecessor, Sucessor,
Inserção e Remoção


4

Árvores – Motivação


Exemplos da vida real:
 Avaliação

de expressões matemáticas por um compilador;  Pesquisa eficiente de elementos de uma coleção de funcionários por um programa de folha de pagamento;  Bancos de dados;
 Árvores de Decisão em sistemas de suporte a decisão de IA (ex: sistemas médicos especialistas);
 Jogos de Xadrez ou Damas.
5

Definições
Grau de um nó
 Grau de uma árvore
 Nível de um nó
 Áltura de uma árvore


6

Árvores Binárias





Um conjunto finito de nós em que cada nó assume grau zero, grau um ou grau dois
O grau de um nó não pode exceder o valor dois
Um nó com somente um filho em sua sub-árvore esquerda é diferente de um nó com somente um filho em sua sub-árvore direita

7

Árvores Binárias – Exemplo

8

Árvores Binárias – Exemplo (2)

9

Árvores Binárias
O nível i de uma árvore tem no máximo 2i nós  Uma árvore de altura h tem no máximo
(2h) – 1 nós


10

Árvore Binária Cheia

11

Árvore Binária Cheia
Uma árvore binária esta cheia se cada nível i possui 2i nós
 Logo, uma árvore binária cheia de altura h possui 2h –1 nós


12

Árvore Binária Completa

13

Árvore Binária Completa


Uma árvore binária completa esta cheia até o nível h-1, e o nível h é preenchido da esquerda para a direita



nós em uma árvore binária completa correspondem aos nós numerados de 1 a n em uma árvore binária cheia