Tarea 6 de Almacenamiento y Recuperación de la
Información
Trimestre 2009 Primavera
Entrega: 31 de julio de
2009 a las 22:00.
El propósito de esta tarea es el de practicar los conceptos de
árboles B vistos en clase.
Considera dos nodos hermanos de un árbol B de orden M. En
principio cada uno de estos nodos debe tener al menos M/2 claves. Sin
embargo, puede ser que uno de los dos nodos tenga muchas más
claves que el otro. En este caso, se puede usar el concepto de
redistribución de modo que después de hacerla ambos nodos
tengan aproximadamente el mismo número de claves.
Supongamos que el hermano izquierdo tiene P claves y el hermano derecho
tiene Q claves:
Si P+Q es par entonces al final de la redistribución tanto
el hermano izquierdo como el hermano derecho deben tener el mismo
número de claves.
Si P+Q es impar entonces al final de la redistribución el
hermano izquierdo debe tener exactamente una clave más que el
hermano
derecho.
Abajo muestro un ejemplo con P = 5 y Q = 8, de modo que P+Q = 13 es
impar, así que el hermano izquierdo debe terminar con 7 claves y
el hermano derecho debe terminar con 6 claves.
Escribe un programa redisNN
que lleve a cabo esta labor.
El archivo de entrada antes.txt
contiene un entero M en su primer renglón, seguido de un vector
A con M enteros en el segundo renglón, seguido de un vector B
con M enteros en el tercer renglón. Las claves del vector A
(hermano izquierdo) serán enteros positivos, mientras que la
parte no usada del vector A está indicada con -1. De la misma
manera, las claves del vector B (hermano derecho) serán enteros
positivos, mientras que la parte no usada del vector B está
indicada con -1. Puedes suponer que 1 <= M <= 1000, que las
claves de A aparecen en orden creciente, que las claves de B aparecen
en orden creciente, que las claves de A son menores que las de B y que
todas las claves están en el rango de 1 a 1,000,000.
El archivo de salida
despues.txt debe contener el entero M en su primer renglón,
seguido de un vector A con M enteros en el
segundo renglón, seguido de un vector B con M enteros en el
tercer
renglón. Los contenidos de A y B deberán reflejar el
efecto de la redistribución.