1111111

Arvores Rubro-Negras * É um tipo de árvore criada em 1972 com o nome de árvores binárias simétricas. * Assim como as árvores binárias comuns, as árvores rubro-negras possuem um conjunto de operações (tais como inserção, remoção e busca), porém são geralmente mais eficientes devido ao fato de estarem sempre balanceadas. * Este balanceamento se dá justamente pela característica que dá nome à árvore, que vem de um bit extra em cada nó que determina se este é "vermelho" ou "preto" dentro do conjunto de regras que rege a árvore. * Além deste bit, cada nó também conta com os campos dados do nó, filho esquerdo do nó, filho direito do nó e pai do nó.

struct node * grandparent(struct node *n)
{
if ((n != NULL) && (n->parent != NULL)) return n->parent->parent; else return NULL;
}
struct node * uncle(struct node *n)
{
struct node *g = grandparent(n); if (g == NULL) return NULL; // No grandparent means no uncle if (n->parent == g->left) return g->right; else return g->left;
}

Regras: * Uma árvore rubro-negra estará sempre balanceada pois segue o seguinte conjunto de regras: * cada nó da árvore possui um valor * a cada novo nó inserido na árvore obedecerá o esquema de menor para o lado esquerdo e maior para o lado direito. * a cada nó é associada uma cor: vermelha ou preta. * o nó raiz é sempre preto. * nós vermelhos que não sejam folhas possuem apenas filhos pretos. para cada nó, todos os caminhos do nó até qualquer folha passa pelo mesmo número de nós pretos.
Regras – Inserção * A cada vez que uma operação é realizada na árvore, testa-se o conjunto de propriedades descritos anteriormente e são efetuadas rotações e ajuste de cores até que a árvore satisfaça todas estas regras. * Uma rotação é uma operação realizada na árvore para garantir seu balanceamento. Na rubro-negra pode ser feita a direita e a esquerda, onde são alterados os