Tarea 1 de Almacenamiento y Recuperación de la
Información
Trimestre 2010 Primavera
Entrega: 14 de mayo a las 22:00.
El propósito de esta tarea es el de practicar los conceptos de
árboles rojinegros vistos en clase.
Sea T = (V, E) un árbol binario con nodos rojos y negros.
Recuerde que T es un
árbol rojinegro si (1) la raíz es negra, (2)
ningún nodo rojo es hijo de otro nodo rojo y (3) todos los
caminos de la raíz a las hojas tienen el mismo número de
nodos negros.
Escribe un programa rojinegroNN
que decida si un árbol binario es rojinegro o no, donde NN son los dos
dígitos de la
clave que le fue proporcionada por el profesor.
La entrada al programa estará en el archivo rojinegro.ent y consiste de un
renglón con un entero N (la cantidad de nodos de T) seguido de
N renglones con tres enteros
Cj, Xj y Yj, donde Cj es el
color del nodo j (0 es negro y 1 es rojo), Xj y Yj
son
los hijos izquierdo y derecho del nodo j (si alguno de Xj o Yj
vale 0 eso significa que el hijo correspondiente no existe). Observa
que la clave almacenada en el nodo j es desconocida. Puedes
suponer que T es un árbol binario, que los nodos de T
están numerados del 1 al N y que 1 <= N <= 100.
La salida del programa deberá estar en el archivo rojinegro.sal y consiste de un
renglón con un entero R (1 si T es rojinegro y 0 si no lo es).
En el caso de que R sea rojinegro
el segundo renglón deberá contener la cantidad H de hojas
de T y el tercer renglón deberá contener
una lista con las H hojas de T (ordenadas de menor a mayor).
En el caso de que R no sea rojinegro
el segundo renglón deberá contener la cantidad V de nodos
de T que violan la condición (2) y el tercer renglón
deberá contener
una lista con esos V nodos (ordenados de menor a mayor).