Arboles B

ARBOLES B

Los árboles-Bo B-árboles son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos. Son árboles binarios de búsqueda en los cuales cada nodo puede poseer más de dos hijos.

 

DEFINICION

La idea tras los árboles-B es que los nodos internos deben tener un número variable de nodos hijo dentro de un rango predefinido. Cuando se inserta o se elimina un dato de la estructura, la cantidad de nodos hijo varía dentro de un nodo. Para que siga manteniéndose el número de nodos dentro del rango predefinido, los nodos internos se juntan o se parten.

 

DEFINICION TÈCNICA

B-árbol es un árbol de búsqueda que puede estar vacío o aquel cuyos nodos pueden tener varios hijos, existiendo una relación de orden entre ellos, tal como muestra el dibujo.

Un árbol-B de orden M (el máximo número de hijos que puede tener cada nodo) es un árbol que satisface las siguientes propiedades:

1.   Cada nodo tiene como máximo M hijos.

2.   Cada nodo (excepto raíz y hojas) tiene como mínimo M/2 hijos.

3.   La raíz tiene al menos 2 hijos si no es un nodo hoja.

4.   Todos los nodos hoja aparecen al mismo nivel.

5.   Un nodo no hoja con k hijos contiene k-1 elementos almacenados.

6.   Los hijos que cuelgan de la raíz (r1, ···, rm) tienen que cumplir ciertas condiciones:

1.  El primero tiene valor menor que r1.

2.  El segundo tiene valor mayor que r1 y menor que r2, etc.

3.  El último hijo tiene valor mayor que rm.

 

 

 

 

 

ALTURA

Con el objetivo de tener una acotación de la altura, h, del árbol B en función del número total de clave almacenados, n, y del orden del árbol B, m, calculamos inicialmente el número mínimo de enlaces por nivel en un árbol B.

 

Nivel               Número mínimo de enlaces

1                                             2

2                                        2*(m/2)

3                                        2*(m/2)2

h-1                                    2*(m/2)h-2

 

 

ESTRUCTURA DE UN NODO

Cada elemento de un nodo interno actúa como un valor separador, que lo divide en sub árboles.

Los nodos internos de un árbol B, es decir los nodos que no son hoja, usualmente se representan como un conjunto ordenado de elementos y punteros a los hijos. Cada nodo interno contiene un máximo de U hijos y, con excepción del nodo raíz, un mínimo de L hijos. Esta relación entre U y L implica que dos nodos que están a medio llenar pueden juntarse para formar un nodo legal, y un nodo lleno puede dividirse en dos nodos legales. Estas propiedades hacen posible que el árbol B se ajuste para preservar sus propiedades ante la inserción y eliminación de elementos.

Los nodos hoja tienen la misma restricción sobre el número de elementos, pero no tienen hijos, y por tanto carecen de punteros. El nodo raíz tiene límite superior de número de hijos, pero no tiene límite inferior. Algunos árboles balanceados guardan valores sólo en los nodos hoja, y por lo tanto sus nodos internos y nodos hoja son de diferente tipo. Los árboles B guardan valores en cada nodo, y pueden utilizar la misma estructura para todos los nodos. Sin embargo, como los nodos hoja no tienen hijos, una estructura especial para éstos mejora el funcionamiento.

 

 

 

 

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(*).

 

 

Inserción

Todas las inserciones se hacen en los nodos hoja.

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.

 

 

 

 

 

Eliminación

Es localizar y eliminar el elemento, y luego corregir, o hacer una única pasada de arriba a abajo por el árbol, pero cada vez que se visita un nodo, reestructurar el árbol para que cuando se encuentre el elemento a ser borrado, pueda eliminarse sin necesidad de continuar reestructurando

Se pueden dar dos problemas al eliminar elementos: primero, el elemento puede ser un separador de un nodo interno. Segundo, puede suceder que al borrar el elemento, el número de elementos del nodo quede debajo de la cota mínima. Estos problemas se tratan a continuación en orden.

 

Eliminación en un nodo hoja

§  Busque el valor a eliminar.

§  Si el valor se encuentra en un nodo hoja, se elimina directamente la clave, posiblemente dejándolo con muy pocos elementos; por lo que se requerirán cambios adicionales en el árbol.

 

Eliminación en un nodo interno

Cada elemento de un nodo interno actúa como valor separador para dos sub árboles, y cuando ese elemento es eliminado, pueden suceder dos casos. En el primero, tanto el hijo izquierdo como el derecho tienen el número mínimo de elementos, L-1. Pueden entonces fundirse en un único nodo con 2L-2 elementos. En el segundo caso, uno de los dos nodos hijos tiene un número de elementos mayor que el mínimo. Entonces se debe hallar un nuevo separador para estos dos sub árboles. Note que el mayor elemento del árbol izquierdo es el mayor elemento que es menor que el separador. De la misma forma, el menor elemento del subárbol derecho es el menor elemento que es mayor que el separador. Ambos elementos se encuentran en nodos hoja, y cualquiera de los dos puede ser el nuevo separador.

§  Si el valor se encuentra en un nodo interno, escoja un nuevo separador (puede ser el mayor elemento del subárbol izquierdo o el menor elemento del subárbol derecho), elimínelo del nodo hoja en que se encuentra, y reemplace el elemento a eliminar por el nuevo separador.

§  Como se ha eliminado un elemento de un nodo hoja, se debe tratar este caso de manera equivalente.

 

 

VIDEO TUTORIAL DE UN ARBOL B

http://www.youtube.com/watch?v=Jr5_ZrZgzk0

 

EJERCICIOS

 

1.    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.

 

2.    En el árbol R del problema anterior, elimine la clave 91 y dibuje el árbol resultante. Elimine ahora la clave 48.Dibuje el árbol resultante, ¿ha habido reducción en el número de nodos?

 

RESULTADO

1.       http://decsai.ugr.es/~jfv/ed1/tedi/cdrom/docs/Ej_B1.htm

http://decsai.ugr.es/~jfv/ed1/tedi/cdrom/docs/Ej_B2.htm
Comments