TrabalhosGratuitos.com - Trabalhos, Monografias, Artigos, Exames, Resumos de livros, Dissertações
Pesquisar

Remoção Rubro Negra

Por:   •  10/12/2019  •  Resenha  •  1.305 Palavras (6 Páginas)  •  192 Visualizações

Página 1 de 6

AULA 10: Remocao em Arv. Rubro-negra

=======

Lema: a altura de uma arv. RN com n nodos tem altura de no maximo 2log(n+1).

Prova:

  Seja x um nodo.  Representamos por hp(x) a altura "preta" de x;  ou

  seja, a quantidade de nodos pretos a partir de x (sem incluir x)

  ate' um nodo externo.  

  Primeiro mostramos que a quantidade de nodos internos em uma

  subarvore de x e' no minimo 2^{hp(x)} - 1 por inducao na altura(h) de x.

  Se h=0, x e' um nodo externo e bh(x)=0: 2^{0} - 1 = 0.

  Se h>0 , x nao e' um nodo externo e tem  2 filhos com alturas menores que x.  

  As alturas  pretas dos filhos de x podem ser hp(x)-1

  ou hp(x), dependendo do filho  ser um nodo preto ou vermelho,

  respectivamente.  Como a altura das subarv. e' menor que a altura de

  x, pela hipotese da inducao a quantidade de nodos internos da

  subarv. com raiz em x e' pelo menos

    (2^{hp(x)-1} - 1) + (2^{hp(x)-1} - 1) + 1

  ou seja, pelo menos 2*2^{hp(x)} - 2 + 1 = 2^{hp(x)} - 1.

  Para terminar a prova, observe que em uma arv. RN de altura h pelo

  menos metade dos nodos em um caminho da raiz ate' um nodo externo sao

  pretos.  Assim hp(x) >= h/2 e  n >= 2^{h/2} -1.

  Movendo 1 e aplicando log_2 em ambos os lados temos

    log(n+1) >= log(2^{h/2})  ou seja

    h <= 2log(n+1).

Consequencia:

  busca, insercao, remocao em arv. RN e' O(log(n))

============================================================================

- remocao de nodos pretos causam desbalanceamento de todos os seus

  ancentrais. ==> um dos nodos pretos vira um "duplo preto"

- Correcao:  tentar "jogar" o desbalanceamento para cima ate' que:

  . seja encontrado um nodo vermelho

  . encontre a raiz

  . possa executar rotacoes e mudancas de cor que restaurem o balanceamento

 

remove-RN( raiz, nodoK ){ /* nodoK e' o nodo que tem a chave K a ser removida */

  se esq(nodoK) == nodoNulo ou dir(nodoK) == nodoNulo

    nodoRem = nodoK               /* se nodoK tem 0 ou 1 filho, remove nodoK */

  senao                           /* senao remove o sucessor */

    nodoRem = sucessor( nodoK )   /* neste caso o nodoRem nao tem filho esq */  

  se esq( nodoRem ) <> nodoNulo

    filho = esq(nodoRem)

  senao

    filho = dir(nodoRem)

  pai(filho) = pai(nodoRem)

  se pai(nodoRem) == nodoNulo

    raiz = filho

  senao se nodoRem == esq(pai(nodoRem))

           esq(pai(nodoRem)) = filho

        senao

           dir(pai(nodoRem)) = filho

  se nodoK <> nodoRem

     /* copia chave e dados do nodoRem para nodoK */

  se cor(nodoRem) == BLACK

    arrumaRem-RN( raiz, filho )

}

arrumaRem-RN( raiz,  p ){

  enquanto p <> raiz e cor(p) == BLACK

    se n == esquerda(pai(p)){   /* extra BLACK a esquerda */

       d = direita(pai(p))

       se cor(d) == RED{        /* Caso 1 */

         cor(d) = BLACK

         cor(pai(p)) = RED

         rotacaoEsq( pai(p) )

         d = direita(pai(p))

       }

       se cor(esquerda(d)) == BLACK e cor(direita(d)) == BLACK{

         cor(d) = RED     /* Caso 2 */

         p = pai(p)

       }

       senao{

           se esquerda(d)->cor == RED  /* direita(d)->cor == RED */

              cor(d) = RED             /* Caso 3 */

              cor(esquerda(d)) = BLACK

              rotacaoDir( d )

              d = direita( pai(p) )

...

Baixar como (para membros premium)  txt (5.3 Kb)   pdf (40.2 Kb)   docx (10 Kb)  
Continuar por mais 5 páginas »
Disponível apenas no TrabalhosGratuitos.com