Árvores rubro-negras

Páginas: 7 (1567 palavras) Publicado: 6 de outubro de 2011
ÁRVORES RUBRO-NEGRAS
Uma árvore rubro-negra é uma árvore binária balanceada onde cada nó, além dos atributos normais dos nós de árvores binárias, tem um atributo de cor (vermelho ou preto) e um ponteiro para o nó pai.
Nas árvores rubro-negras os nós folha não são considerados importantes e por isso não contêm dados, sendo identificados apenas por um ponteiro para NULL. Em certas ocasiões todosos nós folha são representados por apenas um único nó sentinela, que é apontado por todas as referências dos nós internos a nós folhas, para economia de memória.
Árvores rubro-negras possuem as seguintes propriedades:
• Todo nó ou é vermelho ou é preto.
• A raiz é preta.
• Todas as folhas (nil) são pretas.
• Todos os filhos de nós vermelhos são pretos, não havendo dois nós vermelhosconsecutvos.
• Todo caminho de um nó para alguma de suas folhas descendentes possui o mesmo número de nós pretos.



Essas regras asseguram o balanceamento da árvore tornando a altura dela a menor possível. O maior caminho da raiz a uma folha não é maior que duas vezes o menor caminho para outra folha da árvore. Isso ocorre porque todos os caminhos até as folhas possuem o mesmo número de nós pretos eo menor caminho possui todos os nós pretos e o maior possui nós vermelhos e pretos alternados, uma vez que não é possível haver dois nós vermelhos seguidos.
Desta forma uma árvore rubro-negra, tendo a menor altura possível, possui um tempo de busca O(log n), onde n é o número total de nós da árvore.

INSERÇÃO EM UMA ÁRVORE RUBRO-NEGRA
As operações de inserção ou remoção podem gerarresultados que violem as propriedades de uma árvore rubro-negra. Por isso, depois das operações é necessário que seja realizada uma restauração das propriedades das árvores como modificações de cores de nós e rotações de árvore.
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 ponteiros dos nósrotacionados.
Sempre que um nó é inserido ele é da cor vermelha (exceto se for raiz). A inserção é semelhante à de árvores binárias de pesquisa, mas com o tratamento das cores. Se o nó antecessor ao novo for vermelho será necessário alterar as cores. O que acontece depois depende dos nós vizinhos.
Algoritmo para inserção:
Sendo que:
- a cor do nodoNulo é PRETO.
- pai da raiz de uma arvore nãovazia é o nodoNulo.
- todos os nós externos também são representados pelo mesmo nodoNulo.

enum tipoCor {RED, BLACK};

typedef struct no{
ponteiro esq, dir;
ponteiro pai;
longInt chave;
tipoCor cor;
} No;

RN-insere(raiz, k){
novoNodo = criaNodo( k )
x = raiz;
paiX = nodoNulo;
enquanto x nodoNulo
paiX = x;
se k < chave(x)
x = esq(x)senao x = dir(x)
pai(novoNodo) = paiX
se paiX = nodoNulo
raiz = novoNodo
senao se k < chave(paiX)
esq(paiX) = novoNodo
senao
dir(paiX) = novoNodo
cor(novoNodo) = RED
arrumaArvRN( raiz, novoNodo )
}

arrumaArvRN( raiz, p ){
enquanto cor(pai(p)) = RED
se pai(p) == esq(pai(pai(p))){ // insercao nasubarv.esq
tio = dir(pai(pai(p)))
se cor(tio)== RED{ //cor a dir. do avo é vermelho
cor(pai(p)) = BLACK // Caso 1
cor(tio) = BLACK
cor(pai(pai(p)) = RED
p = pai(pai(p))
}
senao{ // cor a dir. do avo é preto
se p == dir(pai(p)){ //desbal. na subarv.dir do filho esq
p = pai(p) // Caso 2: esq-dir
rotEsq(p)
}
cor(pai(p)) = BLACK // Caso 3 esq-esq
cor(pai(pai(p))) = RED
rotDir( pai(pai(p) )
}
senao{
// insercao na subarv. direita -- idem trocando dir...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Árvores rubro-negras
  • Arvores Rubro Negra
  • Arvores Rubro Negras
  • Arvores Rubro Negras
  • Abordagem de arvores rubro-negra
  • Arvores rubro-negra
  • Rubro-\negra
  • arvore rubro negra

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!