6 - Eliminación en un árbol B

Eliminar en un B-Tree debe preservar los invariantes: cada nodo (salvo la raíz) mantiene entre t - 1 y 2t - 1 claves y las hojas permanecen en el mismo nivel. La estrategia top-down evita quedarse sin espacio al regresar de la recursión.

6.1 Eliminación de clave en nodo hoja

Si la clave está en una hoja con al menos t claves:

  • Se elimina directamente desplazando las claves mayores para cerrar el hueco.
  • No hay cambios en otros nodos porque la hoja sigue teniendo al menos t - 1 claves.

6.2 Eliminación en nodo interno

Cuando la clave está en un nodo interno:

  • Si el hijo izquierdo tiene ≥ t claves, se toma su predecesora (máxima del subárbol izquierdo) para reemplazar y se borra recursivamente allí.
  • Si el hijo derecho tiene ≥ t claves, se toma la sucesora (mínima del subárbol derecho) y se elimina en ese hijo.
  • Si ambos hijos tienen solo t - 1 claves, se fusionan con la clave actual y se continua en el nodo fusionado.

6.3 Fusión (merge) de nodos

La fusión combina dos hijos hermanos con t - 1 claves cada uno y la clave separadora del padre:

  • Se crean 2t - 1 claves en un solo nodo y se unen sus hijos (si existen).
  • El padre pierde una clave y un puntero; si queda con menos de t - 1 claves se tratará más arriba.
  • Permite seguir la eliminación en un nodo con espacio suficiente.

6.4 Redistribución de claves entre hermanos

Antes de fusionar conviene redistribuir cuando un hermano tiene ≥ t claves:

  • Si el hermano izquierdo está cargado, se mueve su mayor clave al padre y la clave del padre baja al nodo deficitario.
  • Si el hermano derecho está cargado, se sube su menor clave y se baja la clave del padre.
  • Con esto se evita fusionar y se mantiene la ocupación de ambos nodos.

6.5 Actualizar la raíz si queda vacía

Tras eliminar puede ocurrir que la raíz se quede sin claves:

  • Si tiene un solo hijo, este pasa a ser la nueva raíz (reduce la altura en uno).
  • Si no tiene hijos, el árbol queda vacío.
  • Esta actualización mantiene la raíz con al menos una clave salvo en el caso del árbol vacío.
/* Eliminación top-down en B-Tree (bosquejo) */
void btree_eliminar(BTreeNode **raiz, int clave) {
  if (*raiz == NULL) return;
  eliminar_en_nodo(*raiz, clave);
  /* Si la raíz quedó sin claves, ajustarla */
  if ((*raiz)->cuenta == 0) {
    BTreeNode *vieja = *raiz;
    if (vieja->esHoja) {
      *raiz = NULL;
    } else {
      *raiz = vieja->hijos[0];
    }
    free(vieja->claves);
    free(vieja->hijos);
    free(vieja);
  }
}

/* eliminar_en_nodo garantiza que al descender el hijo elegido tenga ≥ t claves:
   - si un hijo tiene solo t-1, intenta redistribuir con un hermano
   - si ambos hermanos tienen t-1, fusiona y luego desciende */
void eliminar_en_nodo(BTreeNode *nodo, int clave) {
  /* Detalles omitidos por brevedad: casos de hoja, sustitución por predecesor/sucesor,
     redistribución y fusión según ocupación de hermanos. */
}

6.6 Código completo para probar en CLion

Ejemplo autocontenido en main.c con inserción y eliminación top-down listo para compilar:

#include <stdio.h>
#include <stdlib.h>

typedef struct BTreeNode {
  int *claves;
  struct BTreeNode **hijos;
  int cuenta;
  int esHoja;
  int orden;
} BTreeNode;

static BTreeNode *btree_crear(int t) {
  BTreeNode *n = malloc(sizeof(BTreeNode));
  n->orden = t;
  n->esHoja = 1;
  n->cuenta = 0;
  n->claves = malloc(sizeof(int) * (2 * t - 1));
  n->hijos = malloc(sizeof(BTreeNode *) * (2 * t));
  return n;
}

