¿No todos los árboles rojo-negros están equilibrados?

Intuitivamente, los "árboles equilibrados" deben ser árboles donde los subárboles izquierdo y derecho en cada nodo deben tener "aproximadamente el mismo" número de nodos.

Por supuesto, cuando hablamos de que los árboles rojo-negros * (ver definición al final) están equilibrados, en realidad queremos decir que están equilibrados en altura y, en ese sentido, están equilibrados.

Supongamos que intentamos formalizar la intuición anterior de la siguiente manera:

Definición: Un árbol binario se llama -balanced, con , si para cada nodo , la desigualdad $\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$
mantiene y para cada , hay algún nodo para el cual falla la declaración anterior. es el número de nodos en el subárbol izquierdo de yes el número de nodos debajo del árbol con como raíz (incluida la raíz). $\mu' \gt \mu$ $|N_L|$ $N$ $|N|$ $N$

Creo que estos se llaman árboles de equilibrio de peso en parte de la literatura sobre este tema.

Se puede mostrar que si un árbol binario con nodos está equilibrado (para una constante ), entonces la altura del árbol es , manteniendo así la búsqueda agradable propiedades. $n$ $\mu$ $\mu \gt 0$ $\mathcal{O}(\log n)$

Entonces la pregunta es:

¿Hay algún tal que cada árbol rojo-negro suficientemente grande esté equilibrado ? $\mu \gt 0$ $\mu$

La definición de árboles rojo-negros que utilizamos (de Introducción a los algoritmos de Cormen et al):

Un árbol de búsqueda binario, donde cada nodo es de color rojo o negro y

La raíz es negra
Todos los nodos NULL son negros
Si un nodo es rojo, sus dos hijos son negros.
Para cada nodo, todas las rutas desde ese nodo a los nodos NULL descendientes tienen el mismo número de nodos negros.

Nota: no contamos los nodos NULL en la definición de -balanced arriba. (Aunque creo que no importa si lo hacemos). $\mu$

data-structures binary-trees search-trees Aryabhata
fuente

@Aryabhata: ¿qué pasa con la unicidad ( ) en tu edición? Estoy de acuerdo con el hecho de que -balanced implica -balanced. No creo que deba tener que encontrar la exacta para demostrar que la altura es . ¿Me estoy perdiendo de algo?

μ^{'} > μ

$\mu'>\mu$

\frac{1}{3}

$\frac13$

\frac{1}{4}

$\frac14$

μ

$\mu$

O (\log n)

$O(\log n)$

jmad

Además, necesita una declaración negativa para proporcionar una cadena de contraejemplo con un árbol por cada . Cualquier cadena infinita que no disminuya en tamaño de nodo sería suficiente, ¿no?

n \in N

$n \in \mathbb{N}$

Raphael

@jmad: Sin la edición , cada árbol está trivialmente equilibrado en y, por lo tanto, no tenemos una respuesta trivial a la pregunta. Quería evitar eso.

μ^{'}

$\mu'$

0

$0$

Aryabhata

@Raphael: no entiendo. El tamaño del nodo del árbol es . ¿Estás diciendo que no importa qué árbol para y que ? No me parece obvio, ¡y de eso se trata la pregunta!

n^{t h}

$n^{th}$

n

$n$

R B_{n}

$RB_n$

μ_{n} \to 0

$\mu_n \to 0$

Aryabhata

Una versión anterior de esta pregunta afirmaba que el tiempo de ejecución de un algoritmo recursivo en un árbol rojo-negro que realiza una cantidad lineal de trabajo en cada paso no es necesariamente . Este reclamo fue incorrecto; balance de altura implica que la profundidad de un árbol rojo-negro nodo es . Por lo tanto, si realiza un trabajo en cada nivel del árbol, el trabajo total es .

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

Respuestas:

Reclamación : árboles rojo-negro puede ser arbitrariamente in- -balanced. $\mu$

Idea de prueba : llene el subárbol derecho con la mayor cantidad de nodos posible y el izquierdo con la menor cantidad posible de nodos para un número dado de nodos negros en cada ruta raíz-hoja. $k$

Prueba : defina una secuencia de árboles rojo-negros para que tenga nodos negros en cada ruta desde la raíz hasta cualquier hoja (virtual). Defina con $T_k$ $T_k$ $k$ $T_k = B(L_k, R_k)$

$R_k$ el árbol completo de altura con el primer, tercero, ... nivel de color rojo, los otros negros y $2k - 1$
$L_k$ el árbol completo de altura con todos los nodos de color negro. $k-1$

Claramente, todos los son árboles rojo-negros. $T_k$

Por ejemplo, estos son , y , respectivamente: $T_1$ $T_2$ $T_3$

T_1
^{[ fuente ]}

T_2
^{[ fuente ]}

T_3
^{[ fuente ]}

Ahora verifiquemos que la impresión visual del lado derecho sea enorme en comparación con el izquierdo. No contaré las hojas virtuales; No afectan el resultado.

El subárbol izquierdo de está completo y siempre tiene una altura y, por lo tanto, contiene nodos. El subárbol derecho, por otro lado, está completo y tiene una altura de y, por lo tanto, contiene nodos. Ahora el valor de -balance para la raíz es $T_k$ $k-1$ $2^k - 1$ $2k - 1$ $2^{2k}-1$ $\mu$

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

lo que prueba que no hay según lo solicitado. $\mu > 0$

Rafael
fuente

No. Considere un árbol rojo-negro con la siguiente estructura especial.

El subárbol izquierdo es un árbol binario completo con profundidad , en el que cada nodo es negro. $d$
El subárbol derecho es un árbol binario completo con profundidad , en el que cada nodo en profundidad impar es rojo, y cada nodo en profundidad par es negro. $2d$

Es sencillo verificar que este sea un árbol rojo-negro válido. Pero el número de nodos en el subárbol derecho ( ) es aproximadamente el cuadrado del número de nodos en el subárbol izquierdo ( ). $2^{2d+1}-1$ $2^{d+1}-1$

JeffE
fuente

+1: ¡Gracias! Pero el número de nodos es de . ¿Podemos quizás 'rellenarlos' lo suficiente para obtener un árbol de un tamaño dado ? (Parece que eso debería ser factible).

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

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

n

$n$

Aryabhata

Ya tiene un contraejemplo para infinitamente , entonces, ¿por qué molestarse? Pero supongo que si lo desea, puede agregar más nodos rojos al subárbol izquierdo o quitar algunos nodos rojos del subárbol derecho.

n

$n$

JeffE

@JeffE: Básicamente, la cadena del contraejemplo sería un subconjunto 'denso', en lugar de un subconjunto 'disperso'. Quizás cambie la formulación de la pregunta.

Aryabhata