Aula 9_Árvores 2-3 e Árvores 2-3-4

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Árvores 2-3 
e Árvores 2-3-4
Lívia N. Andrade
Introdução
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).
Árvores 2-3 são interessantes por várias razões:
São árvores balanceadas
Fáceis de programar
Servem como uma introdução para árvores B
2
Árvores 2-3
As árvores 2-3, são árvores multivias, um caso especial de árvore B. 
Nestas árvores, os números 2 e 3 referem-se aos números de filhos que a árvore pode ter:
pode ter um item de dados e dois filhos e no máximo dois itens de dados e três filhos por nó.
Assim como na árvore B, todos os nós folhas se localizam no mesmo nível.
Porque não há árvores 1-2-3?
Porque não pode ter um nó não-folha com apenas um filho.
3
Exemplo - árvore 2-3
25
 1 23
 80
0
21 22
24
70 72
90 92
A figura abaixo mostra uma pequena árvore 2-3.
Cada nó pode conter um ou dois itens de dados.
4
Operações em Árvore 2-3
Pesquisa
Inserção
Remoção
5
Ideia básica para a pesquisa
Semelhante à pesquisa na árvore B.
A pesquisa inicia-se sempre pela raiz. 
Se o item procurado não estiver na raiz, identifique o nó filho da raiz em que ele pode estar e siga para este nó.
Se ele não estiver neste outro nó, identifique em qual nó filho deste nó o item poderá estar, e siga para este nó.
O processo se repete até que o item seja encontrado ou até um nó folha ser encontrado.
6
Exemplo 1: Pesquisa Árvore 2-3
Pesquisando pelo item 72 na árvore 2-3 abaixo.
25
 1 23
 80
0
21 22
24
70 72
90 92
Item 72 não está na raiz. 
O item 72 é maior do que o item que está na raiz, siga para o nó filho da direita
7
Exemplo 1: Pesquisa Árvore 2-3
Pesquisando pelo item 72 na árvore 2-3 abaixo.
25
 1 23
 80
0
21 22
24
70 72
90 92
Item 72 não está neste nó. 
O item 72 é menor do que o item que está neste nó, siga para o nó filho da esquerda
8
Exemplo 1: Pesquisa Árvore 2-3
Pesquisando pelo item 72 na árvore 2-3 abaixo.
25
 1 23
 80
0
21 22
24
70 72
90 92
Este nó possui mais itens.
Verifique, em todos os itens existentes, se algum deles é o item 72.
 O item é encontrado.
