Algoritmo de exclusão para uma árvore negra vermelha

Question

Pessoal, estou tentando implementar o algoritmo de exclusão para uma árvore negra vermelha e estou tendo problemas em entender a linha três desse algoritmo (de um livro "Introdução aos algoritmos" Segunda edição):

1 se esquerda [z] = nil [t] ou direita [z] = nil [t
2 Então y ← z
3 else Y ← Tree-Scescessor (Z)
4 se deixado [y] ≠ nil [t
5 Então x ← esquerda [y
6 else x ← à direita [y
7 p [x] ← p [y
8 se p [y] = nil [t
9 Em seguida, raiz [T] ← X
10 else se y = esquerda [p [y]
11 Então saiu [p [y]] ← x
12 else Right [p [y]] ← x
13 se y 3 ≠ z
14 Então chave [z] ← Key [y
15 Copiar dados de satélite de Y em z
16 Se cor [y] = preto
17 Então RB-Delete-Fixup (T, X)
18 retorno y

Primeiro de tudo, não há nenhum lugar neste livro explicou como o sucesso da árvore deve parecer (sem algoritmo para isso), mas eu encontrei esta página: E se eu alimentar esse algoritmo Whit 11,2,1,7,5,8,14,15,4 e depois tente excluir 7, encontra antecessor Mas se eu tentar excluir 11, encontra sucessor. E é isso que eu não consigo entender. Por que às vezes é preciso antecessor e às vezes sucessor? Que critérios são levados em consideração ao tomar essa decisão? A cor de um nó?
Obrigada.

PS Eu também não entendo bem o que está escrito na linha número 13. Isso significa que se Y tiver três cores (nem preto nem vermelho) ou outra coisa?

Answer 1

O sucessor de árvores (como o oposto do predecessor de árvores [que está naquele livro que acredito]) é geralmente definido para árvores de pesquisa binária como o nó com a próxima chave mais alta. Como determina que depende do tipo (preto nesse caso) e tenho quase certeza de que seu livro deixa o método sucessor como um exercício. (Lembro -me do problema: P)

Answer 2

Eu acho que você está lendo CLRS 2ª edição.

O sucessor de árvore é introduzido no Capítulo 12 Seção 2 - "12.2 Árvore de pesquisa binária de consulta". E, ao contrário do que Jesse Naugher diz, não depende do tipo de árvores de busca binária.

A linha 13 que você citou é um erro de digitação. Deve ser "se y! = Z".

Answer 3

Você pode se referir ao seguinte código.

http://code.google.com/p/cstl/source/browse/src/c_rb.c