static void dividir_hijo(BTreeNode *padre, int idx, BTreeNode *hijo) {
  int t = hijo->orden;
  BTreeNode *nuevo = btree_crear(t);
  nuevo->esHoja = hijo->esHoja;
  nuevo->cuenta = t - 1;
  for (int j = 0; j < t - 1; j++) nuevo->claves[j] = hijo->claves[j + t];
  if (!hijo->esHoja) for (int j = 0; j < t; j++) nuevo->hijos[j] = hijo->hijos[j + t];
  hijo->cuenta = t - 1;
  for (int j = padre->cuenta; j >= idx + 1; j--) padre->hijos[j + 1] = padre->hijos[j];
  padre->hijos[idx + 1] = nuevo;
  for (int j = padre->cuenta - 1; j >= idx; j--) padre->claves[j + 1] = padre->claves[j];
  padre->claves[idx] = hijo->claves[t - 1];
  padre->cuenta++;
}

static void insertar_no_lleno(BTreeNode *nodo, int clave) {
  int i = nodo->cuenta - 1;
  if (nodo->esHoja) {
    while (i >= 0 && clave < nodo->claves[i]) { nodo->claves[i + 1] = nodo->claves[i]; i--; }
    nodo->claves[i + 1] = clave; nodo->cuenta++;
  } else {
    while (i >= 0 && clave < nodo->claves[i]) i--;
    i++;
    if (nodo->hijos[i]->cuenta == 2 * nodo->orden - 1) {
      dividir_hijo(nodo, i, nodo->hijos[i]);
      if (clave > nodo->claves[i]) i++;
    }
    insertar_no_lleno(nodo->hijos[i], clave);
  }
}

void btree_insertar(BTreeNode **raiz, int clave) {
  if (*raiz == NULL) return;
  if ((*raiz)->cuenta == 2 * (*raiz)->orden - 1) {
    BTreeNode *nueva = btree_crear((*raiz)->orden);
    nueva->esHoja = 0;
    nueva->hijos[0] = *raiz;
    dividir_hijo(nueva, 0, *raiz);
    *raiz = nueva;
  }
  insertar_no_lleno(*raiz, clave);
}

/* ---------- Eliminación ---------- */
static int maximo(BTreeNode *nodo) {
  while (!nodo->esHoja) nodo = nodo->hijos[nodo->cuenta];
  return nodo->claves[nodo->cuenta - 1];
}
static int minimo(BTreeNode *nodo) {
  while (!nodo->esHoja) nodo = nodo->hijos[0];
  return nodo->claves[0];
}

static void fusionar(BTreeNode *padre, int idx) {
  int t = padre->orden;
  BTreeNode *izq = padre->hijos[idx];
  BTreeNode *der = padre->hijos[idx + 1];
  izq->claves[t - 1] = padre->claves[idx];
  for (int j = 0; j < der->cuenta; j++) izq->claves[j + t] = der->claves[j];
  if (!izq->esHoja) for (int j = 0; j <= der->cuenta; j++) izq->hijos[j + t] = der->hijos[j];
  izq->cuenta += der->cuenta + 1;
  for (int j = idx; j < padre->cuenta - 1; j++) padre->claves[j] = padre->claves[j + 1];
  for (int j = idx + 1; j < padre->cuenta; j++) padre->hijos[j] = padre->hijos[j + 1];
  padre->cuenta--;
  free(der->claves); free(der->hijos); free(der);
}

static void redistribuir_izq(BTreeNode *padre, int idx) {
  BTreeNode *hijo = padre->hijos[idx];
  BTreeNode *hermano = padre->hijos[idx - 1];
  for (int j = hijo->cuenta; j > 0; j--) hijo->claves[j] = hijo->claves[j - 1];
  if (!hijo->esHoja) for (int j = hijo->cuenta + 1; j > 0; j--) hijo->hijos[j] = hijo->hijos[j - 1];
  hijo->claves[0] = padre->claves[idx - 1];
  if (!hijo->esHoja) hijo->hijos[0] = hermano->hijos[hermano->cuenta];
  padre->claves[idx - 1] = hermano->claves[hermano->cuenta - 1];
  hermano->cuenta--; hijo->cuenta++;
}

