Árvores Binárias de Pesquisa Auto-Balanceáveis

Para evitar a degeneração da árvore binária em uma lista encadeada, causada pela inserção ordenada de elementos, foram desenvolvidos diversos modelos de árvores que se reorganizam de forma a manter uma estrutura balanceada, reduzindo a altura da árvore mantendo a eficiência dos algoritmos.

Árvore AVL

As árvores AVL foram as primeiras estruturas de árvores binárias de pesquisa auto-balanceáveis criadas, e foram propostas em 1962 pelos soviéticos Georgy Adelson-Velsky e Evgenii Landis, a quem o nome da estrutura foi dedicado.

Como árvores auto-balanceáveis, as árvores AVL apresentam o modelo mais restrito de árvores que controlam o equilíbrio em relação a altura, fazendo que a árvore seja rebalanceada sempre que a altura de duas sub-árvores forem maior que um. Embora essa restrição acelere a execução de algoritmos sobre os dados, ela exige mais operações na manutenção da árvore, fazendo com que sejam executadas mais execuções, na média, do que em outros modelos como a árvore rubro-negra.

Uma árvore AVL é válida se for uma árvore binária de pesquisa onde todos os elementos possuirem sub-árvores onde a diferença de suas alturas for menor do que um. Esta diferença de altura é dada pelo fator de balanceamento (Equação 1).

\(\begin{eqnarray} FB(n) = H(n.esq) - H(n.dir) \end{eqnarray}\)

Como pode ser visto, o cálculo do fator de balanceamento depende da altura do nó. A altura de um nó é dada pelo maior número de arcos entre um nó e uma folha, porém é mais fácil implementar este cálculo assumindo que uma folha possui altura igal a 1 (um), ou considerando que as folhas são nulas, e dessa forma todos os nós com dados terão, ao menos, altura igual a 1. A Equação 2 mostra como é possível implementar o cálculo desta forma, de maneira recursiva.

\(\begin{eqnarray} H(n) = 1 + max(H(n.esq), H(n.dir)) \end{eqnarray}\)

De posse do valor do fator de balanceamento, é possível verificar se um nó é um nó AVL válido ou não, verificando se o módulo do fator de balanceamento é menor que dois (2) (Equação 3)[^1].

\(\begin{eqnarray} AVL(n) = |FB(n)| < 2 \end{eqnarray}\)

O fator de balanceamento também mostra para que lado a árvore está desbalanceada, caso este valor seja positivo, a árvore possui o lado esquerdo maior, caso seja negativo, o lado direito será maior. Quando o fator de balanceamento é zero (0), os dois lados possui exatamente a mesma altura. No entanto, o fator de balanceamento só faz referência a altura das sub-árvores, não ao número de nós que estas possuem, o que é útil para algoritmos que percorrem a árvore na direção da raiz para as folhas, e não em percursos que incluem todos os nós de uma sub-árvore.

A operação de pesquisa em uma árvore AVL segue o mesmo procedimento que qualquer outra árvore binária de pesquisa, apenas as operações de inserção e exclusão é que devem ser alteradas.

O processo de inserção em uma árvore AVL segue o procedimento de inserção em uma árvore binária de pesquisa comum. Após a inserção, o nó pai do novo nó é avaliado com relação à regra de criação da árvore AVL, e então os nós anteriores são avaliados em direção à raiz da árvore até que esta seja atingida, ou que a altura de um nó não se altere.

Ao avaliar um nó, caso a regra de validação da AVL não seja respeitada, o nó deve ser corrigido. Esta correção do nó pode necessitar de uma ou duas rotações, além do percurso em todos os nós descendentes do nó corrigido para recalcular suas alturas (Algoritmo 1).

Balanceamento de um nó AVL.

rebalance(node):
    if node == null:
        return
    if FB(node) == -2
        if FB(node.right) == +1
           node.right = rotate_right(node.right)
        root = rotate_left(node)
    else if FB(node) == +2
        if FB(node.left) == -1
            node.left = rotate_left(node.left)
        root = rotate_right(node)
    post_order_traverse(root, {height_update})
    rebalance(root.parent)

A remoção em uma árvore AVL segue a mesma idéia da inserção, após a remoção do elemento da árvore binária de pesquisa, o processo de validação e correção é iniciado a partir do nó pai, do nó excluído.

Árvore Rubro-Negra (Red-Black)

O modelo de árovre binária de pesquisa auto-organizável Árvore Rubro-Negra (Red-Black Tree) (Figura 1), onde cada nó da árvore tem um bit extra de informação, que representa a cor do nó, que pode ser vermelho ou preto. Associando a cor do nó e um conjunto de regras de formação, e o uso de rotação de ároveres binárias de pesquisa (para alterar a estrutura da árvore mantendo a ordenação dos elementos) é possível manter os algoritmos de manutenção e pesquisa da árvore eficientes, com todas as operações mantendo o limite superior \(O(lg N)\).

Árvore Rubro-Negra Red-black Tree

