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

16

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.

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:

12

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 , h ( n ) = y m ( n ) = .b(n)= n.black-quotah(n)= n.heightm(n)= n.min-height

Teorema: Fijar un árbol binario . Si para cada nodo n T , h ( n ) 2 m ( n ) y para el nodo r = raíz ( T ) , b ( r ) [ 1TnTh(n)2m(n)r=root(T)entoncesTtiene una coloración rojo-negra con exactamenteb(r)nodos negros en cada camino desde la raíz hasta la hoja.b(r)[12h(r),m(r)]Tb(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 p tal que b ( p ) [ 1np. Entoncesb(n)=b(p)-1,h(n)=h(p)-1yh(n)m(n)m(p)-1.b(p)[12h(p),m(p)]b(n)=b(p)1h(n)=h(p)1h(n)m(n)m(p)1

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

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

Si luegob(n)=1b(p)=12h(p). nno satisface el supuesto inductivo y, por lo tanto, debe ser rojo. Seachijo den. h(c)=h(p)-2y b(c)=b(p)-1=1b(n)=12h(n)1ncnh(c)=h(p)2. Entoncescpuede ser de color rojo-negro por el supuesto inductivo.b(c)=b(p)1=12h(p)1=12h(c)c

Tenga en cuenta que, por el mismo razonamiento, si , entonces tantoncomo un hijo densatisfacen el supuesto inductivo. Por lo tanto,npodría tener cualquier color.b(n)(12h(r),m(r))nnn

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 p está dentro de ciertos límites, un hijo o nieto c de p puede tener b ( c ) dentro de esos mismos límites. Tener b ( n ) en esos límites puede corresponder a que n sea ​​negro. La mayor parte de la prueba se trata de limitar h y m de un hijo o nieto, dado h y m de los padres o abuelos. Tu árbol es ciertamente colorable. b ( r o o tb(p)pcpb(c)b(n)nhmhm , el hijo izquierdo es negro y el hijo derecho es rojo, la ruta de longitud 16 es b r b r b r ... , la ruta de longitud 8 es b b b b b b b b , las rutas de 9 y 12 pueden tener Múltiples colorantes válidos. b(root)=8brbrbrbbbbbbbb
Karolis Juodelė
Hay una pregunta sobre esta respuesta .
David Richerby, el
2

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: S R ( n ) y S B ( n ) que contiene las posibles alturas negras para el subárbol enraizado en n . S R ( n ) contiene las alturas negras suponiendo que n es de color rojo, y S B ( n ) suponiendo que n es de color negro.nSR(n)SB(n)nSR(n)nSB(n)n

Ahora dados los conjuntos para y n . R i g h t (es decir, hijos directos de n ), podemos calcular los conjuntos correspondientes para n , tomando intersecciones y uniones apropiadas (e incrementándolas según sea necesario).n.Leftn.Rightnn

Creo que esto resulta ser un algoritmo de tiempo .O(nlogn)

Aryabhata
fuente