aulaarvoresmultidirecionais_estruturadedadosII_com exercicios resolvidos

Prévia do material em texto

1
Árvores Multidirecionais 
 
Em uma Árvore de Busca Binária, cada nó possui um valor (chave) e pode 
ter até dois filhos. 
Se forem permitidos mais itens de dados e filhos por nó, o resultado é 
uma árvore multidirecional. 
 
 
Árvores 2-3-4 
 
São árvores multidirecionais (tipo B) que podem ter até 4 filhos e 3 três 
itens de dados por nó. 
 
São árvores equilibradas como as árvores Red-Black. São menos eficientes 
que as árvores Red-Black, mas mais fáceis de programar. 
 
 
 
 
 
 
 
 
 
Nessa árvore 2-3-4, cada nó por ter um, dois, ou três itens de dados. Os 
três nós superiores têm filhos, e os seis nós na fila de baixo são nós folha 
(não têm filhos). Em uma árvore 2-3-4 todos os nós folha sempre estão no 
mesmo nível, e os nós de nível superior podem não estar cheios (podem 
conter apenas um ou dois valores, e não três). 
 
60 70 80
4010 20
30
50 
83 867562 64 6655
 2
Os números 2, 3 e 4 no nome da árvore 2-3-4, se referem a quantos links 
de filhos podem existir em um certo nó. Para nós que não são folhas, as 
seguintes 3 organizações são possíveis: 
 
1. Um nó com um item de dados sempre tem dois filhos; 
2. Um nó com dois itens de dados sempre têm três filhos; 
3. Um nó com três itens de dados sempre têm quatro filhos. 
 
Logo, um nó que não é folha sempre deve ter um filho a mais do que tem 
itens de dados. 
 
Se o número de links dos filhos for L e o número de itens de dados for 
D, então: 
 
 L = D + 1 
 
Essa relação determina a estrutura das árvores 2-3-4. Um nó folha, não 
tem filhos, mas pode, no entanto, conter um, dois, ou três valores. Os 
nós vazios e os nós com um link não são permitidos. 
 
Como uma árvore 2-3-4 pode ter nós com até 4 filhos, ela é chamada de 
árvore multidirecional de ordem 4. Também chamada de árvore B de 
ordem 4. 
 
Em uma árvore 2-3-4 um nó sempre deve ter no mínimo dois filhos, a 
menos que seja uma folha. 
 
 
 3
Organização da árvore 2-3-4 
 
Os valores do nós são numerados de 0 a 2, e os links de 0 a 3. Os 
valores em um nó são organizados de forma ascendente, da esquerda 
para a direita (dos números menores para os números maiores). 
 
 
 
 
 
 
 
 
 
 
 
Uma árvore 2-3-4 segue o mesmo princípios da ABBs, possuindo as 
seguintes características: 
 
• Todos os filhos na subárvore enraizados no filho 0 têm valores-
chave menores do que a chave 0. 
• Todos os filhos na subárvore enraizados no filho 1 têm valores-
chave maiores do que a chave 0 e menores de do que a chave 1. 
• Todos os filhos na subárvore enraizados no filho 2 têm valores-
chave maiores do que a chave 1 e menores de do que a chave 2. 
• Todos os filhos na subárvore enraizados no filho 3 têm valores-
chave maiores do que a chave 2. 
 
Não são permitidos valores duplicados. 
60 70 80
4010 20
30
50 
83 867562 64 6655
0 
0 1 2 
0 1 2 0 1 0 1 
0 
0 0 0 
0
0
0
1
1
1
2 3
 4
 
 
Pesquisa 
 
O processo de pesquisa em árvores 2-3-4 é semelhante ao das ABBs, 
ou seja, inicia-se pela raiz, e, se a chave não for encontrada, verifica-
se é maior ou menor que a raiz, continuando a busca até chegar ao nó 
que possui uma seqüência de valor com a chave desejada. 
 
