¿Qué son los árboles B?
Los árboles B, tal y como indica su nombre, son una estructura de datos arborescente. El árbol B es un árbol de búsqueda, por lo tanto, cada nodo está asociado a una clave. ¿Cuál es su particularidad? Pues que en esta estructura los nodos tienen asociados más de una clave.
ÁRBOL DE BÚSQUEDA (1 clave por nodo)
ÁRBOL B (más de 1 clave por nodo)
Fíjate que en el árbol binario de búsqueda los hijos derechos de un nodo contienen las claves más grandes que la clave del nodo padre y, a su vez, los hijos izquierdos contienen las claves más pequeñas que la clave del nodo padre. Algo similar ocurre con el árbol B, más adelante te lo explico en detalle.
Estructura
En esta sección te explico cúal es el esqueleto de esta estructura de datos. Primero de todo, debemos conocer un concepto importante, el orden:
- Orden: número máximo de hijos que puede tener un nodo (lo denotaremos como «m»).
A partir del orden podemos saber el número máximo de claves que puede tener un nodo. Este siempre será m – 1, te lo enseño con este ejemplo.
Puedes comprobar que, para un nodo de orden 4 (puede tener máximo 4 hijos), efectivamente el número de claves es m – 1 = 4 – 1 = 3.
Ahora viene la parte más importante de todas, ¿te acuerdas cuando te dije que los árboles B hacían una cosa parecida a los árboles de búsqueda a la hora de organizar los nodos por claves? Pues ahora mismo te lo explico.
Para el nodo anterior:
- Las claves están ordenadas de forma ascendente, es decir, K1 < K2 < K3
- El hijo 1 contendrá claves más pequeñas que K1
- El hijo 2 contendrá claves más grandes que K1 y más pequeñas que K2
- El hijo 3 contendrá claves más grandes que K2 y más pequeñas que K3
- El hijo 4 contendrá claves más grandes que K3
Analicemos un nodo del ejemplo para ver si se cumple esta estructura.
Propiedades de los árboles B
Para poder conseguir tener un árbol B, no solo debemos comprovar que este definido con la estructura anterior ya que también deben cumplirse una serie de propiedades fundamentales:
PROPIEDAD 1: los árboles B són SIEMPRE balanceados.
PROPIEDAD 2: todos los nodos de un árbol de orden m excepto la raíz deben cumplir que
Este símbolo ⌈ ⌉ significa redondear hacia arriba, por ejemplo:
PROPIEDAD 3: todas las hojas, es decir, los nodos sin hijos, están al mismo nivel.
PROPIEDAD 4: todo nodo interno (no es hoja) con n claves tiene n + 1 hijos.
Anteriormente, hemos comprobado que el árbol B ejemplo cumplía con la estructura. Veamos si cumple con estas tres propiedades.
Verificamos que:
- Las hojas están al mismo nivel ✅
- Está equilibrado (lo implica que todas la hojas estén al mismo nivel) ✅
- Todos los nodos excepto la raíz tienen un mínimo de 1 clave ✅
- Todos los nodos internos tienen n + 1 hijos, donde n es el número de claves ✅
Algoritmos de inserción y eliminación
Lo más impresionante de esta estructura de datos es que, mediante unos algoritmos determinados, podemos insertar y eliminar claves sin alterar su estructura ni propiedades fundamentales. Empecemos con cómo insertar una nueva clave en un árbol B.
Inserción en un árbol B
Al insertar una nueva clave solo debemos introducirla en la posición que le corresponda. No obstante, podemos encontrarnos con algunas dificultades a la hora de añadirla.
En esta sección te explico todos los casos con los que te puedes encontrar con ejemplos. Para ello, operaremos sobre este árbol:
Caso 1: la clave puede inserirse sin problemas
Empecemos por el más fácil. Vamos a añadir el nodo 39.
Como puedes ver, no es difícil. Solo debes ir recorriendo el árbol dependiendo del tamaño de la clave para encontrar su nodo.
Caso 2: La clave ya se encuentra en el árbol
En este caso la estructura del árbol quedaria exactamente igual, no tenemos que cambiar nada.
Eso sí, hay que pensar que los árboles B sirven para almacenar datos de forma ordenada y que las claves solo son un identificador de estos datos. Es decir, imagina que este árbol sirve para guardar los nombres de los alumnos de un instituto. La clave 30 tiene asociada, por ejemplo, ‘Juan’. Si insertásemos la clave 30 con un nuevo nombre, por ejemplo, ‘Javier’ el árbol quedaria exactamente igual pero la información asociada a la clave cambiaría.
Caso 3: el nodo está lleno (split)
Ahora inseriremos la clave 87.
¿Qué pasa? Pues que el nodo al que le toca introducirse está lleno. Para solucionarlo, inseriremos la clave al nodo lleno como si hubiera un espacio más.
Pero no podemos dejar el árbol así ya que los nodos deben ser de orden 4 y ahora tenemos un nodo de orden 5. Para solucionarlo partiremos este nodo por la mitad (split) y la clave del medio subirá al padre.
Finalmente, solo nos quedará añadir las conexiones entre el nodo padre y los nuevos hijos respectando la estructura fundamental.
Extra: ¿qué hago si al hacer un split el padre también está lleno?
Imagina que ahora añadimos el 91 a este árbol. Encontramos el nodo pero está lleno, por lo tanto, hacemos un split.
¿Qué ha pasado? Pues que el nodo padre al que debía subir el elemento del medio está lleno también. En consecuencia, nos vemos obligados a hacer otra división.
Finalmente, añadimos las conexiones correspondientes con los nuevos nodos.
Eliminación en un árbol B
Para eliminar una clave de un nodo debemos mirar si está y, si la encontramos, eliminarla. De momento todo parece muy fácil pero recuerda que los nodos de los árboles B deben cumplir la siguiente propiedad:
¿Qué pasaría si eliminamos una clave y dejamos a un nodo sin el número mínimo? Más adelante te lo cuento, de momento empecemos por los casos más básicos.
Caso 1: la clave no está en el árbol
En este caso no debemos hacer nada y dejar el árbol tal y como estaba.
Caso 2: la clave si está en el árbol
En este caso tenemos dos opciones: que la clave esté en una hoja o que esté en un nodo interno. Si está en una hoja, la eliminaremos y ya habremos acabado. En cambio, si se encuentra en un nodo interno, la eliminaremos y la siguiente clave en orden ascendente la reemplazará. Veámoslo con ejemplos en este árbol:
Eliminamos el 24 que está en una hoja.
Si eliminásemos el 70, que está en un nodo interno, la siguiente clave en orden ascendente lo reemplazaría. Vemos que esta es 82.
El árbol acabaría quedando así:
Caso 3: eliminar una clave genera déficit
Si al eliminar una clave generamos déficit en algun nodo, es decir, dejamos un nodo sin el número mínimo de claves tenemos dos opciones:
La primera opción será que el hermano izquierdo o el derecho le presten una clave. Para ello, será necesario que tengan más de el número mínimo, si no, se quedarían en déficit y seguiríamos con el mismo problema. La segunda opción será fusionar el nodo con déficit con uno de sus hermanos. Esta solo será viable si no se puede aplicar la primera. Veamos un ejemplo para cada una:
Empezaremos con el primer caso eliminando la clave 30 del siguiente árbol:
Vemos que al eliminarla generamos déficit.
Observamos que el hermano izquierdo puede prestarle una clave.
¡IMPORTANTE! Para mantener las propiedades de un árbol B el hermano no le presta una clave directamente. Lo que hacemos es subir al padre la clave del hermano (la más grande si es el izquierdo y la más pequeña si es el derecho) y bajamos la clave del padre al nodo con déficit.
Así es como queda finalmente:
Ahora, sobre este mismo árbol suprimiremos la clave 26. Como puedes comprobar, el hermano izquierdo no puede prestarle ninguna clave y, por si no fuera suficiente, no tiene hermano derecho.
Es en este momento es cuando debemos fusionar (merge) el nodo con déficit con uno de sus hermanos, en este caso, el izquierdo ya que no tiene hermano derecho.
¡IMPORTANTE! En la fusión uniremos las claves del nodo con déficit, las del hermano elegido y la clave del nodo padre de la cual cuelgan estos dos nodos.
Después de todo, terminamos con este árbol:
Si comprendes todos estos algoritmos y conceptos, ¡FELICIDADES, SE PODRÍA DECIR QUE ERES UN EXPERTO EN ÁRBOLES B! Si te ha quedado alguna duda, no dudes en comentarla para ver si puedo resolverla.