A árvore Red-Black possui cinco regras que precisam ser mantidas para garantir o balanceamento, que embora não seja perfeito, permite que a árvore mantenha a eficiência, e faz com que as operações de rotação sejam menos freqüentes do que em relação a outros modelos como a ávore AVL.

  1. Cada nó da árvore pode ser vermelho ou preto.
  2. A raiz da árvore é sempre preta.
  3. Toda folha da árovore é nula e preta.
  4. Se um nó é vermelho, todos os seus filhos são pretos.
  5. Todo caminho de um nó qualquer para qualquer folha descendente deste nó possúi o mesmo número de nós pretos

Alguns autores, substituem as regras 2 e 3 por "as folhas são nulas e tem a mesma cor da raiz". Essa alteração é normalmente utilizada quando da implementação da árvore com um nó sentinela, que faz o papel de folhas.

Para implementar as operações de uma árvore Rubro-Negra, é necessário que o nó da árvore Rubro-Negra (Algoritmo 1) contenha um link para o nó pai, e o controle da cor do nó.

Rotação de uma BST à esquerda.

São necessárias também algumas operações para identificar nós relativos a um outro nó na árvore, como os nós avô (grandparent) e tio (uncle) (Algoritmo 2).

Identificação do avô e tio.

Inserção em uma Árvore Rubro-Negra

A inserção em uma árore Rubro-Negra inicia com a inserção do novo elemento na árvore da mesma forma que os elementos são inseridos em uma árvore binária de pesquisa comum, com a única diferença que o nó inserido deve ser pintado de vermelho. Com a inserção desse nó, a regra 2 da árvore, ou a regra 4 podem ficar inválidas, e portanto, a partir do nó inserido (N) o processo de inserção analisa até cinco casos para corrigir novamente a arvore.

O processo de correção inicia, então no caso 1 (Algoritmo 3), e neste caso, o nó N analisado pode ser a nova raiz da árvore, e nesse caso só é necessário alterar a cor do nó para preto (diz-se pintar o nó de preto), e o algoritmo pode terminar. Caso o nó não seja a raiz, o processo continua a partir do caso 2.

Inserção Red-Black: caso 1.

insert_case_1(Node n):
    if (n.parent == null)
        n.red = false
    else
        insert_case_2(n)

No caso 2 (Algoritmo 4), se o nó pai é preto, nenhuma regra da árvore é quebrada, pois nenhum nó vermelho ganhou um filho vermelho, e em nenhum caso, o número de nós pretos nos caminhos até as folhas foram alterados, uma vez que nenhum nó preto foi inserido na árvore, logo, o processo de correção só deve seguir para o caso 3 quando o pai do nó N for vermelho.

Inserção Red-Black: caso 2.

insert_case_2(Node n):
    if (n.parent.red)
        insert_case_3(n)

Se tanto o pai quanto o tio do nó N são vermelhos, pode-se trocar a cor destes e do avô, e reiniciar o processo de ajuste a partir do avô. Caso os nós não sigam essa configuração, o processo de correção segue para o caso 4 (Algoritmo 5).

Inserção Red-Black: caso 3.

insert_case_3(Node n):
    u = n.uncle()
    if (u != null and u.red):
        n.parent.red = false
        u.red = false
        g = grandparent()
        g.red = true
        insert_case_1(g)
    else:
        insert_case_4(n)
}

Quando o pai é vermelho, e o tio é preto, e o nó N está em lado oposto ao pai, em relação à posição deste em relação ao avô, (Figura 2) é necessária uma rotação para que tanto o pai e o nó N sejam filhos do mesmo lado. A rotação deve ser realizada para o mesmo lado que o pai é filho do avô. Indepedente do lado para o qual a rotação ocorrer, o nó N será a nova raiz desta sub-árvore, sendo o pai filho deste nó (Algoritmo 6). Após a execução deste passo, o algoritmo sempre deve executar o caso 5, utilizando como nó base o pai.

Inserção Red-Black: caso 4. Red-Black insert case 4

Inserção Red-Black: caso 4.

insert_case_4(Node n):
    g = grandparent()
    p = n.parent
    if (n == p.right and p == g.left)
        n.parent.rotate_left()
    else if (n == n.parent.left and n.parent == g.right)
        n.parent.rotate_right()
    insert_case_5(p)
}

Nó último caso, o nó N, vermelho, possui um pai vermelho, um tio preto, e tanto o pai e N estão posicionados do mesmo lado de seus respectivos nós pai (Figura 3). Nesta situação, o pai é pintado de preto, o avô pintado de vermelho, e a árvore é rotacionada no avô, na direção contrária à posição dos nós (Algortimo 7).

Inserção Red-Black: caso 5. Red-Black insert case 4

Inserção Red-Black: caso 5.

insert_case_5(Node n):
    g = grandparent()
    n.parent.red = false
    g.red = true
    if (n = n.parent.left)
        g.rotate_right()
    else
        g.rotate_left()