1 Árvore Rubro-Negra

Nesse texto vamos abordar um tipo especifico de Árvore Rubro Negra, as esquerdistas, ou em inglês left-leaning, isso porque elas são um pouco mais simples de entender do que o caso geral.
Nessas árvores os nós podem ter duas cores: Vermelho e Negro. Entretanto também é possível fazer uma definição equivalente em que as ligações entre os nós é que tem essas cores.

Árvores binárias de busca no geral seguem as seguintes propriedades:

São árvores binárias, então cada nó tem dois filhos: o esquerdo e o direito, e cada filho é por si, também uma árvore binária.
Uma árvore binária pode ser vazia, nesse caso representamos ela simplesmente pelo valor None.
São de busca: Dado alguma forma de comparar o valor armazenado em cada nó, os valores menores do que o pai estão na subárvore esquerda, e os valores maiores do que o pai estão na subárvore direita.

Uma árvore com a raiz x, ligado por uma linha abaixo e a esquerda, um triangulo grande representa toda a subárvore esquerda onde estão os valores menores que x, abaixo e a direita de x, também ligado por uma linha um triangulo representa toda a subárvore direita onde estão os elementos maiores que x

As árvores binárias de busca rubro-negras seguem mais algumas propriedades:

Todo nó é vermelho ou negro.
Nas árvores esquerdistas um nó vermelho sempre é filho esquerdo do seu pai. Como o nó raiz é negro.
Um nó vermelho só tem filhos negros.
As árvores vazias (None) são as folhas e são negras.
Para cada nó x, o caminho para qualquer folha descendente (None) tem o mesmo número de nós negros. Não contamos o próprio nó x e chamamos essa quantidade de altura negra.

Verifique que a seguinte árvore é rubro-negra esquerdista.

Uma árvore binária com raiz 5, com filhos 3 e 7, o 3 tem filhos 2 e 4, o 2 tem o filho esquerdo 1, e o 7 tem o filho esquerdo 6, todas as folhas são Nulos. O 1 o 3 e o 6 são vermelhos.

Por quê esse tipo de árvore é balanceado? Essa pergunta exigiria uma prova formal, mas vou ficar com uma intuição que deve ser suficiente para te convencer: Como não existem dois nós vermelhos consecutivos, para alcançar uma folha, o melhor caso seria se o caminho só tivesse nós negros, digamos h nós. Para alcançar qualquer outro nó folha, o pior caso seria um caminho composto por nós vermelhos e negros alternados. Mas como o número de nós negros é o mesmo, o caminho total no pior caso seria 2h.

Vamos fazer um código em python para representar um nó. Vou usar o atributo cor como um boleano, se o nó tiver cor (se cor = True) o nó é vermelho, se ele não tem cor (se cor = False) ele é negro. Suponha que uma árvore rubro-negra esteja respeitando todas as propriedades, como vamos adicionar um novo nó, se ele for preto podemos estragar a propriedade da altura negra, por isso, sempre que adicionamos um novo nó, ele será vermelho.

class noh:
   def __init__(self, dado):
       self.dado = dado
       self.esq = None
       self.dir = None
       self.cor = True

Considere então que vamos adicionar nosso primeiro nó na árvore. Para respeitar a propriedade que a raiz é sempre negra, nós inserimos um novo nó e logo em seguida deixamos ele negro. Depois vamos inserir o número 7 como em uma árvore binária de busca tradicional obtendo o seguinte resultado

uma raiz com 5 e dois filhos None → Uma raiz 5 com filhos None e 7, com filhos None, o 7 é vermelho

Problema detectado! Essa árvore não está respeitando a propriedade que um nó vermelho deve ser o filho esquerdo do seu pai. Note que não podemos simplesmente remover o vermelho do 7, já que isso estragaria a propriedade da altura negra. Nem podemos pintar o 5 de vermelho, já que isso estragaria a propriedade de que a raiz é negra e um nó vermelho tem filhos negros.

A solução é fazer uma rotação a esquerda. Dessa forma queremos fazer uma raiz com um filho para esquerda. Para generalizar, ao invés dos None, vou colocar subárvores que poderiam estar ali, e desejamos não mexer nessas subárvores.

