Arvore Binaria de Busca

Prévia do material em texto

Estrutura de dadosEstrutura de dados
ABB ABB 
20132013
Prof Melo
Apresentação
• Técnico em Desenvolvimento de Sistemas - Ibratec, Recife-PE
• Bacharel em Sistemas de Informação – FIR, Recife-PE
• Especialista em Docência no Ensino Superior – Faculdade 
Maurício de Nassau, Recife-PE
• Mestre em Ciência da Computação – UFPE/CIN, Recife-PE
• Currículo Lattes http://lattes.cnpq.br/0759508594425296)
• Homepage https://sites.google.com/site/hildebertomelo/
Disciplinas Lecionadas
• Desenvolvimento de Aplicações Desktop
• Programação Orientada a Objetos
• Estrutura de Dados
• Tecnologia da Informação & Sociedade
• Sistemas Operacionais
• Sistemas Distribuídos
• Introdução a Informática
• Lógica de Programação
• Informática Aplicada a Saúde
• Banco de Dados
• Projeto de Banco de Dados
• Análise de Projetos Orientado a Objetos
• Programação Cliente Servidor
• Linguagens de Programação: C, C#, Pascal, PHP, ASP, Delphi, Java, JavaScript
• Programação WEB
Definição
• Representam um conjunto de elementos (nós) 
preservando a relação hierárquica entre eles.
• Formalmente, uma árvore é um conjunto finito T de 
nós, tais que:
– Existe um nó que não é subordinado a nenhum outro nó
denominado raiz da árvore.
– Os demais nós (ligados à raiz por arcos/arestas) formam 
m >= 0 conjuntos disjuntos S1 , S2 , ... , Sm , onde cada um 
destes conjuntos é uma sub-árvore.
Utilidade
• Árvores são úteis na descrição de qualquer 
estrutura que envolve hierarquia, como os 
exemplos:
–Hierarquia de cargos numa empresa;
–Precedência de operações em expressões;
–Análise sintática de textos, 
–Ontologias, etc.
Conceitos
• Os nós subordinados a um nó e ligados a ele 
por um arco são denominados os filhos
daquele nó (pai).
• Os nós subordinados a um nó são irmãos
entre si. 
• O número de filhos (sub-árvores) de um nó é
o grau daquele nó. 
• Um nó de grau zero é chamado folha ou nó
terminal (nó sem filhos). 
• O nível de um nó é a distância daquele nó até
a raiz (número de arcos que devem ser 
percorridos). 
• O nível da raiz é ZERO.
• A altura ou profundidade de uma arvore é
definida pelo nível mais alto da árvore 
acrescido de um ou o número de nós do 
maior ramo.
• Os ancestrais de um nó são os nós existentes 
entre a raiz e o próprio nó.
RAIZ
FOLHAS
Exemplo
• A: raiz da árvores;
• B, C, D, E, H: raízes de 
sub-árvores
• F, G, I, J, K, L, M: folhas
• B, C, D: irmãos, filhos 
de A
• E, F: irmãos, filhos de B
e
k
j
a
db
f
l
c
g
i
h
m
Conceitos
• São estruturas do tipo Árvore, onde há um conceito de ordem e o 
grau de cada nó é menor ou igual a dois, ou seja, cada nó tem, no 
máximo, dois filhos.
• As sub-árvores são identificadas como a da Esquerda e a da Direita.
• Árvore binária é um tipo de árvore.
A
B
A
B
A
B
A
B
A) Duas árvores iguais B) Duas árvores binárias 
diferentes
Conceitos
• As árvores binárias podem ser:
A.Árvore estritamente binária: é uma árvore binária em que cada nó
possui 0 ou 2 filhos.
B.Árvore binária completa: é uma árvore binária cujo o maior nível é o d
e onde cada folha da árvore deve estar neste nível (d) ou no nível d-1.
C. Árvore binária cheia: é uma árvore estritamente binária com 
profundidade d em que todas as folhas estão no nível d.
Exemplos
(A) (B) (C)
Percurso ou Caminhamento
• Uma operação comum é percorrer uma árvore binária, 
seja simplesmente para imprimir o valor de seus 
elementos ou para localizar um determinado elemento.
• No entanto não existe uma ordem natural de percurso 
em uma árvore. Sendo assim, são definidos três métodos 
de percurso:
• Pré-Ordem (pré-fixado)
• Em Ordem (central)
• Pós-Ordem (pós-fixado)
• Sendo esses métodos normalmente definidos 
recursivamente.
Pré-ordem (Pré-fixada)
Percurso em Pré-Ordem
1. Se árvore estiver vazia então fim.
2. Visitar o nó raiz.
3. Percorrer a sub-árvore esquerda, em pré-ordem
4. Percorrer a sub-árvore direita, em pré-ordem.
Void PreOrdem(Raiz *r){ 
If (*r != null) {
Processa (*r); {Ex:imprimir} 
PreOrdem ((*r).esq); 
PreOrdem ((*r).dir); 
} 
}
Em Ordem (Central)
Percurso Em Ordem
1. Se árvore estiver vazia então fim.
2. Percorrer a sub-árvore esquerda, em ordem 
simétrica
3. Visitar o nó raiz.
4. Percorrer a sub-árvore direita, em ordem 
simétrica. Void EmOrdem(Raiz *r){ 
If (*R != null){
EmOrdem ((*r).esq); 
Processa (*r); {Ex:imprimir} 
EmOrdem ((*r).dir); 
}
}
Pós-ordem (Pós-fixada)
Percurso em Pós-Ordem
1. Se árvore estiver vazia então fim.
2. Percorrer a sub-árvore esquerda, em pós-ordem. 
3. Percorrer a sub-árvore direita, em pós-ordem.
4. Visitar o nó raiz.
Void PosOrdem (Raiz *r){ 
If (*r != null){
PosOrdem ((*r).esq); 
PosOrdem ((*r).dir); 
Processa(*r); {Ex:imprimir} 
} 
}
Exercício
• Qual o arranjo dos nó da árvore ao lado, obtido ao percorrê-la em:
– Pré-ordem
– Ordem simétrica
– Pós-ordem
• Responda e justifique sua resposta:
– A árvore acima é uma árvore estritamente binária?
– A árvore acima é uma árvore binária completa?
– A árvore acima é uma árvore binária cheia?
• Quais os nós folhas? 
• Qual o nível de cada nó? 
• Qual a profundidade da árvore? 
• Liste os ancestrais dos nós B, H e F.
Árvore Binária de Busca (ABB)
• Árvore Binária de Busca (ABB)
–Árvores binárias organizadas para facilitar a busca 
de elementos
–Característica: chaveEsq < chaveRaiz < chaveDir
D
F
E G
B
A C
Árvore Binária de Busca (ABB)
• Definição da Estrutura de Dados
• Typedef struct Dado{
– Char nome[60];
– Int idade;
• }
• Typedef struct Raiz{
– Struct Dado dado;
– Struct Raiz *esq;
– Struct Raiz *dir;
• }
Árvore Binária de Busca (ABB)
• Operações sobre ABB
1. Criar arvore vazia 
2. Destruir a arvore
3. Verificar se a arvore está vazia
4. Inserir
5. Pesquisar
6. Alterar
7. Excluir
8. Percurso ou Caminhamento
AAB - Criar / Destruir 
• Void Criar (Raiz *r){
– r = null;
• }
• void Destruir (Raiz *r){
– if (*r “= null){
• Destruir((*r).esq); 
• Destruir((*r).dir);
• Free(*r);
– }
• }
AAB - Vazia 
• Boolean Vazia(Raiz *r){
– Boolean retorno = *r == null? True: false;
– Return retorno;
• }
AAB - Inserir 
• Void inserir(Raiz *r, Dado d){
– If(*r == null){
• *r = (*Raiz) malloc(sizeof(Raiz));
• (*r).dado = d;
– }else if((*r).dado.idade > d.idade){
• Inserir((*r).dir, d);
– }else{
• Inserir((*r).dir, d);
– }
• }
AAB - Pesquisar 
• Raiz pesquisar(Raiz *r, Dado d){
– If(*r == null){
• Return null;
– }else if((*r).idade == d.idade){
• Return *r;
– }else if((*r).dado.idade > d.idade){
• pesquisar((*r).dir, d);
– }else{
• pesquisar((*r).dir, d);
– }
• }
AAB - Alterar 
• Void alterar(Raiz *r, Dado d){
– if((*r).idade == d.idade){
• (*r).dado = d;
– }else if((*r).dado.idade > d.idade){
• pesquisar((*r).dir, d);
– }else{
• pesquisar((*r).dir, d);
– }
• }
AAB – Excluir
• Para excluir um nó de uma árvore deve-se levar em consideração que seus filhos 
devem continuar na árvore e esta deverá continuar ordenada (menor a esquerda e 
maior a direita).
• Então temos três possibilidades que devem ser tratadas separadamente, afim de 
manter intacta a estrutura da árvore binária de busca. Excluir nó que: 
– Não tenha filhos (folha):
• Exclui o nó.
– Tenha somente um dos filhos (esquerdo ou direito):
• Substitui o nó por seu filho.
• Exclui o nó.
– Tenha dois filhos:
• Substitui o nó por outro escolhido, seguindo um dos critérios:
– O menor dos maiores. 
– O maior dos menores.
• Exclui o nó.
AAB – Excluir
Void Remover (Raiz r, Dado d){
Raiz *ptr;
if(*r != null{
if((*r).dado.idade = d.idade){
if((*r).esq == null){ 
*ptr = *r;
*r = (*r).dir;
free(*ptr);
}else if((*r).dir == null){
*ptr = *r;
*r := (*r).esq;
free(*ptr);
}else{
Substituir(*r,(*r).dir);
}
}else if ((*r).dado.dade < d.idade){
Remover((*r).dir,d);
}else{
Remover((*r).esq,d);
}
}
}
AAB – Excluir
• Substitui o nó a ser excluído por outro escolhido 
seguindo um critérios do Menor dos Maiores.
Void Substituir (Raiz *raiz, Raiz *sucessor){
Raiz*ptr;
if ((*sucessor).esq == null){
(*raiz).dado = (*sucessor).dado;
*ptr = *sucessor;
*sucessor = (*sucessor).dir;
free(*ptr);
}else{
Substituir(*raiz,(*sucesso).esq);
}
}
Degeneração (ABB)
• Diferenças muito grande de alturas entre 
sub-àrvores de um nó causando a perda de 
eficiência.
D
F
G
B
I
M
Técnicas de Balanceamento
• Estático : Baseia-se na reorganização total 
dos elementos da árvore em um momento 
apropriado.
• Dinâmico : À medida que os elementos são 
inseridos, a árvore vai sendo balanceada, 
obrigando uma reorganização de seus 
elementos. 
Balanceamento Estático
• Construção de um array com todos os elementos da 
árvore através de um percurso em ordem simétrica.
• Leitura do array de forma semelhante a pesquisa binária 
para a construção de uma nova árvore balanceada.
D
F
G
B
I
M
B D F G I M
Balanceamento Dinâmico (AVL)
• Conceito menos rigoroso sobre o balanceamento, introduzido em 1962 por dois 
matemáticos russos (Adelson e Landis).
• Uma árvore é considerada balanceada se para qualquer nó da árvore, as alturas das sub-
árvores à esquerda e à direita diferem de no máximo de 1.
• Esta diferença é chamada de fator de balanceamento:
– FatBal(n) <= -1, significa que a altura da árvore à esquerda de n é maior que à da direita
– FatBal(n) >= +1, significa que a altura da árvore à esquerda de n é menor que à da direita
– FatBal(n) = 0, significa que a altura da árvore à esquerda de n é igual à da direita
-1
-1
0
+1
0 +1
0
Balanceamento Dinâmico (AVL)
• Após a inserção de um novo nó deve-se recalcular os fatores de 
balanceamento.
• Se houve para um dado nó |FatBal(n)| > 1 então deve-se 
rebalancear a árvores através do roteamento dos nós.
• Neste processo temos dois nós muitos importantes:
– A: Nó ancestral mais próximo do nó inserido com FatBal (n) <> 0 antes da 
inserção.
– B: Filho de A na sub-árvore onde ocorreu a inserção
Perguntas...
Bibliografia
• Livro(s) Texto(s):
• PREISS, Bruno R. Estrutura de Dados e 
Algoritmos. Rio de Janeiro: Campus, 2001.
• PEREIRA, Silvio L. Estruturas de dados 
fundamentais. São Paulo: Érica, 2000.
• AZEREDO, Paulo A. Métodos de 
Classificação de Dados e Análise de suas 
Complexidades. Rio de Janeiro: Campus, 
1995.
• http://www.nuperc.unifacs.br/
Bibliografia
• Livros de referencia:
• WEISS, M. A. Data structures and algorithm 
analysis in C++. California: Benjamin/Cummings, 
1999.
• SEDGEWICK, R. Algorithms in C++: Fundamentals, 
data structures, sorting, searching. New York: 
Addison-Wesley, 2001.
• TANENBAUM, Aaron; LANGSAM, Y. & 
AUGENSTEIN, M. Estruturas de Dados usando C. 
São Paulo: Makron Books, 1995.
• LAFORE, R. Aprenda em 24 horas estrutura de 
dados e algoritmo. Rio de Janeiro: Campus, 1999.
• MORAES, Celso R. Estruturas de Dados e 
Algoritmos. São Paulo: Berkeley Brasil, 2001.