O que é uma árvore rubro-negra, por José de Menezes

As árvores rubro-negras são árvores de busca binárias com um bit extra por nó (informação sobre a cor), que pode ser rubra ou negra. Cada nó de uma árvore rubro-negra contém os campos cor, chave, esqueda, direita e pai. Se o filho ou o pai de um nó não existir, ele receberá valor null . Uma árvore binária de busca é uma árvore rubro-negra se satisfaz as seguintes propridedades

1. Todo nó é ou rubro ou negro
2. Toda folha (nulo) é negra
3. Se um nó é rubro, então seus dois filhos são negros
4. Todo caminho de um nó até uma folha contém o mesmo número de nós negros.

A altura-negra (black-height) de um nó x bh(x), é o número de nós negros em qualquer caminho de x até uma folha, sem contar x.

A árvore rubro-negra é uma boa estrutura para efetuar buscas e manipulações em conjuntos ordenados de elementos. O tempo das operações inserção, remoção e busca em árvores rubro-negras (ARNs) é O(log n).

Lema
Uma árvore rubro-negra com n nós internos tem altura máxima de 2log(n+1)

Prova

Mostre que uma sub-árvore começando em x contém no mínimo
2^bh(x)-1 nós internos. Por indução na altura de x:

se x é uma folha então bh(x) = 0, 2^bh(x)-1
Assuma que x tem altura h, os filhos de x tem altura h-1
a altura-negra dos filhos de x é ou bh(x) ou bh(x) -1
Por indução nos filhos de x a sub-árvore tem 2^bh(x)-1-1 nós internos
Então a sub-árvore começando em x contém

2^bh(x)-1-1 + 2^bh(x)-1-1 + 1 = 2^bh(x)-1 nós internos

seja h = altura da árvore com raíz em x
bh(x) >= h/2
Portanto n >= 2^h/2-1 <=> n + 1 >= 2h/2 <=> lg(n+1) >= h/2
h <= 2lg(n+1)

Espero ter ajudado, abração!!