Em uma árvore AVL, usamos a rotação como uma ferramenta para fazer o balanceamento após a inserção que causou desequilíbrio. Na árvore Rubro negra, alem o do balanceamento, usa a mudança de cor.
Tenta-se mudar as cores em primeiro lugar, caso não funcione, segue para a rotação.
Seja k o nó recém-inserido.
Seja k o nó recém-inserido.
- Como no caso de um BST primeiro procurar por k; Isso nos dá o lugar onde temos de inserir k.
- Criamos um novo nó com chave k e inseri-lo neste local.
- O novo nó está colorido em vermelho.
- Como o nó inserido é colorido em vermelho, a altura preta da árvore permanece inalterada.
- No entanto, se o pai do nó inserido também é vermelho, então temos um problema de vermelho duplo.
Caso 1
- O pai do nó inserido (a) é vermelho.
- Pai de (a) deve ser preto (b)
- A outra criança de (b) é preta (c).
Caso 2
- O pai do nó inserido (a) é vermelho.
- Pai de (a) deve ser preto (b)
- A outra criança de (b) também é vermelha (c).
- O pai de b também poderia ser vermelho. Nesse caso, o problema de vermelho duplo ascende um nível.
- Repetimos esse processo no próximo nível.
- Eventualmente, poderemos colorir a raiz vermelha.
- Nesse caso, recolorimos a raiz negra. Isso aumenta a profundidade preta de cada nó externo em 1.
- Na árvore-B (2-4) isso equivale em dividir o nó raiz.
Precisamos fazer no máximo uma rotação, movendo-se para cima da árvore, mas apenas mudando a cor dos nós.
Nenhum comentário:
Postar um comentário