Arvores Rubro Negras

Árvore Rubro-Negra

Inventada em 1972, 10 anos depois da AVL por Rudolf Bayer, sob o nome B-árvores binárias simétricas. Adquirindo em 1978 seu atual nome, por Leo J. Guibas and Robert Sedgewick.Árvore rubro-negra (do inglês Red-Black trees) A árvore rubro-negra tem esse nome devido a “coloração” de seus nós. Uma árvore rubro negra (ARN) é uma árvore binária de busca com um campo adicional que armazena se o nó é rubro ou negro. O fato de um nó ser rubro ou negro é usado como fator de balanceamento da ARN.
Rotações
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 nodos rotacionados.
Inserções
Ao inserir-se um elemento em uma árvore rubro-negra, esta é comparada com os elementos e alocada em sua posição conforme a regra 2. Ao inserir um elemento ele é sempre da cor vermelha (exceto se for o nodo raiz). A seguir a árvore analisa se o antecessor da folha. Se este for vermelho será necessário alterar as cores para garantir a regra 6.
Propriedades
1 - Cada nó tem uma cor que é rubro ou negro. Por convenção, uma árvore não vazia (ou subárvore) tem a cor de sua raiz e uma árvore vazia é negra
2 - A raiz é negra
3 - Qualquer caminho da raiz até uma subárvore vazia tem um número igual de nós negros
4 - As subárvores de um nó rubro são sempre negras
A altura de qualquer árvore rubro-negra é logarítmica no número de chaves armazenadas
A busca nas árvores rubro-negra tem complexidade logarítmica.
Uma ARN impede que uma subárvore fique com o dobro da altura da outra subárvore de um nó. class ARN
{ Private: typedef enum {RUBRO, NEGRO} cor; typedef struct no *ptr; struct no { t chave; ptr esq; ptr dir; cor tipo; }; ptr raiz; Public: // métodos...
}

Árvore 2-3-4 As árvores 2-3-4 são árvores multidirecionais, ou seja, cada nó poderá ter um, dois ou três campos de