¿En qué orden debe insertar un conjunto de claves conocidas en un árbol B para obtener una altura mínima?

Question

Apr 14, 2013, 07:01 PM

¿En qué orden debe insertar un conjunto de claves conocidas en un árbol B para obtener una altura mínima?

Dado un número fijo de claves o valores (almacenados en una matriz o en alguna estructura de datos) y el orden de b-tree, podemos determinar la secuencia de inserción de claves que generaría un b-tree eficiente en el espacio.

Para ilustrar, considere el árbol-b de orden 3. Deje que las claves sean {1,2,3,4,5,6,7}. Insertando elementos en el árbol en el siguiente orden

for(int i=1 ;i<8; ++i)
{
 tree.push(i);  
}

crearía un árbol como este

        4
     2      6
   1  3   5   7

verhttp://en.wikipedia.org/wiki/B-tree

Pero insertando elementos de esta manera.

flag = true;
for(int i=1,j=7; i<8; ++i,--j)
{
    if(flag)
    {
        tree.push(i);
        flag = false;
    }
    else
    {
        tree.push(j);
        flag = true;
    }   
}

crea un arbol como este