From 4966fd10d0744e37a60255a9e53da3ddb7399e75 Mon Sep 17 00:00:00 2001 From: Alan Kennedy Date: Sat, 29 May 2004 17:58:36 +0000 Subject: [PATCH] Caso 3a terminado, rotacion a izquierda, falta 3a rotacion derecha, 3b y listo Arbol B+ al menos en su funcionalidad basica Crear,Insertar, Buscar, Obtener Bloque dondre Grabar, Eliminar --- emufs/b_plus_test.c | 8 ++++++- emufs/indice_bplus.c | 54 +++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 60 insertions(+), 2 deletions(-) diff --git a/emufs/b_plus_test.c b/emufs/b_plus_test.c index 5742a77..c9ccc83 100644 --- a/emufs/b_plus_test.c +++ b/emufs/b_plus_test.c @@ -67,7 +67,13 @@ printf("Exit Code del Borrar Clave: %i\n",exitcode); querydata.clave.i_clave = 16; exitcode = emufs_b_plus_eliminar(emu->indices,querydata.clave,2); printf("Exit Code del Borrar Clave: %i\n",exitcode);*/ -querydata.clave.i_clave = 4; +/*querydata.clave.i_clave = 16; +exitcode = emufs_b_plus_eliminar(emu->indices,querydata.clave,0); +printf("Exit Code del Borrar Clave: %i\n",exitcode); +querydata.clave.i_clave = 32; +exitcode = emufs_b_plus_eliminar(emu->indices,querydata.clave,0); +printf("Exit Code del Borrar Clave: %i\n",exitcode);*/ +querydata.clave.i_clave = 2; exitcode = emufs_b_plus_eliminar(emu->indices,querydata.clave,0); printf("Exit Code del Borrar Clave: %i\n",exitcode); diff --git a/emufs/indice_bplus.c b/emufs/indice_bplus.c index c192e5d..036d4cc 100644 --- a/emufs/indice_bplus.c +++ b/emufs/indice_bplus.c @@ -439,6 +439,7 @@ int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node) { INDEX_DAT prepostkey; int i = 0,j = 0,minclaves = 0, nivel_mayor1 = 0,cant_claves_child = 0; + int cant_claves_rsibling = 0, cant_claves_lsibling = 0, es_hoja = 0; NODO_B_PLUS *nodo = b_plus_leer_nodo(idx,num_node); NODO_B_PLUS *node_y,*node_z; if (nodo == NULL) { PERR("No leyo nodo bien"); return -1; } @@ -466,7 +467,58 @@ int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node) /* Me debo fijar si esta la clave en este nodo interno, sino busco */ while ( i >= 0 && key.i_clave != nodo->claves[i].i_clave ) --i; if (i < 0) { - /* No esta en este nodo interno, caso 3 */ + PERR("Entre caso 3 del eliminar"); + /* No esta en este nodo interno, caso 3. Determino en que rama debe estar */ + i = nodo->cant_claves - 1; + while ( i >= 0 && key.i_clave < nodo->claves[i].i_clave ) --i; + i++; + cant_claves_child = b_plus_cant_claves_nodo(idx,nodo->hijos[i]); + if (cant_claves_child > minclaves) emufs_b_plus_eliminar(idx,key,nodo->hijos[i]); + else { + /* Vemos si estamos en caso 3a o 3b, mirando cant_claves de sus siblings */ + if (i < nodo->cant_claves) cant_claves_rsibling = b_plus_cant_claves_nodo(idx,nodo->hijos[i+1]); + if (i > 0) cant_claves_lsibling = b_plus_cant_claves_nodo(idx,nodo->hijos[i-1]); + printf ("El sibling derecho si existe tiene %i claves\n", cant_claves_rsibling); + printf ("El sibling izquierdo si existe tiene %i claves\n", cant_claves_lsibling); + if (cant_claves_rsibling > minclaves) { + /* El sibling derecho me dara una key mediante rotacion. Caso 3a */ + PERR("Entre caso 3a right sibling del eliminar"); + node_y = b_plus_leer_nodo(idx,nodo->hijos[i]); + node_z = b_plus_leer_nodo(idx,nodo->hijos[i+1]); + if (node_z->nivel == 0) es_hoja = 1; + /* Le bajo la del padre a NodeY y muevo el apropiado child de NodoZ a NodoY */ + node_y->claves[cant_claves_child] = nodo->claves[i]; + node_y->hijos[cant_claves_child+1] = node_y->hijos[cant_claves_child]; + node_y->hijos[cant_claves_child+1-es_hoja] = node_z->hijos[0]; + node_y->cant_claves++; + /* Le subo al padre desde el NodoZ, teniendo en cuenta si es hoja o no */ + nodo->claves[i] = node_z->claves[es_hoja]; + /* Hago shifting en el sibling para quitar la que subio */ + for (j = 0; j < node_z->cant_claves-1; ++j) { + node_z->claves[j] = node_z->claves[j+1]; + node_z->hijos[j] = node_z->hijos[j+1]; + } + node_z->hijos[j] = node_z->hijos[j+1]; + node_z->cant_claves--; + /* Grabo los cambios y listo */ + b_plus_grabar_nodo(idx,node_z,nodo->hijos[i+1]); + b_plus_grabar_nodo(idx,node_y,nodo->hijos[i]); + b_plus_grabar_nodo(idx,nodo,num_node); + b_plus_destruir_nodo(node_y); + b_plus_destruir_nodo(node_z); + /* Borro recursivamente KEY entrando por Child que ahora tiene minclaves+1 */ + emufs_b_plus_eliminar(idx,key,nodo->hijos[i]); + } + else if (cant_claves_lsibling > minclaves) { + /* el sibling izquierdo me dara una key mediante rotacion Caso 3a */ + PERR("Entre caso 3a left sibling del eliminar"); + node_z = b_plus_leer_nodo(idx,nodo->hijos[i]); + node_y = b_plus_leer_nodo(idx,nodo->hijos[i-1]); + } else { + /* Caso 3b, debo bajar una clave y unificar con sibling disponible */ + PERR("Entre caso 3b del eliminar"); + } + } } else { /* Esta en el nodo interno, caso 2 */ cant_claves_child = b_plus_cant_claves_nodo(idx,nodo->hijos[i]); -- 2.43.0