Remoção Rubro Negra
Por: Carlastar • 10/12/2019 • Resenha • 1.305 Palavras (6 Páginas) • 193 Visualizações
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) )
...