Mais detalhes sobre as árvores 2,3,4

Antes de cair matando nas árvore red black eu tinha dito que é interessante conhecer as árvores 2,3,4. Dei uma explicação muito breve sobre elas anteriormente. Eis mais alguns detalhes…

Suponha que você queira inserir os itens 53, 27, 75, 25, 70, 41 e 38, nessa ordem. Lembre-se que cada nó de uma árvore 2,3,4 suporta uma, duas ou três chaves. Ao inserir os primeiros 3 itens teremos apenas um único nó. O problema começa a partir da quarta inserção… O nó deve ser dividido em dois nós contendo apenas uma chave cada e a quarta chave será colocada no nó onde ela se encaixa…

2,3,4-1
Sequência de inserções (de 53 até 41 apenas).

Ao inserirmos a última chave (38), eis o que acontece: Como não há espaço no nó da esquerda, onde a chave deveria ser colocada, a chave central (27) “sobe” para o nó pai, criando uma ramificação intermediária (de dois nós filhos passamos a ter 3) onde a chave 38 e a próxima (41) são colocadas. Por que a chave 41 vai junto? Porque ela é maior que 27 e menor que 53!

Inserindo 38
Inserindo 38

A mecânica é bem simples. Todas as inserções são feitas em nós filhos, exceto quando não houver espaço, assim a chave central do nó filho “sobre” para o pai, abrindo um espaço (no nó pai) onde a nova chave e a seguinte (ou a anterior, dependendo do lado) entrarão. Com essas regras simples a árvore é mantida balanceada, já que novos nós só surgirão à medida que os demais estejam cheios e, mesmo assim, novos níveis só serão criados depois que os nós pais estejam cheios.

Eis o que acontece quando inserimos a chave 73 depois de termos inserido as chaves 16, 59 e 36 (porque a inserção desses itens na árvore anterior é trivial):

2,3,4-3

Note que a mesma coisa aconteceu no nó contendo as chaves 59, 70 e 75… Não há espaço para inserir o 73, daí a chave 70 “subiu”, abrindo um espaço onde a chave 59 foi colocada e  agora podemos inserir 73 no nó à direita.

Essa nova árvore nos apresenta um problema: O nó raiz está cheio! O que acontecerá se tentarmos inserir uma chave 46? Ela deveria ser colocada no nó que contém as chaves 36, 38 e 41, mas também não há espaço nesse nó e a chave 38 não pode simplesmente “subir”… Não tema! Basta decompor o nó pai e começar tudo de novo.

Note que, depois de decompor o nó pai teremos espaço para migrar as chaves centrais inferiores para “cima”, assim:

2,3,4-4

A árvore de cima é a anterior com o nó pai decomposto (o nó contendo as chaves 27, 53 e 70 é dividido em três nós com chaves unitárias), daí, já que sabemos que o valor 46 vai ser colocado no nó contendo as chaves 36, 38 e 41, a chave 38 “sobe”, criando mais um ramo… Como esse ramo está do lado direito do nó pai (contendo 27 e, agora, 38) a chave 36 vai para o ramo intermediário e a chave 46 é adicionada ao ramo à direita.

Não é tão complicado assim… Fazer chaves subirem é uma rotina recursiva. Se toparmos com um nó cheio, tentamos subir a chave (levando uma outra, de acordo com o critério para o espaço que vai se abrir), mas podemos topar com um nó cheio e temos que subir mais… Se chegarmos ao nó raiz e este estiver cheio, faremos a decomposição e voltamos para “subir” a chave do nó imediatamente abaixo…

Quando virmos a árvore red black isso ficará ainda mais claro, já que esse processo de “subir” a chave nada mais é que uma operação de rotação (existe mais que uma!), onde usamos um critério de “cores” para sabermos se estamos lidando com chaves centrais ou laterais (preta para centrais, vermelhas para laterais).

PS: Usei valores em vermelho aqui para destacar a chave que irá “subir” ou será a chave raiz da decomposição… não tem nada a ver com as red black trees.

 

Anúncios