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

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

É uma árvore de pesquisa binária.
Cada nó é colorido em vermelho ou preto. A raiz é preta.
Dois nós conectados por uma borda não podem ser vermelhos ao mesmo tempo.
Aqui deve ser uma boa definição de uma folha NIL, como no wiki. A folha NIL é colorida em preto.
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,

Eu não sei como provar com precisão que
Também estou interessado no caso mais geral

data-structures search-trees balanced-search-trees 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

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

insertdelete

(h + 2) \cdot 2^{h} - 1

$(h + 2) \cdot 2^h - 1$

h

$h$

2^{h + 1} - 1

$2^{h+1} - 1$

h * 2^{h - 1}

$h * 2^{h-1}$

h

$h$

@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

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:

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)⋅2^{h}−1$ $h$ $2^{h+1}−1$ $h∗2^{h-1}$ $h$ 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

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

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