Conforme já vimos, árvores binárias de busca (ABB) 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 de busca.
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.
As árvores binárias de busca permitem armazenar dados com bastante eficiência. A inserção, busca e remoção tem complexidade O(h) em que h é a altura da árvore.
Entretanto um problema pode acontecer dependendo da ordem em que são inseridos os dados na árvore. Um caso extremo, porém bastante possível, é que os dados entrem já ordenados. Nessa situação, uma árvore binária acaba virando uma lista ligada.
Uma forma de evitar esse tipo de degeneração é através das árvores binárias de busca balanceadas (ABBB). Que buscam manter a altura da árvore limitadas a O(log n) em que n é a quantidade de nós da árvore. Algumas ABBBs utilizam rotações para manter esse balanceamento, as rotações podem ser para a esquerda ou para direita, e elas devem manter as propriedades da ABB, ou seja os nós da esquerda são menores que a raiz, e os da direita são maiores. Vamos começar com uma rotação para a esquerda, no exemplo abaixo, o que queremos é fazer o 7 passar a ser a raiz, note que a subárvore α tem elementos menores que 5, β tem elementos maiores que 5 e menores que 7, e que γ tem elementos maiores que 7. Devemos manter essas subárvores nos locais corretos.
→ 
Vamos codar em python essa rotação, levando em conta que a nossa classe nó é a seguinte:
class noh: def __init__(self, dado): self.dado = dado self.esq = None self.dir = None def rotacionaEsquerda(y): x = y.dir y.dir = x.esq x.esq = y return x
Note que a rotação funciona mesmo que as subárvores sejam None. A rotação a direita é análoga.
→ 
def rotacionaDireita(y): x = y.esq y.esq = x.dir x.dir = y return x
Fazendo as rotações adequadas, conseguiremos deixar as árvores balanceadas. Entretanto não é trivial saber quais rotações são necessárias. Por exemplo, uma árvore que armazenamos primeiro o 5, depois o 7 e por fim um 6, ficaria desbalanceada da seguinte forma:
 | → |
 | → |
 |
Se tentarmos fazer uma rotação a esquerda, teremos:
→ 
A árvore continua desbalanceada, e podemos observar que uma rotação a direita só retornaria ao estado anterior. Podemos verificar que com algumas rotações adicionais nas subárvores, poderíamos enfim deixar a árvore balanceada.
Vale notar que deixar a árvore de busca perfeitamente balanceada, embora fosse muito eficiente para as operações de busca, seria demasiadamente custoso nas operações de inserção e remoção. Então o que buscamos são árvores suficientemente balanceadas. Uma das estruturas de dados que segue esse preceito, é a árvore Rubro-Negra, que veremos seu funcionamento na próxima sessão.
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. Também é possível fazer uma definição equivalente em que as ligações entre os nós é que tem essas cores.
As árvores binárias de busca rubro-negras, além das propriedades de uma ABB, ainda possuem mais algumas:
Todo nó é vermelho ou negro.
Nas árvores esquerdistas um nó vermelho sempre é filho esquerdo do seu pai. Como o nó raiz é negro.
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.
Por quê esse tipo de árvore é balanceado? Essa pergunta exigirá uma prova mais formal, mas por enquanto 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 modificar o código em python para representar um nó. Acrescentando 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.
class noh: def __init__(self, dado): self.dado = dado self.esq = None self.dir = None self.cor = True
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.
→ 
Dessa forma não estragamos a propriedade V. Se o nó 5 for negro, nada precisa ser feito e a árvore continua correta. Entretanto se o nó 5 for vermelho estaremos violando a propriedade III.
Deixaremos assim por enquanto, e consertaremos esse problema depois. Considere agora o caso em que o 4 já estava na árvore e o cinco é o novo nó a ser colocado.
→ 
Agora, embora conservamos a propriedade V, estamos violando a propriedade II. Podemos consertar essa propriedade com uma rotação a esquerda.
→ 
Que cores devem ser os nós 4 e 5, para respeitar a propriedade V? Lembre-se que a árvore em que apenas o 4 estava presente atendia todas as propriedades. Vamos considerar 2 casos: o caso em que 4 era negro, e o caso em que era vermelho.
Caso negro: Observamos que não podem ser 4 e 5 negros, já que isso aumentaria a altura negra das folhas filhas de 4. Também observamos que se 4 for negro e 5 vermelho também estaríamos reduzindo a altura negra da folha filha de 5. Concluímos que o 4 precisa ser vermelho! Já o 5 não poderá ser vermelho pois também estaríamos reduzindo a altura negra de todas as folhas da subárvore.
Caso vermelho: Nesse caso, obviamente não podemos fazer nenhum deles negros já que estaríamos mudando a altura negra. Então deixamos ambos vermelhos.
→ 
→ 
Novamente nesse último caso, estamos violando a propriedade III, mas deixaremos assim temporariamente. Observe que o que fazemos então é que o filho esquerdo da raiz da subárvore é sempre vermelho e a raiz da subárvore tem a mesma cor da raiz antiga. Podemos então alterar a função de rotacionar a esquerda.
def rotacionaEsquerda(y): x = y.dir y.dir = x.esq x.esq = y x.cor = y.cor y.cor = True return x
Agora suponha que temos a árvore abaixo e 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, da mesma forma que na rotação a esquerda a raiz da subárvore recebe a cor da raiz antiga, e podemos atualizar a rotação a direita.
→
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.
→
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