Remoção numa RBT


Remover(**_raiz, *_no)
VARS: 
    _cut     ' nó a remover efectivamente (pode ser o próprio nó ou o seu sucessor)
    _filho   ' filho do nó a remover

Se no tem um filho NIL: 
  _cut = _no
else:
  _cut = sucessor(_no)

' Chegando aqui, sabemos que _cut tem de certeza um único filho (ou zero filhos)

Seja _filho o único filho de _cut (se ambos forem NIL, qualquer um serve)

_filho.pai = _cut.pai

Se _cut.pai é NULL (_cut é a raiz): 
  *_raiz := _filho
else:                               
  se _cut é filho direito: 
    _cut.pai.fd = _filho
  else:                    
    _cut.pai.fe = _filho

' Vamos ver se removemos o nó ou o seu sucessor
Se _cut != _no (removemos o sucessor): 
  _no.chave = _cut.chave

' Só queremos fazer o fixUp se a cor do nó que removemos era preta...
Se _cut.cor == PRETO: 
  Fixup(_filho)

free(_cut)

END Remover



Fixup(**_raiz, *_no)
VARS:
     _tmp = _no
     _irmao

Enquanto _tmp != *_raiz   E   _tmp.cor == PRETO:
  Se _tmp é filho esquerdo:  
    _irmao = _tmp.pai.fd
    Se _irmao.cor == VERMELHO:
      _irmao.cor := PRETO
      _tmp.pai.cor := VERMELHO
      rotacaoesquerda (_raiz, _tmp.pai)
      _irmao := _tmp.pai.fd
    
    Se _irmao.fe.cor == PRETO   E   _irmao.fd.cor == PRETO:
      _irmao.cor := VERMELHO
      _tmp := _tmp.pai
    else:
      Se _irmao.fd.cor == PRETO:
        _irmao.fe.cor := PRETO
	_irmao.cor := VERMELHO
	rotacaodireita(_raiz, _irmao)
	_irmao := _tmp.pai.fd
      
      _irmao.cor = _tmp.pai.cor
      _tmp.pai.cor = PRETO
      _irmao.fd.cor = PRETO
      rotacaoesquerda (_raiz, _tmp.pai)
      _tmp = *_raiz
  
  else:
    _irmao = _tmp.pai.fe
    Se _irmao.cor == VERMELHO:
      _irmao.cor := PRETO
      _tmp.pai.cor := VERMELHO
      rotacaodireita (_raiz, _tmp.pai)
      _irmao := _tmp.pai.fe
    
    Se _irmao.fd.cor == PRETO   E   _irmao.fe.cor == PRETO:
      _irmao.cor := VERMELHO
      _tmp := _tmp.pai
    else:
      Se _irmao.fe.cor == PRETO:
        _irmao.fd.cor := PRETO
	_irmao.cor := VERMELHO
	rotacaoesquerda(_raiz, _irmao)
	_irmao := _tmp.pai.fe
      
      _irmao.cor = _tmp.pai.cor
      _tmp.pai.cor = PRETO
      _irmao.fe.cor = PRETO
      rotacaodireita (_raiz, _tmp.pai)
      _tmp = *_raiz
    
FIM do Enquanto
      
_tmp.cor := PRETO