Arboles B

ARBOLES B

Introducción

Caracteristicas

Se utiliza como método de busca externo.

Fueron propuestos por Bayer y E Mc Creight en 1970

Cada nodo (pagina) en un árbol B de orden N contiene 2N claves como máximo y N claves como mínimo.

Cada pagina tiene 2N hijos como maximo y N+1 hijos como minino execpto la pgina raiz que puede tener como minimo 1 clave y por consiguiente 2 hijos.Las paginas se almacenan en dispositivos secundarios la pagina raiz se almacena en memoria principal.

las paginas hojas estas todas el mismo nivel

Búsqueda
Se empieza en la raíz, y se recorre el árbol hacia abajo, escogiendo el sub-nodo de acuerdo a la posición relativa del valor buscado respecto a los valores de cada nodo.

1.   Situarse en el nodo raíz.
2.   (*) Comprobar si contiene la clave a buscar.
1.  Encontrada fin de procedimiento.
2.  No encontrada:
1. Si es hoja no existe la clave.
2. En otro caso el nodo actual es el hijo que corresponde:
1.    La clave a buscar k < k1: hijo izquierdo.
2.    La clave a buscar k > ki y k < ki+1 hijo iésimo.

3.    Volver a paso 2(*).

Insertar

1. Realizando una búsqueda en el árbol, se halla el nodo hoja en el cual debería ubicarse el nuevo elemento.
2. Si el nodo hoja tiene menos elementos que el máximo número de elementos legales, entonces hay lugar para uno más. Inserte el nuevo elemento en el nodo, respetando el orden de los elementos.
3. De otra forma, el nodo debe ser dividido en dos nodos. La división se realiza de la siguiente manera:
1. Se escoge el valor medio entre los elementos del nodo y el nuevo elemento.
2. Los valores menores que el valor medio se colocan en el nuevo nodo izquierdo, y los valores mayores que el valor medio se colocan en el nuevo nodo derecho; el valor medio actúa como valor separador.
3. El valor separador se debe colocar en el nodo padre, lo que puede provocar que el padre sea dividido en dos, y así sucesivamente.

Ejemplo de Insertar:

Se desea insertar en un árbol B de grado 2, los siguientes elementos: 30, 60, 45, 8, 22, 35, 4, 28, 52, 33, 13, 39, 41, 43, 24, 25 y 15

• Insertar primero 30, 60, 45 y 8.
• 
• Seguidamente al insertar el 22, se produce desbordamiento, por lo que se llevará a cabo el proceso de rompimiento de la página en la inserción.
• 
• Seguidamente se insertan las llaves 35, 4, 28, 52 sin problemas, pero al insertar la llave 33 se produce  un nuevo desbordamiento, por lo que se volverá al proceso de inserción con desbordamiento.
• 
• Al insertar la llave 13, se produce nuevamente un desbordamiento.
• 
• Se insertan 39 y 41 sin problemas, pero al insertar 43 hay desbordamiento, por lo que:
• 
• Se insertan 24 y 25 nuevamente sin problema, pero al insertar el 15 se produce un doble desbordamiento, por lo tanto:
• 
• Quedando el árbol finalmente así:

• 

El proceso de borrado puede llegar a ser algo más complejo que la inserción. Eliminación
La eliminación se realiza de la misma manera que en los arboles B siempre y cuando no altere el valor mínimo de claves que debe de tener cada pagina. Se presentan los siguientes casos con ejemplos: 1. Cuando la clave a eliminar sobrepasa el limite inferior de datos por pagina y su hermano tiene para cederle se procede así:

Al eliminar el 35 se rotaria el 40 a la primera pagina y el 45 subira de padre



2. Cuando la clave a eliminar sobrepasa el limite inferior de datos por pagina y ninguno de sus hermanos tiene para prestarle, se busca un hermano de mas alla y se hacen las rotaciones necesarias para traerlo.



En este caso se debe rotar el 92 y se baja el 90 y subira el 50 y por ultimo bajara el 48, asi quedo otra vez equilibrado
Video Complementario



2.Cuando en el nodo que se va a eliminar la clave queda por debajo del limite y ninguno de sus hermanos tiene para rotarle se deben unir los dos nodos hermanos y al que se le elimino para formar dos nuevos nodos.


Se deben unir H0-H1-H2 para formas solo dos nodos. De esta forma

El arbol final quedaria con el 40 como padre de sus lados, El arbol resultante seria asi


Vídeo Complementario

Ejercicio

Dada la secuencia de claves enteras:190,57,89,90,121,170,35,48, 91,22,126,132 y 80;dibuje el árbol B de orden 5 cuya raíz es R,que se corresponde con dichas claves