Árvore Rubro-Negra

A Árvore Rubro-Negra (Red-Black Tree) é uma estrutura de dados fundamental na ciência da computação, especialmente utilizada em algoritmos que requerem rápida inserção, exclusão e busca de dados. Ela é uma árvore binária de busca balanceada, onde os nós são coloridos de vermelho ou preto, e certas propriedades são mantidas para garantir que a árvore permaneça balanceada, permitindo um desempenho eficiente em suas operações.

Descrição Geral

Uma Árvore Rubro-Negra é uma árvore binária de busca onde cada nó possui uma cor (vermelha ou preta) e segue um conjunto de regras que garantem que a árvore permaneça aproximadamente balanceada. Esse balanceamento permite que operações como busca, inserção e exclusão sejam realizadas em tempo logarítmico, ou seja, O(log ⁡n), onde n é o número de nós na árvore.

Origem e Desenvolvimento

A Árvore Rubro-Negra foi introduzida por Rudolf Bayer em 1972, como uma variante das árvores binárias B-trees, que eram utilizadas para organizar dados em sistemas de arquivos. Posteriormente, ela foi refinada por outros pesquisadores, como Leo J. Guibas e Robert Sedgewick, e se tornou uma das estruturas de dados balanceadas mais conhecidas e amplamente utilizadas em implementações de bibliotecas e sistemas.

Componentes Principais

Os principais componentes de uma Árvore Rubro-Negra são:

• Nós: Cada nó da árvore possui um valor, um ponteiro para o nó esquerdo e o direito, um ponteiro para o pai e uma cor (vermelha ou preta).
• Raiz: O nó no topo da árvore, que não possui pai.
• Folhas: Todos os nós-folha são considerados nós nulos (nulos ou NIL), e são tratados como nós pretos.

Para garantir o balanceamento, a árvore deve obedecer a cinco propriedades:

1. Cada nó é vermelho ou preto.
2. A raiz é sempre preta.
3. Todas as folhas (nós nulos) são pretas.
4. Se um nó é vermelho, ambos os seus filhos devem ser pretos (não podem existir dois nós vermelhos consecutivos).
5. Qualquer caminho de um nó até uma folha nula contém o mesmo número de nós pretos.

Metodologia e Abordagem

O balanceamento da Árvore Rubro-Negra é mantido através de operações de rotação e mudanças de cores durante a inserção e exclusão de nós. Quando uma dessas operações violaria uma das propriedades da árvore, a estrutura se autoajusta para restabelecer as regras, utilizando:

• Rotação à esquerda e rotação à direita: Estas operações são usadas para reorganizar os nós em torno de um ponto de pivô, mantendo a ordem da árvore binária.
• Recolorir: Após uma inserção ou exclusão, algumas vezes os nós são recoloridos para satisfazer as propriedades da árvore.

Vamos construir uma Árvore Rubro-Negra inserindo os seguintes valores, passo a passo, para ilustrar como as regras de balanceamento funcionam:

• Valores a inserir: 10, 20, 30

Passo 1: Inserir 10

• A árvore está vazia, então o valor 10 é inserido como a raiz.
• A raiz de uma Árvore Rubro-Negra deve ser preta.

Estado da árvore:

10 (BLACK)

Passo 2: Inserir 20

• O valor 20 é maior que 10, então é inserido como o filho direito de 10.
• Por regra, novos nós são inseridos como vermelhos.

Estado da árvore:

  10 (BLACK)
      \
      20 (RED)

Neste ponto, a árvore ainda está balanceada, pois o nó pai (10) é preto, e não há dois nós vermelhos consecutivos.

Passo 3: Inserir 30

• O valor 30 é maior que 10 e maior que 20, então é inserido como o filho direito de 20.
• O novo nó 30 é inserido como vermelho.

Estado da árvore antes de balancear:

  10 (BLACK)
      \
      20 (RED)
          \
          30 (RED)

Problema:

Aqui há uma violação da regra de que dois nós vermelhos consecutivos não são permitidos (20 e 30). Agora precisamos corrigir isso através de rotações e recolorações.

Correção: Rotação à Esquerda

• Para balancear a árvore, fazemos uma rotação à esquerda em torno de 10. O nó 20 se torna a nova raiz, 10 passa a ser o filho esquerdo de 20, e 30 permanece como o filho direito de 20.

Estado após a rotação:

      20 (BLACK)
     /     \
  10 (RED) 30 (RED)

Agora a árvore está balanceada. A raiz é preta, e não há dois nós vermelhos consecutivos.

Resumo do Processo:

• Inserimos os valores 10, 20, 30.
• Após a inserção do valor 30, houve uma violação das regras de cor, o que exigiu uma rotação à esquerda e uma recoloração para restaurar o balanceamento.
• No final, a árvore está balanceada com todos os nós seguindo as regras da Árvore Rubro-Negra.

