Árvores rubro-negras

Páginas: 3 (563 palavras) Publicado: 9 de agosto de 2012
UNIVERSIDADE ESTADUAL DE MATO GROSSO DO SUL

ALGORITMOS E ESTRUTURA DE DADOS II
Árvores Rubro-Negra

ERIC MACIEL CARDOSO

UNIVERSIDADE ESTADUAL DE MATO GROSSO DO SUL

Árvore Rubro-Negra Árvore Rubro-Negra
 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

Árvore Rubro-Negra
 A todos os nós é associada uma cor que pode ser vermelha ou negra de talforma que:

1. Nós externos (folhas ou nulos) são negros; 2. Todos os caminhos entre um nó e qualquer de seus nós externos descendentes percorre um número idêntico de nós negros; 3. Se um nó é vermelho(e não é a raiz), seu pai é
negro;
Observe que as propriedades acima asseguram que o maior caminho desde a raiz uma folha é no máximo duas vezes maior que o de o qualquer outro caminho até outrafolha e portanto a árvore é aproximadamente balanceada

Árvore Rubro-Negra
 (Altura negra) A altura negra de uma árvore rubro-negra A, denotada an(A) é o número de nós negros que se encontram noscaminhos da raiz até uma folha.
18 10 3 1 5 13 22

20
16 19

27 21 24
40

12

14

17

Árvore Rubro-Negra
 Definição de um nó

Chave Ptr Esquerda

Cor(Rubro ou Negra)

Ptr Direita Inserção em Árvores Rubro-Negra

Árvore Rubro-Negra
 Ao inserir um nó x numa posição vazia da árvore (isto é, no lugar de um nó nulo) este é pintado de vermelho.

 Isto garante amanutenção do critério (2), já que um nó vermelho não contribui para a altura negra.

p

1

p 1
x

1

Árvore Rubro-Negra
[Caso 0] Se x não tem pai ou se p, o pai de x, é negro, nada mais precisaser feito já que o critério (3) também foi mantido; [Caso 1] Suponha agora que p é vermelho. Então, se p não tem pai, então p é a raiz da árvore e basta trocar a cor de p para negro
p x p

x...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Arvores Rubro Negra
  • Árvores rubro-negras
  • 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!