Árboles B: remove

Borrar un elemento de un árbol B consta de tres pasos principales: buscar el nodo en el que se encuentra la clave que se desea borrar, borrar la clave y equilibrar el árbol si es necesario. Al borrar un árbol, puede producirse una situación denominada underflowing.

El underflowing se produce cuando un nodo contiene menos del número mínimo de claves que debería contener.

Los términos que hay que entender antes de aprender la operación de borrado son:

• Inorder Predecessor

  La mayor clave del hijo izquierdo de un nodo se denomina su Inorder predecessor

• Inorder Successor

  La clave más pequeña del hijo derecho de un nodo se denomina Inorder Successor

Deletion Operation

Existen dos casos a la hora de borrar una key que se encuentra en un nodo hoja.

La eliminación de la key no provoca underflowing

Sencillamente se elimina la key de ese nodo hoja

La eliminación de la key provoca underflowing

Si la eliminación de la key provoca que hayan menos keys del mínimo permitido hay que rebalancear el árbol

En este caso particular podemos llegar a 3 casos diferentes:

• Tomamos prestada una clave de su nodo hermano inmediato en el orden de izquierda a derecha. Primero, visitamos el nodo hermano inmediato izquierdo. Si el nodo hermano izquierdo tiene más de el número mínimo de claves, se toma prestada la clave de mayor valor de este nodo. Esta clave será elevada hacia el padre, y por otro lado, la clave que tiene como hijo este nodo izquierdo, será bajada al nodo hoja.

  Vamos a ver un ejemplo de esto, en este arbol de grado 5, refiriéndonos con grado al número máximo de hijos que puede tener un nodo. Por tanto

  minKeys = grado / 2 - 1 =  2;      maxKeys = grado - 1 = 4

Si en este nodo quisiéramos borrar el número 14, el nodo se quedaría con menos de las claves permitidas. Por tanto lo que hacemos es elevar el número de mayor valor del hermano izquierdo(11) del nodo con las keys 6, 10, 11

Elevamos el 11 al nodo padre, mientras que la key que era padre de este hijo(12), va a pasar al nodo hoja donde se borró la key.

Quedando el árbol de la siguiente forma:

• Si el nodo izquierdo también tiene el mínimo de claves, se intenta tomar prestada una clave del nodo hermano inmediato derecho. En este caso se toma la clave de menor valor y hacemos lo mismo que hicimos en el ejemplo anterior

Veamos el ejemplo, si de este nodo intentamos borrar el 14, el nodo se queda con menos de las claves permitidas, por lo que se busca en el hermano izquierdo, pero como ya tiene el mínimo de keys, no podemos tomar prestada ninguna key. Por lo tanto, miramos en el hermano derecho del nodo donde queremos borrar la key, en este caso si tiene más keys del mínimo, por lo que podemos tomar prestada la clave de menor valor de este (22).

Al igual que antes, esta clave subirá hacia el padre, mientras que la clave que era el padre de este nodo, bajará hacia el nodo donde se ha borrado la key.

El 22 sube hacia el padre y el 21 baja del padre al nodo donde se elimino la key (14), hay que tener en cuenta que el valor que baja del padre tiene que situarse en la posición correcta respecto a su valor y al valor de las demás keys

Quedando el árbol de esta manera

• Hay un último caso que se produce cuando queremos borrar una key pero tanto el nodo izquierdo como el derecho tienen el mínimo número de claves. En el árbol que nos quedo como resultado en el ejemplo anterior, si quisiéramos borrar la key 15, no podemos aplicar ninguna de las opciones vistas anteriormente.

  Podemos realizar una última operación para poder borrar la key y rebalancear el árbol, para ello hay que mergear el nodo donde la key es borrada con su hermano izquierdo o con su hermano derecho. En este merge la key padre de estos nodos se incluye dentro del merge.

  Si en el ejemplo anterior, borramos el 15, primero borramos esta key, despues realizamos un merge entre los hermanos

  

Quedando este resultado.

Como podemos ver, el nodo padre solo se ha quedado con una clave, si este nodo fuera root estaría bien dado que el nodo root puede tener menos keys del mínimo. En caso de ser un nodo interno, habría que realizar alguna de las operaciones vistas hasta ahora.

Vamos a ver un ejemplo donde es un nodo interno para terminar de asimilar el concepto

En este ejemplo donde el nodo interno (22) se queda con menos de las claves permitidas, no podemos aplicar la primera estrategia dado que no tiene hermano izquierdo, tampoco podemos aplicar la segunda estrategia dado que el hermano derecho (45, 56) tiene las minimas claves permitidas, por lo que habra que volver a mergear este nodo target (22) con su hermano derecho (45, 56)

Quedando el resultado de la siguiente manera

root se puede quedar con menos keys del mínimo.

Key en un nodo interno

A la hora de eliminar una key que esta en un nodo interno, tenemos varías opciones también,

Si del nodo interno quisiéramos borrar el número 56 podemos hacerlo de la siguiente manera:

LST = left subtree

RST = right subtree

• Sustituir la key con el inorder predecesor(Max element in lst) si este tiene más del número mínimo de keys. Es decir en el subárbol izquierdo de esa key, elegir la key de mayor valor. El lst (left subtree) de 56 sería el nodo compuesto por 51,54
• Sustituir la key con el inorder sucessor (Min element in rst), si este tiene más del número mínimo de keys. Es decir en el subárbol derecho de la key, elegir la key de menor valor. El rst(right subtree) es el subárbol compuesto por 65,66.
• Cuando no es posible elevar una key del subárbol izquierdo y tampoco del derecho, por que ambos tienen el mínimo numero de keys, entonces realizamos la operación que vimos antes de mergear ambos hermanos incluyendo la key del padre, pero una vez incluida esta key, será borrada.

❗ Una cosa importante a tener en cuenta, el mayor elemento del subárbol izquierdo o el menor del subárbol derecho no tiene que ser precisamente los valores del subarbol inferior inmediato, es decir, si este subárbol también es un nodo interno habría que buscar también en los hijos de este en busca de la key correcta.

Utilizando la primera estrategia sería de la siguiente manera:

Quedando el árbol:

Lo mismo sería el caso para cuando el subárbol izquierdo tiene las keys mínimas y tendriamos que hacer esto mismo pero buscando recursivamente en el subárbol derecho.

Vamos a ver un ejemplo de cuando no es posible elevar una key de un subárbol izquierdo o un subárbol derecho. En el ejemplo anterior, si quisiéramos borrar la key 45, no podríamos elevar ninguna key. Por tanto lo que hacemos es mergear los nodos hermanos (41, 43) (51, 54) incluyendo la key del padre(45), para después borrarla

Por último borramos la key (quizás se puede borrar directamente del padre sin pasos intermedios)

Height reduce

Cuando realizamos las operaciones anteriores podemos llegar a un caso en el que no se pueda tomar keys del subárbol izquierdo o del subárbol derecho y solo será posible el merge, este merge lo que hara será reducir el heght o depth del árbol:

En el comienzo del ejemplo la altura o depth es 2

En este árbol si queremos eliminar la key 22, tenemos que borrar la key y hacer un merge de los hijos de la key, quedando:

Ahora bien, el nodo interno (75) se ha quedado con menos de las keys permitidas, por lo que tenemos que volver a mergear este con alguno de sus hermanos (izquierdo o derecho), en este caso con el único hermano que tiene

Quedando:

Por lo que se ha acabado reduciendo la altura o depth a 1.