Tarea 5 de Almacenamiento y Recuperación de la
Información
Trimestre 2008 Invierno
Entrega: 6 de junio de 2008 a
las 10:00.
El propósito de esta tarea es el de simular lo que pasa en la
raíz de un árbol B. Suponga que se tiene un árbol
B de orden N que consta sólamente de un nodo raíz. Este
nodo raíz comienza vacío y se le harán algunas
operaciones de inserción y de borrado. Puedes suponer que nunca
habrá más claves que el orden del árbol.
Escribe un programa raizbNN
que lleve a cabo la simulación de este proceso,
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 opera.txt que contiene en su
primer renglón dos enteros N y M (el orden del árbol y el
número de operaciones que se le harán). Cada uno de los
siguientes M renglones contiene una letra (I o B) separada con un
espacio de una clave numérica C. La letra I significa que se
debe insertar la clave C en la raíz (excepto cuando C ya
esté en la raíz). La letra B significa que se debe borrar
la clave C de la raíz (excepto cuando C no esté en la
raíz). Puedes suponer que 1 <= N <= 1000, que 1 <= M
<= 1000 y que 1 <= C <= 1,000,000.
La salida del programa deberá estar en el archivo resul.txt que contendrá
en su primer renglón el entero R (la cantidad de claves en la
raíz). En su segundo renglón contendrá las R
claves en la raíz, ordenadas de menor a mayor y separadas por un
espacio.
Ejemplo de entrada
|
Ejemplo de salida
|
4 5
I 3
I 1
B 4
B 1
I 5
|
2
3 5
|