ÁRBOL B

Los árboles reciben su nombre de R. Bayer, quien en 1970 propuso un nuevo tipo de árboles, en los que todas las páginas, excepto una), contienen entre n y 2n nodos, siendo n una constante dada. Como consecuencia de esto se puede deducir que los árboles B no son árboles binarios como sí lo son los binarios de búsqueda o los AVL.

En los árboles B los nodos se agrupan dentro de páginas, por lo que se podría definir a la página como un conjunto de nodos.

Los árboles B deben cumplir las siguientes características en cuanto a estructura:

Toda página tiene como máximo 2n nodos.
Toda página distinta de la raíz tiene como mínimo n nodos. La raíz tiene como mínimo 1 nodo.
Toda página que no sea una hoja tiene m+1 páginas hijas, siendo m el número máximo de llaves.
Todas las páginas hoja están en el último nivel.
Además de estas características, los árboles B tienen que cumplir un cierto orden:

Los nodos dentro de una página mantienen un orden ascendente de izquierda a derecha.
Cada nodo es mayor que los nodos situados a su izquierda.
Cada nodo es mayor que los nodos situados a su derecha.
A continuación se muestran dos árboles, uno de ellos es un árbol B y otro no.

ESTRUCTURA DE UN ÁRBOL B: 

Cada hoja tiene 4 nodos. Este es un árbol B correcto, ya que cumple todas las reglas en cuanto a su estructura y al orden.

ESTRUCTURA DE UN ÁRBOL B INCORRECTO:

Nodo no raíz con menos de n nodos.
En cambio, este no es un árbol B, ya que a pesar de mantener el orden, hay una página (que no es la raíz) que tiene menos de n elementos (en este caso menos de 2 elementos). Esta página es la que contiene al elemento 10.

OPERACIONES:

las operaciones básicas que se pueden realizar en los árboles B:
*Búsqueda.
*Inserción.
*Retiro.

Ejemplo Inserción:

30, 60, 45, 8, 22, 35, 4, 28, 52, 33, 13, 39, 41, 43, 24, 25, 15.

Inserción: 30, 60, 45, 8:

Inserción: 22:

Inserción: 35, 4, 28, 52:

Inserción: 33:

Inserción: 13:

Inserción: 39:

Inserción: 41:

Inserción: 43:

Inserción: 24, 25:

Inserción: 15:

ELIMINACIÓN:

PROCESO DE ELIMINACIÓN:

* Buscar el elemento a eliminar.

* Si el elemento a borrar esta en el nodo hoja, se borra y termina (manteniendo reglas).

* Si el elemento no se encuentra en la hoja, se buscara el sustituto así:

           - El último elemento de la hoja más a la derecha del sub-árbol izquierdo del nodo actual.

             (el mayor de los menores).

           - El primer elemento de la hoja más a la izquierda del su-árbol derecho del nodo actual .

             (el menor de los mayores).  

Ejemplo:

Caso 1:

Retirar llaves 61 y 16:

no hay problema.

Caso 2:

Retirar llave 41:

En este caso se aplica la 2da regla (41=46 y 46=50)(llaves).

Para complementar estos temas: