INF 1010
Estruturas de Dados Avançadas
Árvores 2-3
17/10/2011
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
1
Características
•
Árvores 2-3
•
Cada nó armazena 1 ou 2 chaves
•
Cada nó interno possui 2 ou 3 filhos
•
São balanceadas
17/10/2011
•
Não dependem de operações de rotação
•
Balanceamento é garantido diretamente pelas
operações de inserção e remoção
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
2
Características
•
Árvores 2-3 (cont.)
•
17/10/2011
São árvores de busca
•
Nó interno com 2 filhos
•
Nó interno com 3 filhos
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
3
Caminhamento
•
Caminhamento em Ordem Infixa (esboço)
1. Caminhe pela subárvore da esquerda.
2. Imprima a menor chave (que pode ser a única).
3. Caminhe pela subárvore do meio.
4. Imprima a maior chave, se existir.
5. Caminhe pela subárvore da direita, se existir.
17/10/2011
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
4
Busca
•
Exemplo: Busca por “130”
17/10/2011
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
5
Inserção
•
Algoritmo de Inserção (esboço)
1. Localize a folha onde a nova chave será inserida.
2. Divida a folha, se necessário.
3. Divida nós internos, recursivamente,
se necessário.
17/10/2011
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
6
Inserção
•
Algoritmo de Inserção (cont.)
•
Se a folha já tem 2 chaves, divida a folha
•
Mova a “chave do meio” para o pai
17/10/2011
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
7
Inserção
•
Algoritmo de Inserção (cont.)
•
Se o pai já tem 2 chaves, divida o pai
•
Mova a “chave do meio” para o pai do pai
17/10/2011
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
8
Inserção
•
Algoritmo de Inserção (cont.)
•
Se a raiz já tem 2 chaves, crie nova raiz
•
Mova a “chave do meio” para a nova raiz
17/10/2011
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
9
Inserção
•
Inserção de “39”
•
Localize a folha onde “39” deve ser inserida
•
A folha só tem 1 chave: insira “39”
39
17/10/2011
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
10
Inserção
•
Inserção de “38”
•
Localize a folha onde “38” deve ser inserida
•
A folha tem 2 chaves: simule a inserção de “38”
38
17/10/2011
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
11
Inserção
•
Inserção de “38”
•
Mova a chave do meio para o pai p
•
Separe o menor e o maior valores em 2 nós,
que serão filhos de p
17/10/2011
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
12
Inserção
•
Inserção de “37”
•
Localize a folha onde “37” deve ser inserida
•
A folha só tem 1 chave: insira “37”
37
17/10/2011
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
13
Inserção
•
Inserção de “36”
•
Localize a folha onde “36” deve ser inserida
•
A folha já tem 2 chave: Simule a inserção de “36”
36
17/10/2011
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
14
Inserção
•
Inserção de “36”
•
Simule mover a chave do meio para o pai p
•
Simule criar 2 novos filhos de p
17/10/2011
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
15
Inserção
•
Inserção de “36”
•
17/10/2011
Divida o nó p
•
Mova a chave do meio para o pai de p
•
Os nós com as chaves menor e maior formam novos nós
•
Redistribua os 4 filhos de p entre os novos nós
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
16
Exercício
•
Ilustre como fica a árvore 2-3, inicialmente
vazia, com a seguinte sequência de
inserções: 1, 2, 3, 4, 5, 6 e 7.
17/10/2011
© 2011 DI, PUC-Rio • Estruturas de Dados Avançadas • 2011.2
17
Exercício
•
Algoritmo de busca
struct node {
int x, y;
Node *l, *m, *r;
};
•
17/10/2011
y = -1, significa ausência de valor.
© 2011 DI, PUC-Rio • Estruturas de Dados Avançadas • 2011.2
18
Remoção
•
Algoritmo de Remoção (esboço)
1. Se a chave a ser removida pertencer a uma folha,
•
Remova a chave.
2. Se a chave a ser removida pertencer a um nó
interno
•
Troque a chave com a sua sucessora
(que necessariamente está em uma folha).
•
Remova a chave (da folha).
3. Redistribua e combine nós.
17/10/2011
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
19
Remoção
•
Algoritmo de Remoção (cont)
•
17/10/2011
Remova e Redistribua – Casos 1 e 2
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
20
Remoção
•
Algoritmo de Remoção (cont)
•
17/10/2011
Remova e Redistribua – Casos 3 e 4
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
21
Remoção
•
Algoritmo de Remoção (cont)
•
17/10/2011
Remova e Combine – Casos 5 e 6
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
22
Remoção
•
Algoritmo de Remoção (cont)
•
17/10/2011
Remova e Combine – Caso 7
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
23
Remoção
•
Algoritmo de Remoção (cont)
•
17/10/2011
Remova e Redistribua – Caso 8
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
24
Remoção
•
Algoritmo de Remoção (cont)
•
17/10/2011
Remova e Redistribua – Caso 9
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
25
Remoção
•
Algoritmo de Remoção (cont)
•
17/10/2011
Remova e Combine – Caso 10
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
26
Remoção
•
Algoritmo de Remoção (cont)
•
17/10/2011
Remova e Combine – Caso 11
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
27
Remoção
•
Algoritmo de Remoção (cont)
•
17/10/2011
Remova a raiz – Caso 12
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
28
Remoção
•
Remoção de “65”
•
O nó que contém “65” é interior
•
Troque “65” com a sua sucessora
17/10/2011
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
29
Remoção
•
Remoção de “65”
•
Remova “65”
•
17/10/2011
Como a folha possui 2 chaves, é possível remover “65”
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
30
Remoção
•
Remoção de “70”
•
O nó que contém “70” é interior
•
Troque “70” com a sua sucessora
17/10/2011
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
31
Remoção
•
Remoção de “70”
•
17/10/2011
Remova “70”
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
32
Remoção
•
Remoção de “70”
•
A árvore torna-se inválida
•
Combine nós
17/10/2011
© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1
33
Resumo
•
Árvores 2-3
•
Cada nó armazena 1 ou 2 chaves
•
Cada nó interno possui 2 ou 3 filhos
•
Algoritmos de inserção e remoção mantém
as árvores balanceadas
•
Caso especial de Árvores-B
17/10/2011
© 2011 DI, PUC-Rio • Estruturas de Dados Avançadas • 2011.2
34