Imagine uma árvore vermelha e preta. Sempre existe uma sequência de inserções e exclusões que a cria?

41

Vamos assumir a seguinte definição de uma árvore vermelho-preta:

  1. É uma árvore de pesquisa binária.
  2. Cada nó é colorido em vermelho ou preto. A raiz é preta.
  3. Dois nós conectados por uma borda não podem ser vermelhos ao mesmo tempo.
  4. Aqui deve ser uma boa definição de uma folha NIL, como no wiki. A folha NIL é colorida em preto.
  5. Um caminho da raiz para qualquer folha NIL contém o mesmo número de nós pretos.


Questão

Suponha que você tenha implementado as operações inserte deletepara a árvore vermelho-preta. Agora, se você receber uma árvore vermelha-preta válida, sempre haverá uma sequência inserte deleteoperações que a construirão?


Motivação

Esta questão é motivada por esta questão e pela discussão desta questão .

Pessoalmente, acredito que, se você imaginar uma árvore vermelha-preta válida que consiste apenas em nós pretos (o que implica que você está imaginando uma árvore perfeitamente equilibrada), há uma sequência inserte deleteoperações que a constroem. Contudo,

  1. Eu não sei como provar com precisão que
  2. Também estou interessado no caso mais geral
alisianoi
fonte
Sua pergunta parece um pouco circular ... qualquer conjunto de operações de inserção e exclusão criará uma árvore vermelho-preta ... literalmente qualquer coisa, pois vermelho-preto é apenas uma definição. Sua pergunta está limitada a uma árvore puramente negra?
JOX
2
Não, acho que você não entendeu. Obviamente, qualquer conjunto de inserções e exclusões constrói uma árvore vermelha e preta. A questão é a seguinte: alguma árvore que se encaixa na definição é construtível por alguma sequência de inserções e exclusões? Se você receber uma árvore, poderá recriar uma sequência de inserções e exclusões?
Alisianoi 30/10/2015
2
insertdelete(h+2)2h-1 1h2h+1 1-1 1h2h-1 1h
11
@AntonTrunov obrigado, eu meio que entendo isso. Mas e o caso de uma árvore vermelha e preta geral? O que você acha, é possível construir qualquer árvore Vermelho-Preto com inserte deleteoperações?
Alisianoi
2
a) A resposta dependerá da implementação precisa de inserte delete; pode haver várias maneiras de fazer essas operações. b) Como as árvores RB são essencialmente árvores B da ordem 4, pode-se procurar inspiração. Os detalhes podem ser complicados, pois o mapeamento de RB para B (e / ou para trás) não é exclusivo.
Raphael

Respostas:

2

As operações de inserção e exclusão em uma árvore vermelho-preto incluem o balanceamento necessário para manter as propriedades vermelho-preto.

O problema com árvores negras vermelhas não inclinadas (esquerda ou direita) é que existem várias maneiras de restaurar a escuridão vermelha após a exclusão ou inserção básica.
Não é a inserção ou a exclusão que transforma a árvore, mas o reequilíbrio e a rotação que ocorrem posteriormente para preservar / restaurar a escuridão vermelha da árvore.

A descrição básica da árvore vermelho-preta não prescreve qual das rotas possíveis a seguir.
Pode não ser possível descobrir como reconstruir exatamente uma determinada árvore preta e vermelha, porque o reequilíbrio não precisa ser determinístico.

Isso foi "resolvido" com árvores negras vermelhas inclinadas para a esquerda.
Existe apenas uma maneira de fazer o balanceamento. Portanto, qualquer árvore preta vermelha inclinada pode ser reconstruída usando inserções e exclusões, porque o reequilíbrio / rotação é feito de uma maneira determinística específica.

Isso não significa que as árvores RB inclinadas à esquerda sejam melhores ou mais eficientes, o que ganham por um lado usando regras determinísticas de balanceamento, e perdem por outro por código de balanceamento mais complexo.


(h+2)2h1 1h2h+1 1-1 1h2h-1 1h vezes a camada vermelha mais baixa da árvore até atingir a raiz.

Eu acho que um algoritmo de balanceamento completo como Day-Stout-Warren seria mais eficiente.

Johan
fonte
11
Usando as operações inserte deleteno livro CLRS, você pode criar uma árvore RB válida que consiste apenas em nós pretos . O truque é inserir mais nós do que o necessário e excluir os excessivos. O algoritmo irá eliminar nós vermelhos.
Anton Trunov
@AntonTrunov, você tem um link para esse algoritmo? Seria bom incluí-lo na resposta. Não consigo encontrá-lo usando meu google-fu.
9379 Johan Johan
11
Infelizmente não tenho um link. Tentei responder à pergunta na época e criei um algoritmo para o caso especial de todas as árvores RB pretas. Eu meio que a descrevi nesse comentário, mas não forneci uma prova.
Anton Trunov
O que você quer dizer com "Isso foi 'resolvido' com árvores negras vermelhas inclinadas para a esquerda". Mesmo uma árvore preta vermelha inclinada para a esquerda tem várias maneiras de armazenar os mesmos itens.
user239558