Árvore Binária & AVL
Equipe:
 Felipe Pontes
 Gustavo Márcio
 Márcio de Medeiros
Árvore Binária & AVL
Sumário





Introdução
Conceitos Básicos
Algoritmos
Árvores Binárias Balanceadas e AVL
Aplicações
Introdução
Inserir em Array Ordenado:



Achar o Local da inserção: O(log N);
Inserir: Mover os elementos para frente (N/2 movimentos);
Procurar em Lista Encadeada:



Comparar cada elemento da lista: N/2 comparações;
Tempo necessário: O(N);
Solução para os problemas?


SIM!!
 ÁRVORE BINÁRIA
Árvore Binária & AVL
Sumário





Introdução
Conceitos Básicos
Algoritmos
Árvores Binárias Balanceadas e AVL
Aplicações
Conceitos Básicos








Raiz;
Caminho;
Nó;
Folha;
Pai e Filho;
Sub-árvore;
Níveis;
Árvores Binárias.
Árvore Binária & AVL
Sumário





Introdução
Conceitos Básicos
Algoritmos
Árvores Binárias Balanceadas e AVL
Aplicativos e Aplicações
Algoritmos
Inserção
Função Insere ( Elemento , Árvore )  Árvore
começar
se EvaziaArv ( Árvore )
devolver CriarArv (Árvore, NULL, NULL )
senão
começar
se ( Elemento < No ( Árvore ))
devolver CriarArv ( No ( Árvore ), Insere ( Elemento, fe ( Árvore )), fd (
Árvore))
senão
devolver CriarArv ( No ( Árvore ), fe ( Árvore ), Insere ( Elemento, fd (
Árvore ))
acabar
acabar
Algoritmos
Deleção
Função eliminar (Elemento, Árvore)  Árvore;
começar
se EvaziaArv ( Árvore )
eliminar = NULL
senão
começar
se No ( Árvore )=x
começar
se EvaziaArv (fd(a))
eliminar=fe(a)
senão
se EvaziaArv (fe(a))
eliminar=fd(a)
senão
eliminar = CriarArv (min(fd(a)),fe(a),eliminar(min(fd(a))),fd(a))
acabar
senão
começar
Se x < No(Árvore)
eliminar = CriarArv (no(a),eliminar(x,fe(a),fd(a));
senão
elimina = CriarArv (no(a),fe(a),eliminar(x,fd(a));
acabar
acabar
devolver Árvore
acabar
Algoritmos
Busca
O algoritmo de busca é idêntico ao algoritmo de inserção, com pequenas modificações:
Função Busca (Elemento, Árvore)  Árvore
começa
enquanto (Nó(Árvore) != Elemento)
se (Nó (Árvore) = NULL)
devolva NULL
se (Elemento < Nó (Árvore))
Busca (Elemento, fe(Árvore))
senão
começa
se (Elemento > Nó(Árvore))
Busca (Elemento, fd(Árvore))
Senão
começa
se (Elemento = Nó(Árvore))
devolve Nó(Árvore)
acaba
acaba
acaba_enquanto
acaba
Algoritmos
Percurso - InOrder

O percurso InOrder fará com que todos os nós sejam visitados na
ordem ascendente, baseada em seus valores chaves
Algoritmo Simplificado
1.
2.
3.
Chama a si mesmo para percorrer a subárvore esquerda do nó;
Visita o nó;
Chama a si mesmo para percorrer a subárvore a direita do nó.
Algoritmos
Percurso - PreOrder

O percurso PreOrder fará com que todos os nós sejam visitados
de modo a gerar uma expressão algebrica prefixa.
Algoritmo Simplificado
1.
2.
3.
Visita o nó;
Chama a si mesmo para percorrer a subárvore esquerda do nó;
Chama a si mesmo para percorrer a subárvore a direita do nó.
Algoritmos
Percurso - PostOrder

O percurso PostOrder fará com que todos os nós sejam visitados
de modo a gerar uma expressão algebrica posfixa.
Algoritmo Simplificado
1.
2.
3.
Chama a si mesmo para percorrer a subárvore esquerda do nó;
Chama a si mesmo para percorrer a subárvore a direita do nó.
Visita o nó;
A * (B + C)
*
+
A
B
Infixa: A*(B+C)
Posfixa: ABC+*
Prefixa: *A+BC
C
Árvore Binária & AVL
Sumário





Introdução
Conceitos Básicos
Algoritmos
Árvores Binárias Balanceadas e AVL
Aplicativos e Aplicações
Árvores Binárias Balanceadas
e AVL
Inserindo os nós 30, 20, 40, 10, 25, 35 e 50 nesta
ordem, teremos:
30
20
10
40
25
35
50
Árvores Binárias Balanceadas
e AVL
Inserindo os nós 10, 20, 30, 40 e 50 nesta ordem,
teremos:
10
20
30
40
50
Árvores Binárias Balanceadas
•
•
•
Existem ordens de inserção de nós que
conservam o balanceamento de uma árvore
binária.
Na prática é impossível prever essa ordem ou
até alterá-la.
Algoritmos para balanceamentos.
Árvores Binárias Balanceadas
•
•
•
A vantagem de uma árvore balanceada com
relação a uma degenerada está em sua
eficiência.
Por exemplo: numa árvore binária degenerada
de 10.000 nós são necessárias, em média,
5.000 comparações (semelhança com arrays
ordenados e listas encadeadas).
Numa árvore balanceada com o mesmo número
de nós essa média reduz-se a 14 comparações.
Árvores Binárias Balanceadas
•
•
Uma árvore binária balanceada é aquela na qual, para
cada nó, as alturas de suas sub-árvores esquerda e
direita diferem de, no máximo, 1.
Fator de balanceamento de um nó é a diferença entre a
altura da sub-árvore esquerda em relação à sub-árvore
direita.
FB(p) = altura(sub-árvore esquerda p) - altura(subárvore direita p)
•
Em uma árvore binária balanceada todos os Fatores de
Balanceamento de todos os nós estão no intervalo -1 <=
FB <= 1
AVL
•
•
•
Algoritmo de balanceamento de árvores
binárias.
A origem da denominação AVL vem dos seus
criadores: Adel’son-Vel’skii e Landis.
Ano de divulgação: 1962.
AVL
•
•
•
•
Inicialmente inserimos um novo nó na árvore
normalmente.
A inserção deste pode degenerar a árvore.
A restauração do balanceamento é feita através
de rotações na árvore no nó “pivô”.
Nó “pivô” é aquele que após a inserção possui
Fator de Balanceamento fora do intervalo.
AVL
•
Primeiro caso:
•
•
•
FB > 1 (subárvore esquerda maior que subárvore
direita)
E a subárvore esquerda desta subárvore esquerda é
maior que a subárvore direita dela
Então realizar uma rotação simples para a direita.
3
2
1
AVL
•
Primeiro caso:
3
2
2
1
1
3
AVL
•
Segundo caso:
•
•
•
FB < -1 (subárvore esquerda menor que subárvore
direita)
E a subárvore direita desta subárvore direita é maior
que a subárvore esquerda dela
Então realizar uma rotação simples para a esquerda.
1
2
3
AVL
•
Segundo caso:
1
2
2
1
3
3
AVL
•
Terceiro caso:
•
•
•
FB > 1 (subárvore esquerda maior que subárvore
direita)
E a subárvore esquerda desta subárvore esquerda é
menor ou igual que a subárvore direita dela
Então realizar uma rotação dupla para a direita.
1
3
2
AVL
•
Terceiro caso:
1
1
2
3
2
1
2
3
3
AVL
•
Quarto caso:
•
•
•
FB < -1 (subárvore esquerda menor que subárvore
direita)
E a subárvore direita desta subárvore direita é menor
que a subárvore esquerda dela
Então realizar uma rotação dupla para a esquerda.
3
1
2
AVL
•
Quarto caso:
3
3
2
1
2
2
1
1
3
Árvore Binária & AVL
Sumário





Introdução
Conceitos Básicos
Algoritmos
Árvores Binárias Balanceadas e AVL
Aplicações
Aplicações

Para que servem as Árvores Binárias?

Exemplos de aplicações:

Redes de Comunicação de Dados


Envio de pacotes ordenados e/ou redundantes
Codificação de Huffman

Compressão e Descompressão de arquivos
1) Redes de Comunicação



A maioria dos protocolos de comunicação
fragmenta as mensagens em pacotes que
são numerados e enviados através da rede
Não há garantia da chegada em ordem dos
pacotes
Perdas de pacotes geram novos envios e
estes podem causar duplicatas dos mesmos
Reconstrução da Mensagem

Como reconstruir a mensagem corretamente?



Descartar os pacotes repetidos
Ordenar os pacotes
Como implementar tal algoritmo?

Utilizando Árvores Binárias
Exemplo:
P3
P1 Ok
P2 ?
R
P3
A
P3
R
P2
P1
R
Ordem de Chegada:
P1
P2
B
P2
P2
P3 Ok
P3
R
P2
P1
P1
P1
R
Confirmação de envio: P1 e P3.
Reenvio de P2.
Problemas: ordens e redundância dos pacotes
Algoritmo




O primeiro pacote é colocado na raiz da
árvore. Cada pacote sucessivo é comparado
com o da raiz
Se for igual, descarta-se a réplica. Se for
menor ou maior, percorre-se os lados
esquerdo ou direito da árvore
Sub-árvore vazia implica inserção do novo
pacote
Sub-árvore não vazia implica comparação
dos pacotes com a mesma
Problemas resolvidos?

Problema da ordenação


A ordenação dos pacotes pode ser feita
trivialmente com apenas uma chamada ao
método inOrder() da árvore binária
Problema da redundância

Solucionado com o algoritmo de inserção na
árvore, visto que o pacote, antes de ser inserido,
é comparado com os demais que já se encontram
na árvore binária
2) Codificação de Huffman




Algoritmo utilizado para comprimir arquivos
Todo o algoritmo é baseado na criação de
uma Árvore Binária
Programas como Winzip e WinRAR utilizam
este algoritmo
Criado por David Huffman em 1952
Códigos e Caracteres




Caracteres são letras, números e símbolos
Códigos são seqüências de bits que podem
representar de maneira ÚNICA um caracter
b bits para representar c caracteres: c = 2b
Exemplos:
ASCII (7 bits)
7
2 = 128 caracteres
Extended ASCII (8 bits)
8
2 = 256 caracteres
Como comprimir arquivos?
No código ASCII, todos os caracteres têm um
número fixo de bits
 Números variáveis de bits implica menor
capacidade de armazenamento
 Associações com bits variáveis podem
comprimir consideravelmente o arquivo
 Como comprimir arquivos desta maneira?
 Utilizando a Codificação de Huffman!

Exemplo:

Considere o arquivo com o seguinte texto:
AAAAAAAAAABBBBBBBBCCCCCCDDDDDEE



Freqüências: A = 10; B = 8; C = 6; D = 5; E = 2
Construção da Árvore Binária
Comparação do número de bits


Tamanho Fixo (8 bits)  Total = 248 bits
Tamanho Variável  Total = 69 bits
Compressão



Depois da geração da árvore, o arquivo é
percorrido novamente e cada caracter do
arquivo é substituído pelo código binário
contido na árvore, gerando uma cadeia de bits
Criação da tabela de caracteres e códigos
binários
O que é armazenado?


Cadeia de bits gerada
Tabela de caracteres e códigos
Descompressão


Regeneração da árvore binária através da
tabela de caracteres e códigos
A cadeia de bits é percorrida e, à medida que
uma sub-cadeia é encontrada na tabela de
caracteres e códigos, a mesma é substituída
pelo caracter correspondente
Conclusões


As árvores binárias são uma das estruturas
de dados mais importantes devido a grande
aplicabilidade das mesmas.
A maioria dos algoritmos das árvores binárias
são de simples entendimento, facilitando
sobremaneira
o
desenvolvimento
de
sistemas.
Bibliografia
•
•
•
•
•
•
•
http://w3.ualg.pt/~hshah/ped/
http://www.geocities.com/grupotrees/AVL/avl.htm
http://inf.unisinos.br/~anibal/prog2avl.rtf
http://www.inf.unisinos.br/~osorio/lab2/lab2-a09b.pdf
http://www.howtodothings.com/showarticle.asp?article=313
http://www.ppgia.pucpr.br/~laplima/aulas/materia/arvbin_m.h
tml
Material disponível em http://www.gmmc.kit.net/bd
Dúvidas