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

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 $\mu$ $0 \le \mu \leq \frac{1}{2}$ $N$

$μ \leq \frac{| N_{L} | + 1}{| N | + 1} \leq 1 - μ$ $\mu \le \frac{|N_L| + 1}{|N| + 1} \le 1 - \mu$
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). $\mu' \gt \mu$ $|N_L|$ $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$ $\mu$ $\mu \gt 0$ $\mathcal{O}(\log n)$

Então a questão é:

Há alguns tal que cada grande o suficiente vermelho-preto árvore é -balanced? $\mu \gt 0$ $\mu$

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). $\mu$

data-structures binary-trees search-trees Aryabhata
fonte

@Aryabhata: o que é com a singularidade (

) em sua edição? Eu estou bem com o fato de que

μ^{'} > μ

$\mu'>\mu$

equilibrado implica

\frac{1}{3}

$\frac13$

equilibrado. Não acho que você deva encontrar o

exatopara provar que a altura é

. Estou esquecendo de algo?

\frac{1}{4}

$\frac14$

μ

$\mu$

O (\log n)

$O(\log n)$

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?

n \in N

$n \in \mathbb{N}$

Raphael

@jmad: Sem o

editar, cada árvore é trivialmente

-balanced e por isso temos uma resposta não trivial para a questão. Eu queria evitar isso.

μ^{'}

$\mu'$

0

$0$

Aryabhata

@ Rafael: Eu não entendo. O tamanho do nó da árvore

. Você está dizendo que não importa qual árvore escolhemos para

e que

? Não me parece óbvio, e é disso que se trata!

n^{t h}

$n^{th}$

n

$n$

R B_{n}

$RB_n$

μ_{n} \to 0

$\mu_n \to 0$

Aryabhata

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ós é

. Portanto, se você executar

trabalho em cada nível da árvore, o trabalho total será

O (n \log n)

$O(n\log n)$

n

$n$

O (\log n)

$O(\log n)$

O (n)

$O(n)$

O (n \log n)

$O(n \log n)$

Jeffe

Respostas:

Reivindicação : árvores rubro-negro pode ser arbitrariamente un $\mu$ -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 $T_k$ de árvores vermelho-negra para que $T_k$ tem $k$ nós de preto em cada caminho a partir da raiz para qualquer folha (virtual). Defina $T_k = B(L_k, R_k)$ com

$R_k$ a árvore completa de altura $2k - 1$ com o primeiro terço, ... Índice de cor vermelha, os outros preto, e,
$L_k$ a árvore completa da altura $k-1$ com todos os nós de cor preta.

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

Por exemplo, estes são $T_1$ , $T_2$ e $T_3$ , 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 $T_k$ é completa e tem sempre altura $k-1$ e, por conseguinte, contém $2^k - 1$ nodos. A subárvore direita, por outro lado, está completa e tem altura $2k - 1$ e, portanto, contém $2^{2k}-1$ nós . Agora, o valor do equilíbrio em $\mu$ para a raiz é

$\qquad \displaystyle \frac{2^k}{2^k + 2^{2k}} = \frac{1}{1 + 2^k} \underset{k\to\infty}{\to} 0$

o que prova que não há $\mu > 0$ conforme solicitado.

Rafael
fonte

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$

$2^{2d+1}-1$ $2^{d+1}-1$

JeffE
fonte

2^{2 d + 1} + 2^{d + 1} - 1

$2^{2d+1} + 2^{d+1} - 1$

n

$n$

n

$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