La función divide

Es la rutina principal en la construcción de la forma balanceada del B+. Esta rutina regresa el apuntador al nodo donde debe insertarse el nuevo elemento. Tiene 5 parámetros de entrada: el nodo a dividir n, la llave k que se desea insertar, la posición i de la llave en n, un apuntador a una bandera auxiliar fl, y la llave que se colocará en el nodo padre. La primera parte de esta rutina se encarga de dividir el nodo y decidir en cual de los dos nuevos nodos quedará k. La segunda parte se encarga de insertar la llave media en el nodo padre, considerando si existe nodo padre, si está lleno este nodo , o si quedan lugares en dicho nodo.

 
/* Genera el arbol dividiendo un nodo en 2 partes   */
/* [ABRIL-97]                                       */
/* AMILCAR MENESES VIVEROS                          */
node *divide(node *n, Bkey k, int i, int *fl, Bkey *mk)
{
    int aux, j; 
    node *mid, *nr, *father, *mid2; 
    Bkey midkey; 

    /* Divide el nodo en "mitades" y decide  */
    /* que mitad debe contener  la llave 'k' */
    mid = makenode(); 
    if (i< (mdOr-1)) {
       copy(n, mdOr, ORDER, mid); 
       nr = n;  *fl = 1; midkey = n->ak[mdOr-1]; 
    }
    else if ( i == (mdOr-1)) {
       copy(n, mdOr-1, ORDER, mid); 
       nr = n; *fl = 1; midkey = k; 
    }
    else {
       copy(n, mdOr, ORDER, mid);
       nr = mid; *fl = -1; midkey = n->ak[mdOr-1];
    }

    /* Revisa la insercion de los nuevos nodos hijos en el nodo padre */ 
    /* con su llave correspondiente                                   */ 
    father = n->up; 
    if (father == NULL) { 
        father = maketree(midkey); 
        addnode(father, n, 0); 
        addnode(father, mid, 1); 
    } 
    else if ( (father->nKeys) < (ORDER-1) ) { 
         j = nodesearch(father, midkey); 
         ins_key(father, midkey, j); 
         addnode(father, mid, j+1); 
    }
    else {
         j = nodesearch(father, midkey); 
         mid2 = divide(father, midkey, j, &aux, mk); 
         j = nodesearch(mid2, midkey); 
         ins_key(father, midkey, j); 
         addnode(mid2, mid, j+1); 
    }
    *mk = midkey; 
    return nr; 
}