Retorne então o nó e a posição que o item se localiza neste nó.
9
Ideia básica para a inserção
Semelhante à inserção na árvore B
Quando ocorre a tentativa de inserção de um item em uma página folha cheia, a página folha é então dividida em duas páginas folha, o item do meio sobe para a página pai, e os elementos com chave menores ficam na página folha da esquerda e os itens com chaves maiores na página folha da direita.
10
Exemplo 2: Inserção Árvore 2-3
Insira item 50 na árvore 2-3 abaixo.
25
10 20
27 32
25
10 20
27 32
50
Página folha está cheia.
Solução: Dividir a página e subir o elemento do meio para a página pai
11
Exemplo 2: Inserção Árvore 2-3
Insira item 50 na árvore 2-3 abaixo.
25
10 20
27 32
25 32
10 20
27 
50
12
Exemplo 3: Inserção Árvore 2-3
Insira item 5 na árvore 2-3 abaixo.
5
Página folha está cheia.
Solução: Dividir a página e subir o elemento do meio para a página pai
25 32
10 20
27 
50
25 32
10 20
27 
50
13
Exemplo 3: Inserção Árvore 2-3
Insira item 5 na árvore 2-3 abaixo.
10
25 32
10 20
27 
50
25 32
20
27 
50
Página raiz também está cheia.
Solução: Dividir a página e subir o elemento do meio para a nova página raiz.
5
14
Exemplo 3: Inserção Árvore 2-3
Insira item 5 na árvore 2-3 abaixo.
25 32
10 20
27 
50
32
20
27 
50
5
25
10
15
Exercício de Inserção
Inserir as seguintes chaves em um árvore 2-3: 
25, 80, 1, 22, 0, 24, 70, 90, 23, 21, 72, 92, 78, 98, 20.
Árvore 2-3 resultante
80
23
72 
92
1
25
21
0
20
22
24
70
78
90
98
16
Idéia básica da Exclusão 
Semelhante à remoção na árvore B.
Primeiro pesquise a chave para ter a certeza de que esta existe na árvore.
Se existir, verifique se está em folha, e faça a exclusão.
Se após a exclusão algum nó ficar com apenas um filho, a árvore deve modificar sua estrutura para que todos os nós tenham pelo menos 2 filhos e todos os nós folhas no mesmo nível.
17
Exemplo 4: Exclusão Árvore 2-3
Remover item 73.
80
23
72 
92
1
25
21
0
20
22
24
70 73
78
90
98
18
Exemplo 4: Exclusão Árvore 2-3
Remover item 73.
80
23
72 
92
1
25
21
0
20
22
24
70 
78
90
98
19
Exemplo 5: Exclusão Árvore 2-3
Remover item 20.
80
23
72 
92
1
25
21
0
20
22
24
70
78
90
98
20
Exemplo 5: Exclusão Árvore 2-3
Remover item 20.
80
23
72 
92
1
25
21
0
22
24
70
78
90
98
Erro!
Nó não pode ter apenas um filho.
Solução: junte o item do único filho com o item do nó pai
21
Exemplo 5: Exclusão Árvore 2-3
Remover item 20.
80
23
72 
92
 0 1
25
21
22
24
70
78
90
98
ERRO!
Assim como na árvore B, os nós folhas devem estar todos no mesmo nível.
Solução: agrupar os nós folhas, para que todas as folhas fiquem no mesmo nível.
22
Exemplo 5: Exclusão Árvore 2-3
Remover item 20.
80
72 
92
 0 1
25
21 23
22
24
70
78
90
98
23
Exemplo 5: Exclusão Árvore 2-3
Remover item 20.
80
70 72 78 
90 92 98
 0 1
25
21 23
22
24
ERRO!
Os nós podem ter no máximo 2 itens de dados
Solução: levar o menor elemento da subárvore da direita para a raiz, e descer o item da raiz para a subárvore da esquerda
24
Exemplo 5: Exclusão Árvore 2-3
Remover item 20.
80
 72 78 
90 92 98
 0 1
70
21 23
22
24 25
ERRO!
Os nós podem ter no máximo 2 itens de dados.
Solução: levar o menor elemento da subárvore da direita para a raiz, e descer o item da raiz para a subárvore da esquerda.
25
Exemplo 5: Exclusão Árvore 2-3
Remover item 20.
90
72 78 80 
 92 98
 0 1
70
21 23
22
24 25
ERRO!
Os nós podem ter no máximo 2 itens de dados.
Solução: levar o menor elemento da subárvore da direita para a raiz, e descer o item da raiz para a subárvore da esquerda.
26
Exemplo 5: Exclusão Árvore 2-3
Remover item 20.
90
78 80 
 92 98
 0 1
72
21 23
22
24 25 70
ERRO!
Os nós podem ter no máximo 2 itens de dados.
Solução: levar o menor elemento da subárvore da direita para a raiz, e descer o item da raiz para a subárvore da esquerda.
27
Exemplo 5: Exclusão Árvore 2-3
Remover item 20.
90
78 80 
 92 98
 0 1
72
21 24
22 23
 25 70
28
Exemplo 5: Exclusão Árvore 2-3
Árvore inicial
Árvore após remoção do item 20
90
 78 80 
92 98
 0 1