A B C
Nós com chaves 
menores que A 
Nós com chaves 
entre A e B 
Nós com chaves 
entre B e C 
Nós com chaves 
maiores que C 
 5
Exemplo: 
 
• Pesquisando o valor 64 na seguinte árvore 2-3-4 
 
 
 
 
 
 
 
 
 
1. Iniciar da raiz; 
2. O valor é pesquisado na raiz, porem não encontrado; 
3. Como 64 é maior do que 50, deve-se ir para o filho 1, que 
contem os valores 60, 70 e 80. 
4. O valor é pesquisado seqüencialmente comparando-se com 
todos os valores desse nó, porém não é encontrado. 
5. Nesse nó (60-70-80) busca-se por meio de qual link continuará 
a pesquisa. Como 65 é maior que 60 e menor que 70, a pesquisa 
continua com o filho 1 (link) desse nó, o qual contem os valores 
62, 64 e 66. 
6. O valor é pesquisado seqüencialmente comparando-se com 
todos os valores desse nó, e então localizado como o filho 1 
desse nó. 
60 70 80
4010 20
30
50 
83 867562 64 6655
0 
0 1 2 
0 1 2 0 1 0 1 
0 
0 0 0 
0
0
0
1
1
1
2 3
 6
 
Inserção 
 
Os valores são sempre inseridos nos nós folha. 
 
Obs: Se os valores fossem inseridos nos nós com filhos, o número de filhos 
precisaria ser mudado para manter a estrutura da árvore, que estipula que 
deve haver um filho a mais do que valores em um nó. 
 
Durante a procura pela posição em que o valor seja inserido, se nós 
completos não são encontrados durante a pesquisa, a inserção é fácil. 
Quando o nó folha apropriado é encontrado, o novo valor é simplesmente 
inserido nele. 
 
 7
Exemplo: Inserindo o valor 18 
 
• Antes da Inserção 
 
 
 
 
 
 
 
 
 
• Depois da Inserção 
 
 
 
 
 
 
 
 
 
 
A inserção pode envolver mover um ou dois outros valores em um 
nó, de modo que as chaves fiquem na ordem correta depois que o 
novo valor for inserido. Nesse exemplo, o valor 23 tinha de ser 
mudado para a direita a fim de abrir espaço para o 18. 
 
 
 
 
42
13 235 9
11
28 55
9763 67 7244 4730
74
42
13 18 235 9
11
28 55 
9763 67 7244 4730
7423 é deslocado 
para a direita
18 é inserido 
 8
Divisões de nós 
 
Esse tipo de árvore é freqüentemente chamado de Árvore 2-3-4 top-down 
(de cima para baixo), porque os nós são divididos para baixo até o ponto de 
inserção. 
 
 
Terminologia para divisão dos nós 
 
• A: 1º valor do nó que está sendo dividido 
• B: 2º valor do nó que está sendo dividido 
• C: 3º valor do nó que está sendo dividido 
 
Divisão de um nó que não é raiz 
 
Assumindo que o nó que está sendo dividido não é raiz, o 
processo de divisão ocorre da seguinte maneira: 
 
• Um novo nó, vazio, é criado. É um irmão do nó que está sendo 
dividido, e é inserido à sua direita; 
• O item de dados C é movido para a sua direita; 
• O item de dados B é movido para o pai do nó que está sendo 
dividido; 
• O item de dados A continua como está. 
• Os dois filhos de extrema direita estão desconectados do nó 
que está sendo dividido e conectados ao novo nó. 
Durante o processo de inserção, caso um nó completo seja encontrado 
no percurso para baixo do ponto de inserção, o processo de inserção se 
torna mais complicado. Quando isso ocorre, o nó deve ser dividido, 
processo que mantém a árvore equilibrada. 
 9
Exemplo: Inserindo o valor 99 
 
• Antes da Inserção 
 
 
 
 
 
 
 
 
 
 
• Depois da Inserção 
 
 
 
 
 
 
 
 
 
 
 