Uma raiz 5, cujo filho esquerdo é uma subárvore representada pelo número 3, e o filho direito é o 7, como filhos duas subárvores representadas pelos valores 6 e 8 → Uma raiz 7, cujo filho esquerdo é o 5 que por sua vez tem como filhos duas subárvores representadas pelos valores 3 e 6. O filho direito do 7 é uma subárvore representada pelo número 8. O 5 é vermelho

O código para essa rotação seria assim:

def rotacionaEsquerda(y):
   x = y.dir
   y.dir = x.esq
   x.esq = y
   x.cor = y.cor
   y.cor = True
   return x

Mas agora suponha que inserimos o nó 3 (ou que ele já estivesse lá e fosse vermelho. Novamente não podemos simplesmente remover a cor do 3 ou do 5, pois isso afetaria a propriedade da altura negra. Então a solução é fazer uma rotação a direita no 7, que vai transformar a linha colocando o 5 na raiz e o 3 e o 7 como irmãos.

Uma árvore com a raiz 7 seu filho esquerdo é o 5 e o filho esquerdo do 5 é o 3. 5 e 3 são vermelhos. As demais partes são subárvores, o 3 tem duas subárvores, representadas pelo 1 e pelo 4. O 5 tem como filho esquerdo uma subárvore representada pelo 6 e o 7 tem como filho direito uma subárvore representada pelo valor 8 → Uma árvore com a raiz 5 seu filho esquerdo é o 3 e o filho direito é o 7. 3 e 7 são vermelhos. As demais partes são subárvores, o 3 tem duas subárvores, representadas pelo 1 e pelo 4. O 7 tem duas subárvores, representadas pelo 6 e pelo 8

O código dessa rotação segue abaixo:

def rotacionaDireita(y):
   x = y.esq
   y.esq = x.dir
   x.dir = y
   x.cor = y.cor
   y.cor = True
   return x

Só que agora temos um nó vermelho que é filho direito. Mas se fizermos uma rotação a esquerda voltamos no problema anterior. Então vamos precisar de mais uma operação, que é a sobeVermelho. Note que dois filhos vermelhos e um pai negro, se o vermelho vai para o Pai a altura negra permanece a mesma. E mais, note que a raiz é o único nó que pode trocar de vermelho para negro sem prejudicar a propriedade da altura negra. Segue o código da sobeVermelho.

Uma árvore com a raiz 5 seu filho esquerdo é o 3 e o filho direito é o 7. 3 e 7 são vermelhos. As demais partes são subárvores, o 3 tem duas subárvores, representadas pelo 1 e pelo 4. O 7 tem duas subárvores, representadas pelo 6 e pelo 8 → Uma árvore com a raiz 5 vermelha seu filho esquerdo é o 3 e o filho direito é o 7. 3 e 7 agora são negros. As demais partes são subárvores, o 3 tem duas subárvores, representadas pelo 1 e pelo 4. O 7 tem duas subárvores, representadas pelo 6 e pelo 8

Nesse caso, se o 5 for a raiz, ela também precisa ficar negra.

def sobeVermelho(y):
   y.cor = True
   y.esq.cor = False
   y.dir.cor = False

Por fim precisamos de 2 funções auxiliares:

def ehVermelho(y):
   if y == None:
       return False
   else:
       return y.cor

def ehNegro(y):
   if y == None:
       return True
   else:
       return y.cor == False

e a inserção:

def insere_aux(raiz, dado):
   if raiz == None:
       return noh(dado)
   elif dado < raiz.dado:
       raiz.esq = insere_aux(raiz.esq, dado)
   elif dado > raiz.dado:
       raiz.dir = insere_aux(raiz.dir, dado)
   else:
       #jah existe esse dado, ignorar
       return raiz

   if ehVermelho(raiz.dir) and ehNegro(raiz.esq):
       raiz = rotacionaEsquerda(raiz)
   if ehVermelho(raiz.esq) and ehVermelho(raiz.esq.esq):
       raiz = rotacionaDireita(raiz)
   if ehVermelho(raiz.esq) and ehVermelho(raiz.dir):
       sobeVermelho(raiz)
   return raiz

def insere(raiz, dado):
   raiz = insere_aux(raiz, dado)
   raiz.cor = False
   return raiz

A busca é igual ao da árvore binária.

def busca(raiz, dado):
   if raiz == None:
       return raiz
   if dado < raiz.dado:
       return busca(raiz.esq, dado)
   if dado > raiz.dado:
       return busca(raiz.dir, dado)
   return raiz