static void redistribuir_der(BTreeNode *padre, int idx) {
  BTreeNode *hijo = padre->hijos[idx];
  BTreeNode *hermano = padre->hijos[idx + 1];
  hijo->claves[hijo->cuenta] = padre->claves[idx];
  if (!hijo->esHoja) hijo->hijos[hijo->cuenta + 1] = hermano->hijos[0];
  padre->claves[idx] = hermano->claves[0];
  for (int j = 0; j < hermano->cuenta - 1; j++) hermano->claves[j] = hermano->claves[j + 1];
  if (!hermano->esHoja) for (int j = 0; j < hermano->cuenta; j++) hermano->hijos[j] = hermano->hijos[j + 1];
  hermano->cuenta--; hijo->cuenta++;
}

static void asegurar_claves(BTreeNode *padre, int idx) {
  int t = padre->orden;
  BTreeNode *hijo = padre->hijos[idx];
  if (hijo->cuenta >= t) return;
  if (idx > 0 && padre->hijos[idx - 1]->cuenta >= t) redistribuir_izq(padre, idx);
  else if (idx < padre->cuenta && padre->hijos[idx + 1]->cuenta >= t) redistribuir_der(padre, idx);
  else {
    if (idx < padre->cuenta) fusionar(padre, idx);
    else fusionar(padre, idx - 1);
  }
}

static void eliminar_en_nodo(BTreeNode *nodo, int clave) {
  int idx = 0;
  while (idx < nodo->cuenta && clave > nodo->claves[idx]) idx++;
  if (idx < nodo->cuenta && nodo->claves[idx] == clave) {
    if (nodo->esHoja) {
      for (int j = idx; j < nodo->cuenta - 1; j++) nodo->claves[j] = nodo->claves[j + 1];
      nodo->cuenta--;
    } else {
      if (nodo->hijos[idx]->cuenta >= nodo->orden) {
        int pred = maximo(nodo->hijos[idx]);
        nodo->claves[idx] = pred;
        eliminar_en_nodo(nodo->hijos[idx], pred);
      } else if (nodo->hijos[idx + 1]->cuenta >= nodo->orden) {
        int succ = minimo(nodo->hijos[idx + 1]);
        nodo->claves[idx] = succ;
        eliminar_en_nodo(nodo->hijos[idx + 1], succ);
      } else {
        fusionar(nodo, idx);
        eliminar_en_nodo(nodo->hijos[idx], clave);
      }
    }
  } else {
    if (nodo->esHoja) return;
    asegurar_claves(nodo, idx);
    if (idx > nodo->cuenta) idx--;
    eliminar_en_nodo(nodo->hijos[idx], clave);
  }
}

void btree_eliminar(BTreeNode **raiz, int clave) {
  if (*raiz == NULL) return;
  eliminar_en_nodo(*raiz, clave);
  if ((*raiz)->cuenta == 0) {
    BTreeNode *vieja = *raiz;
    *raiz = vieja->esHoja ? NULL : vieja->hijos[0];
    free(vieja->claves); free(vieja->hijos); free(vieja);
  }
}

static void imprimir_btree(BTreeNode *nodo, int nivel) {
  if (!nodo) return;
  for (int i = 0; i < nodo->cuenta; i++) {
    if (!nodo->esHoja) imprimir_btree(nodo->hijos[i], nivel + 1);
    for (int j = 0; j < nivel; j++) printf("  ");
    printf("%d\n", nodo->claves[i]);
  }
  if (!nodo->esHoja) imprimir_btree(nodo->hijos[nodo->cuenta], nivel + 1);
}

int main(void) {
  int t = 3;
  BTreeNode *raiz = btree_crear(t);
  int datos[] = {10, 20, 5, 6, 12, 30, 7, 17, 3, 4, 15};
  int cantidad = (int)(sizeof(datos) / sizeof(datos[0]));
  for (int i = 0; i < cantidad; i++) btree_insertar(&raiz, datos[i]);
  printf("Árbol luego de inserciones:\n"); imprimir_btree(raiz, 0);

  int borrar[] = {6, 7, 4, 3, 30};
  int nb = (int)(sizeof(borrar) / sizeof(borrar[0]));
  for (int i = 0; i < nb; i++) {
    btree_eliminar(&raiz, borrar[i]);
    printf("\nTras eliminar %d:\n", borrar[i]);
    imprimir_btree(raiz, 0);
  }
  return 0;
}
Ejemplo visual de eliminación en árbol B
Retornar