Obs: 
Uma outra forma de descrever a divisão de nó é dizer que 
um nó de 4 foi transformado em dois nós de 2. 
No processo de buscar pela posição para inserir um valor, 
pode ocorrer de mais do que um nó completo ser encontrado 
no percurso até o ponto de inserção. Quando este for o 
caso, haverá diversas divisões. 
83 92 104
4715 21
29
62 
1129787 8974
Nó que será 
dividido
A B C 
83
4715 21
29
62 92
11297 9987 8974
Novo nó
A 
B 
C 
104
92 é movido 
para cima
99 é inserido 
104 se move 
para a direita
83 permanece
 10
 
 Divisão da Raiz 
 
Quando uma raiz completa é encontrada no início da pesquisa 
pelo ponto de inserção, a divisão resultante deverá ocorrer da 
seguinte maneira: 
 
• Um novo nó é criado, o qual se torna a nova raiz, e o pai do nó 
que está sendo dividido. 
• Um segundo novo nó é criado e se torna o irmão do nó que está 
sendo dividido. 
• O item de dados C é movido para o novo irmão. 
• O item de dados B é movido para a nova raiz, que é criada. 
• O item de dadosA, continua como está. 
• Os dois filhos mais à direita do nó que está sendo dividido são 
desconectados dele e conectados no novo nó do lado direito. 
• A raiz se conecta aos 2 filhos 
 
 11
 
Exemplo: Inserindo o 41 
 
• Antes da inserção 
 
 
 
 
 
 
 
• Depois da inserção 
 
 
 
 
 
4 
 
 
 
 
 
 
 
No exemplo, a raiz é dividida. Este processo cria uma nova raiz 
que está em um nível maior do que a antiga. Dessa forma, a 
altura total da árvore é aumentada em um. Outra maneira de 
descrever a divisão do nó é dizer que um nó de 4 é dividido em 
3 nós de 2. 
26 49 72
8252 6131 359 13
A B C 
Raiz que será 
dividida
26
8252 6131 35 419 13
A 
B 
C 
72
49
Novo nó
49 é movido 
para cima
41 é inserido
72 se move 
para a direita
26 permanece
Nova raiz 
 12
 
 Divisão de nós para baixo 
 
Todos os nós completos são divididos para baixo, e uma divisão 
não pode causar um efeito de volta pela árvore. É garantido que o 
pai de qualquer nó que está sendo dividido não esteja completo, e 
pode, portanto, aceitar o item de dados B sem precisar ele 
mesmo ser dividido. É claro que se esse pai já tem dois filhos, 
quando o seu filho for dividido, ele ficará cheio. Entretanto, isso 
apenas significa que ele será dividido quando a próxima inserção 
o encontrar. 
 
Exemplo: Inserindo os valores 70-50-30-40-20-80-25-90-75-10 
 
 
 
 
 
 
 
 
 
 
70 50 70 30 50 70
30 50 70
A B C 
Raiz que será 
dividida
30 40
A 
B 
C 
70
50
Novo nó
50 é movido 
para cima
70 se move 
para a direita
30 permanece 
Nova raiz
40 é inserido
20 30 40 70
50
20 30 40 70 80
50
 13
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
20 25
30 50
Novo nó 
A 
B 
C 
40
30 é movido 
para cima
25 é inserido
40 se move 
para a direita
20 permanece 
70 80
20 25
30 50
40 70 80 90
Nó que será 
dividido
B C A 
20 30 40 70 80
50
Nó que será 
dividido
B C A 
20 25
30 50 80
40 70 75
B 
A 
Novo nó
C 
9030 é movido 
para cima
75 é inserido
90 se move 
para a direita70 permanece
80 é movido 
para cima
 14
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
20 25
30 50 80
40 70 75 90
A B C 
Raiz que será 
dividida
30
9070 754010 20 25
A 
B 
C 
80
50
Novo nó 
50 é movido 
para cima
10 é inserido 
80 se move 
para a direita
30 permanece 
Nova raiz