72
21 24
22 23
25 70
80
23
72 
92
1
25
21
0
20
22
24
70
78
90
98
29
Árvores 2-3-4
As árvores 2-3-4, são também árvores multivias.
Nestas árvores, os números 2, 3 e 4 referem-se aos números de filhos que a árvore pode ter:
Nó com 1 item possui 2 filhos
Nó com 2 itens possui 3 filhos
Nó com 3 itens possui 4 filhos
Porque não há árvores 1-2-3-4?
Porque não pode ter um nó não-folha com apenas um filho.
30
Operações em Árvore 2-3-4
Pesquisa
Semelhante a pesquisa na árvore 2-3
Inserção
Semelhante a pesquisa na árvore 2-3
Remoção
Semelhante a pesquisa na árvore 2-3
31
Exemplo 6: Inserção Árvore 2-3-4
Insira item 70 na árvore 2-3-4 abaixo.
30 50 60
30
60 70
Página cheia.
Solução: dividir a página em duas páginas
50
32
Exemplo 7: Inserção Árvore 2-3-4
Insira os itens 40, 20 e 10 na árvore 2-3-4 abaixo.
30
60 70
50
 20 30 40
60 70
50
Página cheia.
Solução: dividir a página em duas páginas
33
Exemplo 7: Inserção Árvore 2-3-4
Insira os itens 40, 20 e 10 na árvore 2-3-4 abaixo.
30
60 70
50
 10 20 
60 70
30 50
 40
34
Exemplo 8: Inserção Árvore 2-3-4
Insira os itens 55 e 80 na árvore 2-3-4 abaixo.
 10 20 
60 70
30 50
 40
 10 20 
55 60 70
30 50
 40
Página cheia.
Solução: dividir a página em duas páginas
35
Exemplo 8: Inserção Árvore 2-3-4
Insira os itens 55 e 80 na árvore 2-3-4 abaixo.
 10 20 
60 70
30 50
 40
 10 20 
55 
30 50 60
 40
70 80
36
Exemplo 9: Inserção Árvore 2-3-4
Insira os itens 62 e 75 na árvore 2-3-4 abaixo.
 10 20 
55 
30 50 60
 40
62 70 80
Página cheia.
Solução: dividir a página em duas páginas
 10 20 
55 
30 50 60
 40
70 80
37
Exemplo 9: Inserção Árvore 2-3-4
Insira os itens 62 e 75 na árvore 2-3-4 abaixo.
 10 20 
60 70
30 50
 40
 10 20 
55 
30 50 60
 40
62 
Página cheia.
Solução: dividir a página em duas páginas
75 80
70
38
Exemplo 9: Inserção Árvore 2-3-4
Insira os itens 62 e 75 na árvore
2-3-4 abaixo.
 10 20 
60 70
30 50
 40
 10 20 
55 
30
 40
62 
75 80
50 
 60 70
39
Exercício de Inserção Árvore 2-3-4
Mostre a árvore 2-3-4 resultante após a inserção das chaves abaixo:
 7, 10, 12, 3, 5, 8, 4, 6, 9, 11,13, 21, 22, 14, 15, 16, 17, 18, 19, 20, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23
40
Exemplo 10: Remoção Árvore 2-3-4
Remover o item 50 na árvore 2-3-4 abaixo.
 10 15 
70 75
20 30
 25
90
50 
80
 40
 10 15 
 20 30 80
 25
90
 40 70 75
Os dois filhos da raiz são unidos e árvore é reconfigurada
41
Exemplo 11: Remoção Árvore 2-3-4
Remover o item 30 na árvore 2-3-4 abaixo.
 10 15 
 20 30 80
 25
90
 40 70 75
O item 
30 é substituido pelo item 40
 10 15 
 20 40 80
 25
90
 70 75
42
Exemplo 12: Remoção Árvore 2-3-4
Remover o item 40 na árvore 2-3-4 abaixo.
As duas páginas folhas do item removido são agrupadas em uma página
 10 15 
 20 40 80
 25
90
 70 75
 10 15 
 20 80
90
 25 70 75
43
Referências Utilizadas
Livro:
	
ZIVIANI, Nivio, Projeto de algoritmos com implementação em Pascal e C, 3a. edição, Editora Thomson, 2011
Notas de aula da disciplina, disponível no Moodle.
44