Arboles B: remove (steps)

Casos para eliminar una clave

Dependiendo de la posición de la clave y las propiedades del nodo, el proceso de eliminación se divide en diferentes casos:

Caso 1: La clave está en un nodo hoja

• Si la clave está en un nodo hoja, simplemente elimínala del nodo.
• Después de eliminar, verifica si el nodo aún cumple con la propiedad mínima del B-Tree:
  • Cada nodo (excepto la raíz) debe tener al menos ⌈m/2⌉ - 1 claves, donde m es el orden del B-Tree.
  • Si el nodo viola esta propiedad, realiza una fusión o redistribución (ver más adelante).

---

Caso 2: La clave está en un nodo interno

• Si la clave está en un nodo interno, reemplázala con una clave adecuada y elimina esa clave reemplazada. Existen dos opciones para el reemplazo:
  1. Predecesor en orden: Busca la clave más grande en el subárbol izquierdo del nodo.
  2. Sucesor en orden: Busca la clave más pequeña en el subárbol derecho del nodo.
• Luego, elimina la clave predecesora o sucesora del nodo hoja correspondiente (lo que puede llevarnos al Caso 1).
• Asegúrate de mantener las propiedades del B-Tree después de este proceso.

---

Caso 3: El nodo donde está la clave tiene menos claves de las necesarias

Si, después de eliminar la clave, un nodo tiene menos claves que el mínimo permitido, aplica uno de estos procedimientos:

1. Redistribución:
   • Si uno de los nodos hermanos inmediatos (adyacentes) tiene más claves que el mínimo, toma una clave prestada del nodo hermano.
   • Mueve una clave del nodo padre al nodo afectado y ajusta las claves y los punteros de los nodos.
2. Fusión:
   • Si los nodos hermanos inmediatos no pueden prestar una clave (porque también tienen el mínimo permitido), fusiona el nodo afectado con uno de sus hermanos.
   • Mueve una clave del nodo padre al nodo resultante de la fusión.
   • Si el nodo padre ahora tiene menos claves de las necesarias, repite el proceso de fusión o redistribución hacia arriba en el árbol.