Implementação de Exemplo

Abaixo, implementação de referência em Python:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.parent = None
        self.color = "RED"

class RedBlackTree:
    def __init__(self):
        self.NIL = Node(None)
        self.NIL.color = "BLACK"
        self.root = self.NIL

    def insert(self, value):
        new_node = Node(value)
        new_node.left = self.NIL
        new_node.right = self.NIL

        y = None
        x = self.root

        while x != self.NIL:
            y = x
            if new_node.value < x.value:
                x = x.left
            else:
                x = x.right

        new_node.parent = y
        if y is None:
            self.root = new_node
        elif new_node.value < y.value:
            y.left = new_node
        else:
            y.right = new_node

        self._fix_insert(new_node)

    def _fix_insert(self, k):
        while k.parent and k.parent.color == "RED":
            if k.parent == k.parent.parent.right:
                u = k.parent.parent.left
                if u.color == "RED":
                    u.color = "BLACK"
                    k.parent.color = "BLACK"
                    k.parent.parent.color = "RED"
                    k = k.parent.parent
                else:
                    if k == k.parent.left:
                        k = k.parent
                        self._right_rotate(k)
                    k.parent.color = "BLACK"
                    k.parent.parent.color = "RED"
                    self._left_rotate(k.parent.parent)
            else:
                u = k.parent.parent.right
                if u.color == "RED":
                    u.color = "BLACK"
                    k.parent.color = "BLACK"
                    k.parent.parent.color = "RED"
                    k = k.parent.parent
                else:
                    if k == k.parent.right:
                        k = k.parent
                        self._left_rotate(k)
                    k.parent.color = "BLACK"
                    k.parent.parent.color = "RED"
                    self._right_rotate(k.parent.parent)
            if k == self.root:
                break
        self.root.color = "BLACK"

    def _left_rotate(self, x):
        y = x.right
        x.right = y.left
        if y.left != self.NIL:
            y.left.parent = x
        y.parent = x.parent
        if x.parent is None:
            self.root = y
        elif x == x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.left = x
        x.parent = y

    def _right_rotate(self, x):
        y = x.left
        x.left = y.right
        if y.right != self.NIL:
            y.right.parent = x
        y.parent = x.parent
        if x.parent is None:
            self.root = y
        elif x == x.parent.right:
            x.parent.right = y
        else:
            x.parent.left = y
        y.right = x
        x.parent = y

    def inorder_traversal(self, node):
        if node != self.NIL:
            self.inorder_traversal(node.left)
            print(f"{node.value} ({node.color})", end=" ")
            self.inorder_traversal(node.right)

Aplicabilidade e Casos de Uso

Árvores Rubro-Negras são amplamente utilizadas em sistemas que requerem operações eficientes de inserção, busca e remoção, como em:

• Sistemas de banco de dados: Estruturas como índices para acessar rapidamente grandes volumes de dados.
• Compiladores: Manutenção de tabelas de símbolos.
• Bibliotecas padrão: Em muitas linguagens de programação (C++, Java), árvores rubro-negras são usadas para implementar mapas e conjuntos.

Benefícios e Vantagens

• Eficiência: Como a árvore permanece balanceada, as operações de busca, inserção e remoção têm um desempenho garantido de O(log⁡n).
• Simplicidade: As operações de balanceamento, embora detalhadas, são relativamente simples de implementar.
• Uso prático: Suas propriedades fazem da árvore uma escolha sólida para problemas que requerem uma estrutura de dados balanceada e eficiente.

Limitações e Considerações

• Operações complexas: As operações de inserção e remoção, especialmente o balanceamento com rotações, podem ser difíceis de entender e implementar corretamente.
• Espaço adicional: Armazenar a cor de cada nó adiciona uma pequena sobrecarga de memória.
• Não é perfeitamente balanceada: Embora a árvore seja “aproximadamente” balanceada, outras árvores, como AVL, podem ser mais rigorosamente balanceadas, oferecendo melhor desempenho em cenários específicos.

Comparação com Outras Estruturas de Dados

Em comparação com a Árvore AVL, por exemplo, a Árvore Rubro-Negra é mais flexível em termos de balanceamento, o que pode resultar em operações de inserção e remoção mais rápidas. No entanto, as árvores AVL mantêm um balanceamento mais rigoroso, oferecendo buscas mais rápidas em alguns casos.

Implementação e Adaptação

A implementação de uma Árvore Rubro-Negra pode ser feita em várias linguagens de programação. Muitos frameworks e bibliotecas de linguagem já incluem implementações prontas de árvores rubro-negras, como a TreeMap em Java ou o std::map em C++. Para adaptá-la, é importante entender a necessidade do problema e verificar se o balanceamento logarítmico se adequa à aplicação.