Colorea un árbol binario para que sea un árbol rojo-negro

Una pregunta común de la entrevista es dar un algoritmo para determinar si un árbol binario dado está equilibrado en altura (definición de árbol AVL).

Me preguntaba si podemos hacer algo similar con los árboles rojo-negros.

Dado un árbol binario arbitrario sin color (con nodos NULL), ¿existe un algoritmo "rápido" que pueda determinar si podemos colorear (y encontrar un color) los nodos Rojo / Negro para que satisfagan todas las propiedades de un árbol Rojo-Negro (definición como en esta pregunta )?

Un pensamiento inicial fue que simplemente podemos eliminar los nodos NULL e intentar verificar recursivamente si el árbol resultante puede ser un árbol rojo-negro, pero eso no parece ir a ninguna parte.

Hice (una breve) búsqueda en la web de documentos, pero no pude encontrar ninguno que pareciera tratar este problema.

Es posible que me falte algo simple.

algorithms data-structures binary-trees search-trees Aryabhata
fuente

Estoy bastante seguro de que un árbol puede ser de color rojo-negro si para cada nodo, la ruta más larga desde él a un nodo NULL no es más de dos veces más larga que la más corta. ¿Es eso lo suficientemente rápido?

Karolis Juodelė

Respuestas:

Si para cada nodo de un árbol, el camino más largo desde él hasta un nodo de hoja no es más de dos veces más largo que el más corto, el árbol tiene una coloración rojo-negra.

Aquí hay un algoritmo para descubrir el color de cualquier nodo n

if n is root,
    n.color = black
    n.black-quota = height n / 2, rounded up.

else if n.parent is red,
    n.color = black
    n.black-quota = n.parent.black-quota.

else (n.parent is black)
    if n.min-height < n.parent.black-quota, then
        error "shortest path was too short"
    else if n.min-height = n.parent.black-quota then
        n.color = black
    else (n.min-height > n.parent.black-quota)
        n.color = red
    either way,
        n.black-quota = n.parent.black-quota - 1

Aquí n.black-quotaestá el número de nodos negros que espera ver yendo a una hoja, desde el nodo ny n.min-heightes la distancia a la hoja más cercana.

Por razones de brevedad de la notación, dejar que , y . $b(n) =$ n.black-quota $h(n) =$ n.height $m(n) =$ n.min-height

Teorema: Fijar un árbol binario . Si para cada nodo , y para el nodo , $T$ $n \in T$ $h(n) \leq 2m(n)$ $r = \text{root}(T)$ entoncestiene una coloración rojo-negra con exactamentenodos negros en cada camino desde la raíz hasta la hoja. $b(r) \in [\frac{1}{2}h(r), m(r)]$ $T$ $b(r)$

Prueba: Inducción sobre . $b(n)$

Verifique que los cuatro árboles de altura uno o dos satisfagan el teorema con . $b(n) = 1$

Por definición de árbol rojo-negro, la raíz es negra. Sea un nodo con un padre negro tal que $n$ $p$ . Entonces,y. $b(p) \in [\frac{1}{2}h(p), m(p)]$ $b(n) = b(p) -1$ $h(n) = h(p)-1$ $h(n) \geq m(n) \geq m(p)-1$

Suponga que el teorema se cumple para todos los árboles con raíz , . $r$ $b(r) < b(q)$

Si , entonces puede ser de color rojo-negro por el supuesto inductivo. $b(n) = m(n)$ $n$

Si luego $b(p) = \frac{1}{2}h(p)$ . no satisface el supuesto inductivo y, por lo tanto, debe ser rojo. Seahijo de. y $b(n) = \lceil \frac{1}{2}h(n) \rceil - 1$ $n$ $c$ $n$ $h(c) = h(p)-2$ . Entoncespuede ser de color rojo-negro por el supuesto inductivo. $b(c) = b(p)-1 = \frac{1}{2}h(p)-1 = \frac{1}{2}h(c)$ $c$

Tenga en cuenta que, por el mismo razonamiento, si , entonces tantocomo un hijo desatisfacen el supuesto inductivo. Por lo tanto,podría tener cualquier color. $b(n) \in (\frac{1}{2}h(r), m(r))$ $n$ $n$ $n$

Karolis Juodelė
fuente

@Aryabhata, cualquier recorrido está bien, siempre que el padre se vea antes que sus hijos. No tengo una prueba formal escrita, pero tengo una idea de cómo se vería. Intentaré escribir algo cuando pueda.

Karolis Juodelė

@Aryabhata, agregué una prueba. Perdona que haya tardado tanto.

Karolis Juodelė

@Aryabhata, la idea es que si

de algún nodo

está dentro de ciertos límites, un hijo o nieto

puede tener

dentro de esos mismos límites. Tener

en esos límites puede corresponder a que

sea negro. La mayor parte de la prueba se trata de limitar

de un hijo o nieto, dado

de los padres o abuelos. Tu árbol es ciertamente colorable.

b (p)

$b(p)$

p

$p$

c

$c$

p

$p$

b (c)

$b(c)$

b (n)

$b(n)$

n

$n$

h

$h$

m

$m$

h

$h$

m

$m$

, el hijo izquierdo es negro y el hijo derecho es rojo, la ruta de longitud 16 es

, la ruta de longitud 8 es

, las rutas de 9 y 12 pueden tener Múltiples colorantes válidos.

b (r o o t) = 8

$b(root) = 8$

b r b r b r \dots

$brbrbr\dots$

b b b b b b b b

$bbbbbbbb$

Karolis Juodelė

Hay una pregunta sobre esta respuesta .

David Richerby, el

Creo que la respuesta de Karolis es correcta (y una caracterización bastante agradable de los árboles rojo-negros, dando un algoritmo de tiempo ), solo quería agregar otra posible respuesta. $O(n)$

Un enfoque es usar programación dinámica.

Dado un árbol, para cada nodo , construye dos conjuntos: y que contiene las posibles alturas negras para el subárbol enraizado en . contiene las alturas negras suponiendo que es de color rojo, y suponiendo que es de color negro. $n$ $S_R(n)$ $S_B(n)$ $n$ $S_R(n)$ $n$ $S_B(n)$ $n$

Ahora dados los conjuntos para y (es decir, hijos directos de ), podemos calcular los conjuntos correspondientes para , tomando intersecciones y uniones apropiadas (e incrementándolas según sea necesario). $n.Left$ $n.Right$ $n$ $n$

Creo que esto resulta ser un algoritmo de tiempo . $O(n \log n)$

Aryabhata
fuente