Nem todas as árvores vermelho-pretas estão equilibradas?

30

Intuitivamente, "árvores equilibradas" devem ser árvores nas quais as subárvores esquerda e direita em cada nó devem ter "aproximadamente o mesmo" número de nós.

Obviamente, quando falamos de árvores vermelhas-pretas * (ver definição no final) sendo equilibradas, na verdade queremos dizer que elas são equilibradas em altura e, nesse sentido, são equilibradas.

Suponha que tentemos formalizar a intuição acima da seguinte maneira:

Definição: Uma árvore binária é chamada balanceada, com , se para cada nó , a desigualdadeμ0μ12N

μ|NL|+1|N|+11μ

mantém e para cada , há algum nó para o qual a instrução acima falha. é o número de nós na subárvore esquerda de eé o número de nós sob a árvore com como raiz (incluindo a raiz).μ>μ|NL|N|N|N

Acredito que essas árvores sejam chamadas de árvores com peso equilibrado em algumas publicações sobre esse tópico.

Pode-se mostrar que se uma árvore binária com nós é balanceada (para uma constante ), a altura da árvore é , mantendo assim a boa pesquisa propriedades.nμμ>0O(logn)

Então a questão é:

Há alguns tal que cada grande o suficiente vermelho-preto árvore é -balanced?μ>0μ


A definição de árvores Vermelho-Pretas que usamos (de Introdução aos Algoritmos por Cormen et al):

Uma árvore de pesquisa binária, em que cada nó é colorido em vermelho ou preto e

  • A raiz é preta
  • Todos os nós NULL são pretos
  • Se um nó é vermelho, os dois filhos são pretos.
  • Para cada nó, todos os caminhos desse nó para os nós NULL descendentes têm o mesmo número de nós pretos.

Nota: não contamos os nós NULL na definição de balanceada acima. (Embora eu acredite que não importa se o fizermos).μ

Aryabhata
fonte
@Aryabhata: o que é com a singularidade ( ) em sua edição? Eu estou bem com o fato de que 1μ>μ equilibrado implica113 equilibrado. Não acho que você deva encontrar oµexatopara provar que a altura éO(logn). Estou esquecendo de algo? 14 μO(logn)
Jmad
Além disso, você precisa de uma declaração negativa para fornecer uma corrente contra-exemplo com uma árvore para cada . Qualquer cadeia infinita que não diminua o tamanho do nó seria suficiente, não seria? nN
Raphael
@jmad: Sem o editar, cada árvore é trivialmente 0 -balanced e por isso temos uma resposta não trivial para a questão. Eu queria evitar isso. μ0
Aryabhata
@ Rafael: Eu não entendo. O tamanho do nó da árvore é n . Você está dizendo que não importa qual árvore escolhemos para R B n e que μ n0 ? Não me parece óbvio, e é disso que se trata! nthnRBnμn0
Aryabhata
1
Uma versão anterior desta pergunta alegava que o tempo de execução de um algoritmo recursivo em uma árvore vermelho-preta que realiza uma quantidade linear de trabalho em cada etapa não é necessariamente . Esta reivindicação estava incorreta; O balanço de altura implica que a profundidade de uma árvore vermelho-preto de n nós é O ( log n ) . Portanto, se você executar O ( n ) trabalho em cada nível da árvore, o trabalho total será O ( n log n ) . O(nregistron)nO(registron)O(n)O(nregistron)
Jeffe

Respostas:

31

Reivindicação : árvores rubro-negro pode ser arbitrariamente un μ -balanced.

Ideia de prova : preencha a subárvore direita com o maior número possível de nós e a esquerda com o menor número possível de nós para um determinado número k de nós pretos em cada caminho da folha da raiz.

Prova : Definir uma sequência Tk de árvores vermelho-negra para que Tk tem k nós de preto em cada caminho a partir da raiz para qualquer folha (virtual). Defina Tk=B(euk,Rk) com

  • Rk a árvore completa de altura2k-1 com o primeiro terço, ... Índice de cor vermelha, os outros preto, e,
  • euk a árvore completa da alturak-1 com todos os nós de cor preta.

Claramente, todos Tk são árvores vermelho-pretas.

Por exemplo, estes são T1 , T2 e T3 , respectivamente:


T_1
[ fonte ]


T_2
[ fonte ]


T_3
[ fonte ]


Agora vamos verificar se a impressão visual do lado direito é enorme em comparação com a esquerda. Não contarei folhas virtuais; eles não impactam o resultado.

O sub esquerda de Tk é completa e tem sempre altura k1 e, por conseguinte, contém 2k1 nodos. A subárvore direita, por outro lado, está completa e tem altura 2k1 e, portanto, contém 22k1 nós 2 k - 1 . Agora, o valor do equilíbrio em μ para a raiz é

2k2k+22k=11+2kk0

o que prova que não há μ>0 0 conforme solicitado.

Rafael
fonte
14

Não. Considere uma árvore vermelha e preta com a seguinte estrutura especial.

  • A subárvore esquerda é uma árvore binária completa com profundidade , na qual cada nó é preto.d
  • A subárvore direita é uma árvore binária completa com profundidade , na qual todo nó na profundidade ímpar é vermelho e todo nó na profundidade par é preto.2d

22d+112d+11

JeffE
fonte
22d+1+2d+11n
1
n
@ Jeff: Basicamente, a cadeia de contra-exemplo seria então um subconjunto 'denso', em vez de um subconjunto 'esparso'. Talvez eu mude a formulação da questão.
Aryabhata