Arvores_AVL_B

Prévia do material em texto

1
Árvores Binárias
Balanceadas
Elisa Maria Pivetta Cantarelli
elisa@fw.uri.br
Árvores Balanceadas
{ Uma árvore é dita balanceada quando as suas sub-
árvores à esquerda e à direita possuem a mesma
altura.
{ Todos os links vazios estão no mesmo nível, ou seja,
que a árvore está completa.
{ A árvore que não está balanceada, define-se como
degenerada
{ Árvore binária
balanceada.
c
b d
a
f
g
e
(b)
{ Árvore binária
Degenerada
d
b f
a
c e g
(a)
d
b f
a
c e g
(c)
h
{ Árvore binária
Incompleta
Balanceada
2
Árvores Balanceadas
{ Balanceamento Estático
z O balanceamento estático de uma árvore binária consiste
em construir uma nova versão, reorganizando-a.
{ Balanceamento Dinâmico: AVL
{ Árvore AVL em homenagem aos matemáticos russos (Adelson-
Velskii e Landism -1962)
{ Uma árvore AVL é uma árvore binária de pesquisa onde a
diferença em altura entre as subárvores esquerda e direita é no
máximo 1 (positivo ou negativo).
{ A essa diferença chamamos de “fator de balanceamento” de n
(FatBal (n)).
{ Essa informação deverá constar em cada nó de uma árvore
balanceada
Árvores AVL
{ Assim, para cada nodo podemos definir um
fator de balanceamento (FB), que vem a ser
um número inteiro igual a
FB(nodo p) = altura(subárvore direita p) - 
 altura(subárvore esquerda p)
O Fator de uma folha é sempre Zero (0)
3
Árvores Balanceadas
{ Exemplos de árvores AVL e árvores não-AVL.
{ Os números nos nodos representam o FB para cada nodo.
{ Para uma árvore ser AVL os fatores de balanço devem ser necessariamente -1, 0,
ou 1.
Exemplos de árvores AVL
Exemplos de árvores não AVL
BALANCEAMENTO DE
ÁRVORES AVL
{ Inicialmente inserimos um novo nodo na árvore.
{ A inserção deste novo nodo pode ou não violar a
propriedade de balanceamento.
{ Caso a inserção do novo nodo não viole a propriedade
de balanceamento podemos então continuar inserindo
novos nodos.
{ Caso contrário precisamos nos preocupar em restaurar o
balanço da árvore. A restauração deste balanço é
efetuada através do que denominamos ROTAÇÕES na
árvore.
4
Árvores AVL
{ Se quisermos manter a árvore
balanceada a cada inserção, devemos ter
um algoritmo que ajuste os fatores de
balanceamento
{ O algoritmo corrige a estrutura através
de movimentação dos nós, ao que
chamamos de “rotação”.
BALANCEAMENTO DE
ÁRVORES AVL
Exemplos
{ Vamos considerar a seguinte árvore (os números ao lado
dos nodos são o FB de cada nodo):
•A árvore acima está balanceada, como podemos observar
pelos FB de cada nodo.
•Os casos possíveis de desbalanceamento são 2. Veremos
cada um deles.
5
{ Ao inserir o número 5 na árvore. Esta inserção
produziria a seguinte árvore:
•O nodo 8 fica com o FB -2 e tem um filho com FB +1. Neste caso o
balanceamento é atingido com duas rotações, também denominada
ROTAÇÃO DUPLA.
•Primeiro rotaciona-se o nodo com FB 1 para a esquerda.
Tipo 1 - ROTAÇÃO DUPLA
Tipo 1 - ROTAÇÃO DUPLA
A seguir rotaciona-se o nodo que tinha FB -2 na direção oposta
(direita neste caso).
A árvore fica:
6
Tipo 1 - ROTAÇÃO DUPLA
•Os FB nos nodos voltaram a ficar dentro do esperado das árvores AVL.
•O caso simétrico ao explicado acima acontece com os sinais de FB
trocados, ou seja, um nodo com FB +2 com um filho com FB -1. Também
utilizariamos uma rotação dupla, mas nos sentidos contrários, ou seja, o
nodo com FB -1 seria rotacionado para a direita e o nodo com FB +2 seria
rotacionado para a esquerda.
A árvore fica:
Tipo 2 - ROTAÇÃO Simples
Suponha que queremos inserir o nodo 3 na árvore inicial.
A inserção produziria a seguinte árvore:
• A inserção do nodo 3 produziu um desbalanço no nodo 8 verificado pelo FB -2
neste nodo.
•Neste caso, como os sinais dos FB são os mesmos (nodo 8 com FB -2 e nodo 4
com FB -1) significa que precisamos fazer apenas uma ROTAÇÃO SIMPLES à
direita no nodo com FB -2.
• No caso simétrico (nodo com FB 2) faríamos uma rotação simples à esquerda.
7
Tipo 2 - ROTAÇÃO Simples
Observe que os FB estão dentro do esperado para mantermos a propriedade de
balanceamento de árvores AVL.
Após a rotação simples a árvore ficaria:
A descrição do algoritmo em pseudo-código para construção
de uma árvore AVL:
{ 1. Insira o novo nodo normalmente (ou seja, da mesma maneira que
inserimos numa ABB);
{ 2. Iniciando com o nodo pai do nodo recém-inserido, teste se a
propriedade AVL é violada neste nodo, ou seja, teste se o FB deste
nodo é maior do que abs(1). Temos aqui 2 possibilidades:
z 2.1 A condição AVL foi violada
{ 2.1.1 Execute as operações de rotação conforme for o caso (Tipo 1
ou Tipo 2)
2.1.2 Volte ao passo 1
z 2.2 A condição AVL não foi violada.
{ Se o nodo recém-testado não tem pai, ou seja, é o nodo raiz da
árvore, volte para inserir novo nodo (Passo 1)
8
Dicas: Árvores AVL
1. Para identificarmos quando uma rotação é
simples ou dupla observamos os sinais de
FatBal:
• se o sinal for igual, a rotação é simples.
• se o sinal for diferente a rotação é dupla.
2. Se FB+ rotação para esquerda
3. Se FB- rotação para direita
Exercícios
9
Exercício 1
{ Considere a inserção dos seguintes
valores (nesta ordem) em uma
árvore AVL: 5,3,8,2,4,7,10,1,6,9,11.
Para essas inserções nenhuma
rotação é necessária. Desenhe a
árvore AVL resultante e determine o
fator de balanceamento de cada nó.
Exercício 2
Construir uma árvore AVL com os seguintes dados:
• Inserir inicialmente 10, 20, 30
• Se necessário fazer balanceamento
• Inserir 25 e 27
• Se necessário fazer balanceamento
10
Resolução do Exercício 2
A inserção dos 3 primeiros números resulta na seguinte árvore: 
Após a inserção do elemento 30 a árvore fica desbalanceada. O
caso acima é do Tipo 2. Fazemos uma rotação para a esquerda
no nodo com FB 2. A árvore resultante fica:
10
20
30
+2
+1
0
20
3010
0
0 0
Resolução do Exercício 2
• O passo seguinte é inserir os nodos 25
e 27. A árvore fica desbalanceada
apenas após a inserção do nodo 27
• Este caso é do Tipo 1.
• O nodo 30 tem FB -2 e o seu nodo filho
tem FB 1. Precisamos efetuar uma
rotação dupla, ou seja, uma rotação
simples à esquerda do nodo 25,
resultando:
20
3010
+2
0 -2
25
27
+1
0
20
3010
+2
0 -2
27
25
-1
0
11
Resolução do Exercício 2
• seguida de uma rotação simples à
direita do nodo 30, resultando:
e a árvore está balanceada.
20
2710
+1
0 0
25 300 0
Exercício 3
{ Determinado sistema armazena
registros por chaves numéricas em
uma árvore AVL. Nessa árvore são
inseridos os seguintes valores:
20,10,5,30,25,27 e 28 nessa
ordem. Apresente passo a passo
como a árvore vai sendo
construída. Realize as rotações
necessárias e indique qual rotação
foi realizada em cada caso.
12
Resolução: Exercício 3
1) Inserção das chaves 20 e 10, nessa ordem
{ A árvore ficou pendendo para a esquerda
{ O fator de balanceamento do nó cuja chave é
20 é -1.
{ O fator de uma folha é sempre 0 (zero).
2) ...Continuar as inserções
20
10
(-1)
(0)
Árvores Multivias (Multiway tree)
13
Árvores Multivias
{ Em uma árvore binária, cada nó possui um
item de dado e pode ter até dois filhos.
{ Se permitirmos o uso de mais itens de dados
e filhos por nó, o resultado é uma árvore
Multivias ou M-vias (multiway tree).
{ Uma Estrutura Multivia com algoritmo
eficiente deve considerar:
z Tempo de acesso a cada nó
z Balanceamento da árvore.
{ As árvores 2-3-4, são árvores multivias que
podem ter até quatro filhos e três itens de
dados por nó.
Árvores 2-3-4
{ Árvores 2-3-4 são interessantes por
várias razões:
z São árvores balanceadas.
z Fáceis de programar.
z Servem como uma introdução para
árvores B.
14
Árvores 2-3-4
{ A figura mostra uma pequena árvore 2-3-4.
{ Cada nó pode conter um, dois ou três itens
de dados.
50
30 60 70 80
10 20 5540 62 64 66 75 83 86
Árvores 2-3-4
{ Um nó interno deve sempre ter um filho a
mais que seus itens de dados.
{ Um nó folha, ao contrário, não possui filhos,
mas ele pode conter um, dois ou três itens
de dados. Nós vazios não são permitidos.
{ Devido a uma árvore 2-3-4 possuir nós
com até quatro filhos, ela é chamada de
árvore multivias de ordem4 (multiway
tree of order 4).
15
Árvores 2-3-4
{ O 2, 3 e 4 no nome árvore 2-3-4 referem-se a quantos
links para filhos podem potencialmente estar contidos em
um dado nó.
{ Para nós internos (não folhas), três combinações são
possíveis:
z um nó com um item de dado sempre possuirá dois
filhos;
z um nó com dois itens de dados sempre possuirá três
filhos;
z um nó com três itens de dados sempre possuirá quatro
filhos.
50
30 60 70 80
10 20 5540 62 64 66 75 83 86
Árvores 2-3-4
Por que uma árvore 2-3-4
não é chamada de árvore
1-2-3-4?
{ Um nó não pode ter somente um filho, como
os nós na árvore binária
{ Um nó com um item de dado precisa sempre
ter dois links, a menos que seja uma folha,
neste caso, ele não possui links.
16
Árvores 2-3-4
{ Um nó com dois links é chamado 2-nós,
{ Um nó com três links é chamado 3-nós
{ Um nó com quatro links é chamado 4-nós
25
12 33 37
0 1 Í 2-nós
83
40 62
27 33 51 55 59
0 1
Í 3-nós
2
100 10578
50 75 95
30 35 55
0 1
Í 4-nós
2 3
Árvores 2-3-4 X Árvore Binária
{ Em uma árvore binária, todos os filhos
com chaves menores que a chave do
nó estão “enraizados” no nó filho à
esquerda, e todos os filhos com
chaves maiores ou iguais a chave do
nó estão “enraizados” no nó filho à
direita.
{ Na árvore 2-3-4 o princípio é o mesmo,
mas existe algo mais:
17
Árvores 2-3-4
{ todos os itens de dados na sub-árvore “enraizada” no
filho 0, possuem valores menores do que a chave 0;
{ todos os itens de dados na sub-árvore “enraizada” no
filho 1, possuem valores maiores do que a chave 0, mas
menores do que a chave1;
{ todos os itens de dados na sub-árvore “enraizada” no
filho 2, possuem valores maiores do que a chave 1, mas
menores do que a chave2;
{ todos os itens de dados na sub-árvore “enraizada” no
filho 3, possuem valores maiores do que a chave 2.
{ Valores duplicados geralmente não são permitidos.
Deste modo nós não necessitamos nos preocupar com a
comparação de chaves iguais.
A B C
Nó com chaves
menores do que
A
Nó com chaves
entre A e B
Nó com chaves
entre B e C
Nó com chaves
maiores do que
C
0 1 2 3
Pesquisa em árvores 2-3-4
Exemplo:
{ Para pesquisar por um item de dado com a chave 64 na
árvore da figura, você inicia na raiz, porém não
encontra o item.
{ Por que 64 é maior do que 50, você vai para o filho 1, o
qual nós representamos com 60,70 e 80.
{ Você não encontra o item de dado, assim você precisa
passar para o próximo filho.
{ Aqui, devido a 64 ser maior do que 60, mas menor do
que 70, você vai novamente para o filho 1. Desta vez
você encontra o item específico no link 62, 64 e 66.
50
30 60 70 80
10 20 5540 62 64 66 75 83 86
18
Inserção em árvore 2-3-4
{ Novos itens de dados são sempre inseridos nas
folhas.
{ Se os itens foram inseridos em um nó com
filhos, então o número de filhos necessitará ser
mudado para manter a estrutura da árvore, o
que estipula que esta árvore deve ter um filho a
mais do que os itens de dados em um nó.
{ O processo de inserção inicia pela pesquisa do
nó folha apropriado.
{ Se nós que não estão cheios são encontrados
durante a pesquisa, a inserção é fácil.
{ A inserção pode envolver a movimentação de
um ou dois itens em um nó.
{ As chaves deverão estar na ordem correta após
o novo item ser inserido.
Exemplo 1: Inserção em árvore 2-3-4
 - O item 23 vai ser deslocado para direita
para “abrir espaço” para inserir o item 18.
28 55
11 74
5 9 3013 23 44 47 63 67 72 97
42
a) Antes da inserção
18 é inserido 23 é deslocado para direita
28 55
11 74
5 9 3013 18 23 44 47 63 67 72 97
42
b) Depois da inserção
- Inserção de um item (18) sem divisão
do nó
19
Exemplo 2 - Inserção em árvore 2-3-4
{ Com Divisão de nós
z As inserções tornam-se mais complicadas se um
nó cheio é encontrado no caminho abaixo do
ponto de inserção.
z Quando isto acontece, o nó precisa ser dividido
(split).
z É este processo de divisão que mantêm a árvore
balanceada.
z O tipo de árvore 2-3-4 que estamos vendo é
freqüentemente chamada de árvore 2-3-4 top-
down, por que os nós são divididos de maneira
“para baixo” do ponto de inserção.
Inserção em árvore 2-3-4
{ Chamaremos os itens de dados a serem
divididos por A, B e C.
z assumimos que o nó a ser dividido não é o
raiz, nós examinaremos a divisão da raiz
depois
62
29 83 92 104
15 21 7447 87 89 97 112
a) Antes da inserção
nó a ser dividido
inserção do 99
A B C
20
Inserção em árvore 2-3-4
{ Um novo nó vazio é criado. Ele é parente (sibling) do nó que está
sendo dividido, e é colocado a sua direita;
{ O item de dado C é movido para o novo nó;
{ O item de dado B é movido para o pai do nó que está sendo dividido;
{ O item de dado A fica aonde ele está;
{ Os dois filhos mais à direita são desconectados do nó que está sendo
dividido e são conectados no novo nó.
62
29 83 92 104
15 21 7447 87 89 97 112
a) Antes da
inserção
nó a ser dividido
inserção do 99
A B C
62 92
29 104
15 21 7447 87 89 97 99 112
b) Após a inserção
novo nó
92 movido para cima
A
B
C
83
99 inserido
83 fica no lugar 104 foi p/ direita
Exemplo 3 - Inserção em árvore 2-3-4
{ Dividindo a raiz
z Quando uma raiz cheia é encontrada no
inicio da pesquisa para encontrar o
ponto de inserção, o resultado da
divisão é ligeiramente mais
complicado:
26 49 72
9 13 31 35 52 61 82
a) Antes da inserção raiz a ser dividido
inserção do 41
A B C
21
Inserção em árvore 2-3-4
z o item de dado C é movido para o novo nó parente;
z o item de dado B é movido para a nova raiz;
z o item de dado A é deixado aonde está;
z os dois filhos mais a direita do nó que está sendo dividido são
desconectados dele e conectados no novo nó do lado direito.
26 49 72
9 13 31 35 52 61 82
a) Antes da inserção
raiz a ser dividido
inserção do 41
A B C
49
9 13 31 35 41 52 61 82
b) Após a inserção
novo nó raiz
49 é movido p/cima
A
B
C
26 72 novo nó à direita
72 movido
p/ direita
26 fica no
lugar
41 inserido
•um novo nó é criado, tornando-
se a nova raiz, e os pais do novo
nó são divididos;
•um segundo novo nó é criado,
tornando-se parente (sibling) do
nó que está sendo dividido;
Árvores B
22
Árvore B
{ São árvores de pesquisa balanceadas
especialmente projetadas para a pesquisa de
informação em discos magnéticos e outros meios de
armazenamento secundário.
{ Minimizam o número de operações de
movimentação de dados (escrita/leitura) numa
pesquisa ou alteração.
{ O grau de um nó pode ser alto.
{ Podem ser consideradas como uma generalização
natural das árvores de pesquisa binárias.
Árvores B
{ As árvores são uma boa abordagem para dados
em memória.
{ Mas, as árvores trabalham com arquivos?
z Elas trabalham, mas um tipo diferente de árvore
precisa ser usado para dados externos do que
para dados em memória.
{ A árvore apropriada é um árvore múltivias,
parecida com uma árvore 2-3-4, mas com
muito mais itens de dados por nó
{ Ela se chama Árvore B (tree-B). As árvores B
foram concebidas como estrutura apropriada
para armazenamento externo por R. Bayer e E.
M. McCreight em 1972.
{ Árvores M-Vias permanentemente balanceadas
são chamadas de Árvore B.
23
Árvores B - Um bloco por nó
{ O acesso a disco é mais eficiente
quando o dado é lido ou escrito em
um bloco de uma só vez.
{ Em uma árvore, a entidade que
contêm dados é o nó.
{ Ideal: armazenar um bloco inteiro
de dados em cada nó da árvore.
{ Deste modo, ler um nó acessa um
conjunto máximo de dados em um
curto espaço de tempo.
Árvores B - Links
{ Em uma árvore, precisamos também
armazenar os links para outros nós.
{ Em uma árvore em memória, estas
“ligações” são referências (ou ponteiros,
em linguagens como Pascal e C) para os
nós em outras partes da memória.
{ Para as árvores armazenadas em um
arquivo em disco, as ligações (links) são
números de blocos em um arquivo.
24
Árvores B x Árvores 2-3-4
{ Dentro de cada nó os dados são
ordenados seqüencialmente pela
chave, como nas árvores 2-3-4.
{ A estrutura de uma árvore B é
similar a de uma árvore 2-3-4,
exceto que na árvore B existem
mais itens de dadospor nó e mais
links para nós filhos.
Árvores B
Características
{ A raiz tem no mínimo uma chave e
dois filhos
{ Uma folha tem no mínimo d chaves
e não tem filhos
{ Todas as folhas estão no mesmo
nível (balanceamento)
25
Pesquisa em Árvores B
{ Primeiro, o bloco contendo a raiz é lido.
{ O algoritmo de pesquisa então inicia a
verificação de cada um dos registros (se ele
não estiver cheio, tantos quantos o nó
atualmente armazena) iniciando pelo registro 0.
{ Quando ele encontra um registro com chave
maior, ele sabe que deve ir para o filho que
reside entre este registro e o precedente.
{ Este processo continua até o nó correto ser
encontrado.
{ Se uma folha é alcançada sem encontrar a
chave específica, a pesquisa não obteve
sucesso.
Inserção em Árvores B
{ Em uma árvore B é importante
manter um nó tão cheio quanto
possível;
{ deste modo cada acesso à disco, o
qual lê uma entrada de um nó,
pode adquirir o máximo de
quantidade de dados.
26
Construção de uma pequena árvore B
{ A figura (a) mostra um nó raiz que já está
cheio;
{ Itens com chaves 20,40,60 e 80 já foram
inseridas na árvore.
{ Um novo item de dado com a chave 70
deve inserido, resultando na divisão de
um nó.
{ A raiz está sendo dividida, dois novos nós
são criados: uma nova raiz e um novo nó
para a direita do que está sendo dividido.
(a) 7020 40 60 80 20 40 60 8070
Construção de uma pequena árvore B
{ Na figura (b) inserimos mais dois itens: 10 e 30.
{ Eles preenchem totalmente o filho da esquerda, tal como
apresentado nas figura (c).
{ O próximo item a ser inserido, 15, divide o filho à
esquerda, como visto na figura (d).
{ Aqui o item 20 foi promovido para cima, na raiz.
(b)
10
30
60
20 40 70 80
(c)
1560
10 20 30 40 70 80
10 15 20 4030
(d)
20 60
10 15 30 40 70 80
27
Construção de uma pequena árvore B
{ Na fig. (e) três itens, 75,85 e 90, são inseridos
{ O terceiro filho é dividido, causando a criação
de um novo nó e a promoção do item
intermediário, 80, para a raiz.
{ O resultado disto é visto na figura (f).
(f)
20 60 80
10 15 30 40 70 75 85 90
(e)
7520 60
10 15 30 40
70 75 80 9085
85 90
70 80
Construção de uma pequena árvore B
{ Novamente três itens, 25, 35 e 50, são adicionados fig. (g)
{ Os primeiros dois itens enchem totalmente o segundo filho
{ E o terceiro filho é divido, provocando a criação de um novo
nó e a promoção do item intermediário, 35, para a raiz,
como pode ser visto na figura (h).
(h)
20 35 60 80
10 15 25 30 40 50 70 75 85 90
(g)
25
20 60 80
10 15 30 40
25 30 35 5040
35 50
70 75 85 90
28
Construção de uma pequena árvore B
{ Agora a raiz está cheia.
{ Contudo, inserções subseqüentes não necessariamente causarão a
divisão do nó, porque os nós são divididos somente quando uma
nova inserção em um nó cheio é efetuada, não quando um nó cheio
é encontrado em uma pesquisa sobre a árvore.
{ Assim, 22 e 27 são inseridos no segundo filho sem causar qualquer
divisão, como apresentado na figura (j).
(j)
20 35 60 80
10 15 22 25 27 30 40 50 70 75 85 90
(i)
22
20 35 60 80
10 15 25 30
27
40 50 70 75 85 90
{ O próximo item a ser inserido, 32, não causa uma divisão, na
realidade, ele causa duas divisões.
{ O segundo nó filho, está cheio, deste modo, ele é dividido, como visto
na figura (l).
{ O item 27, promovido a partir da divisão, não foi colocado no seu
lugar porque a raiz está cheia.
{ Portanto a raiz também precisa ser dividida, resultando no arranjo
presente na figura (M).
22 25 27 3230(k)
3220 35 60 80
10 15 22 25 27 30 40 50 70 75 85 90
20 27 35 8060(l)
2720 35 60 80
10 15 22 25 40 50 70 75 85 90
(M)
35
10 15 22 25 30 32
20 27
40 50 70 75 85 90
60 80
29
Implementação em árvore B mais
Eficiente
{ Considerar
z T= ordem da árvore (ou grau)
z T>=2
z Cada nó contém no mínimo T-1 chaves
e T filhos
z Cada nó pode ter no máximo 2T-1
chaves e 2T filhos
z Todos os nós folhas estão no mesmo
nível.
Ex: t=2
t-1= 1 chave
t= 2 filhos
Máx:
2t-1= 3 chaves
2t= 4filhos
Inserção:
{ É sempre feita nas folhas
{ Percorrer a árvore em busca da chave
{ Verificar se o nó esta cheio:
z se contém (2T-1) chaves
{ Se o nó estiver cheio:
z Dividir ao meio
z Colocar chave no nó pai
z Se este também estiver cheio repetir o
processo
30
Arvores B+
{ É uma variante da árvore B
{ Os nós internos são indexados para
acesso rápido aos dados.
{ As folhas possuem estrutura diferente
da árvore B. Elas formam um conjunto
de seqüência, de modo que varrer essa
lista de folhas resulta nos dados obtidos
na ordem ascendente.
{ Ela é um índice implementado como
uma árvore B regular mais uma lista
ligada de dados.
Arvores B+
{ Inserir em uma folha que tenha espaço,
significa colocar a folha em ordem
{ Inserir em uma folha cheia: A folha é dividida,
o novo nó é incluído no conjunto de
seqüências.
{ A primeira chave do nono nó é copiada (não
movida como na árvore B) para o
ascendente.
{ Poderá exigir reorganização no nodo
ascendente
{ Se o ascendente está cheio, ocorre mesmo
processo da árvore B
31
Exemplo: Inserção em B+
Exemplo: Remoção em B+