ARBOLES B

Introducción

Los B-árboles sugieron en 1972 creados por R.Bayer y E.McCreight.El problema original comienza con la necesidad de mantener índices en almacenamiento externo para acceso a bases de datos,es decir,con el grave problema de la lentitud de estos dispositivos se pretende aprovechar la gran capacidad de almacenamiento para mantener una cantidad de información muy alta organizada de forma que el acceso a una clave sea lo más rápido posible.

Los árboles con múltiples hijos hacen que el mantenimiento de índices en memoria externa sea mucho más eficiente y es justamente éste el motivo por el que este tipo de árboles han sido los que tradicionalmente se han usado para el mantenimiento de índices en sistemas de bases de datos.Lógicamente,aunque este tipo de estructuras sean más idóneas para mantener grandes cantidades de datos en almacenamiento externo es posible construirlas de igual forma en memoria principal,y por consiguiente pueden ser mantenidas en memoria (mediante el uso de punteros por ejemplo)al igual que las que hemos estudiado hasta ahora.

Los árboles B constituyen una categoría muy importante de estructuras de datos, que permiten una complementación efciente de conjuntos y diccionarios, para operaciones de consulta y acceso secuencial. Existe una gran variedad de árboles B: los árboles B, B+ y B*; pero todas ellas están basadas en la misma idea, la utilización de árboles de búsqueda no binarios y con condición de balanceo.

El árbol B fue desarrollado para mantener estructuras de datos cuyo contenido se va modificando con el tiempo (Alta y bajas) de forma de poder encontrar en forma rápida y eficiente un elemento en particular. Para ello se busca que la profundidad del árbol sea la menor posible. Se requería también que la modificación del contenido no sea muy costosa en tiempo y espacio. Están pensados para disminuir la cantidad de accesos a disco, y la posibilidad de mantener en memoria la parte que se está utilizando y el resto conservarlo en el disco.

características

• Se utilizan para manejar archivos que contienen gran cantidad de información.
• Son una generalización de los arboles balanceados
• Son utilizados como método de búsqueda externa
• cada nodo en un árbol b  de orden n contiene 2n  claves como nodos máximo y n claves como mínimo
• las paginas se almacenan en memoria secundaria , la raíz  se almacena en la memoria principal 
• las paginas hojas están todas en el mismo nivel.
• crecen de abajo hacia arriba  

Definición

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. Los nodos que conforman el árbol B son denominados Páginas, para comprender de una mejor manera el concepto de Árbol B es necesario, primeramente, conocer la estructura básica de una página.

• Un campo Puntero Página < Dato, se utiliza para establecer el enlace con otra página que posee datos menores del dato que posee
• Dato, información que posee la pagina
• Un campo Puntero Página > Dato, que se utiliza para establecer el enlace con otra página que posee datos menores del dato que posee, si la pagina fuera el último de la lista, este campo tendrá como valor: NULL (vacío). Al emplearse el campo puntero sig para relacionar dos nodos, no será necesario almacenar físicamente a los nodos en espacios contiguos.

Estructura de una Página

Cada elemento de una página interno actúa como un valor separador, que lo divide en sub árboles. Las páginas de un árbol B, es decir las páginas que no son hoja, usualmente se representan como un conjunto ordenado de elementos y punteros a los hijos. Cada página interna contiene un máximo de M hijos y, con excepción del nodo raíz, un mínimo de X hijo(s). Esta relación entre M y X implica que dos nodos que están a medio llenar pueden unirse para formar una página con las características básicas, y un nodo lleno puede dividirse (romperse) en dos páginas con las características básicas. Estas propiedades hacen posible que el árbol B se ajuste para preservar sus propiedades ante la inserción y eliminación de elementos.

Las páginas hoja tienen la misma restricción sobre el número de elementos, pero no tienen hijos, y por tanto poseen punteros vacios (nulos). 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 las páginas hoja, y por lo tanto sus páginas internas y páginas hojas son de diferente tipo. Los árboles B guardan valores en cada página, y pueden utilizar la misma estructura para todos las páginas.

Un ÁRBOL B de orden n es un árbol de búsqueda que satisface :

• Cada página contiene como máximo 2n claves
• Cada página contiene como mínimo n claves,excepto la raíz que puede tener sólo una.
• Cada página o es una página hoja o tiene m+1 descendientes (enlaces a sus hijos), siendo m el número de claves en ésta.
• Todas las páginas hoja están al mismo nivel.
  

1. 1. • 
        

Insertar

1. La raíz es la única pagina que puede contener un numero menor  de llaves o de claves al indicado por n.
2. toda pagina que no sea la raíz debe contener un numero de llaves  n>=n mayor o igual a n y menor o igual a m. 
3. toda pagina con un m de llaves  debe tener m+1 apuntadores dirigidos a m+1. paginas, que son los hijos de la pagina.
4. las llaves de cada una de las paginas debe almacenarse  de forma ascendente
5. todas las hojas deben estar en n mismo nivel.
6. la raíz puede ser eventualmente una hoja
7. Realizando una búsqueda en el árbol, se halla el nodo hoja en el cual debería ubicarse el nuevo elemento.
8. 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.
9. De otra forma, el nodo debe ser dividido en dos nodos. La división se realiza de la siguiente manera:Se escoge el valor medio entre los elementos del nodo y el nuevo elemento.
10. 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.
11. 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í:

Eliminar
La idea para realizar el borrado de una clave es similar a la inserción teniendo en cuenta que ahora, en lugar de divisiones, realizamos uniones. Existe un problema añadido, las claves a borrar pueden aparecer en cualquier lugar del árbol y por consiguiente no coincide con el caso de la inserción en la que siempre comenzamos desde una hoja y propagamos hacia arriba. La solución a esto es inmediata pues cuando borramos una clave que está en un nodo interior, lo primero que realizamos es un intercambio de este valor con el inmediato sucesor en el árbol, es decir, el hijo más a la izquierda del hijo derecho de esa clave.
Las operaciones a realizar para poder llevar a cabo el borrado son por tanto:

1. Consiste en eliminar una llave sin violar los principios de los arboles b
2. Si la llave se encuentra en una pagina hoja simplemente se elimina
3. De lo contrario se debe bajar  la llave léxico gráficamente adyacente en la pagina antecedente y sustituir esta llave por la que se encuentre mas a la derecha del sub árbol izquierdo o por la que este mas a la izquierda del sub árbol derecho.
4. Redistribución: la utilizaremos en el caso en que al borrar una clave el nodo se queda con un número menor que el mínimo y uno de los hermanos adyacentes tiene al menos uno más que ese mínimo, es decir, redistribuyendo podemos solucionar el problema.
5. Unión: la utilizaremos en el caso de que no sea posible la redistribución y por tanto sólo será posible unir los nodos junto con la clave que los separa y se encuentra en el padre. En definitiva, el algoritmo nos queda como sigue:

• Localizar el nodo donde se encuentra la clave..
• Si el nodo localizado no es una hoja, intercambiar el valor de la clave localizada con el valor de la clave más a la izquierda del hijo a la derecha. En definitiva colocar la clave a borrar en una hoja. Hacemos nodo actual igual a esa hoja.
• Borrar la clave.
• Si el nodo actual contiene al menos el mínimo de claves como para seguir siendo un B-árbol, fin.
• Si el nodo actual tiene un número menor que el mínimo:
• Si un hermano tiene más del mínimo de claves, redistribución y fin.
• Si ninguno de los hermanos tiene más del mínimo, unión de dos nodos junto con la clave del padre y vuelta al paso 4 para propagar el borrado de dicha clave (ahora en el padre).

ARBOLES AVL

Definicion

Un árbol AVL es un caso especial de un árbol binario con altura balanceada.  Un árbol binario es un árbol-p de altura balanceada si para cada nodo en el árbol, la diferencia de las alturas de sus dos subárboles es máximo p.  Un árbol AVL es un árbol-1 de altura balanceada, es decir, en un árbol AVL la diferencia de las alturas de los dos subárboles de cualquier nodo no puede ser mayor que 1.

Los árboles AVL están siempre equilibrados de tal modo que para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha o viceversa. Gracias a esta forma de equilibrio (o balanceo), la complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad . El factor de equilibrio puede ser almacenado directamente en cada nodo o ser computado a partir de las alturas de los subárboles.

si el factor de equilibrio del árbol es distinto  de -1 a 1  entonces el arbol se debe balancear

Caracteristicas

Un AVL es un ABB 

La diferencia entre las alturas de los subárboles derecho e izquierdo no debe excederse en más de 1. 

Cada nodo tiene asignado un peso de acuerdo a las alturas de sus subárboles. 

Un nodo tiene un peso de 1 si su subárbol derecho es más alto, -1 si su subárbol izquierdo es más alto y 0 si las alturas son las mismas. 

La inserción y eliminación en AVL es la misma que en los ABBs. 

Equilibrio

Equilibrio (n) = altura-der (n) – altura-izq (n) describe relatividad entre subárbol der y subárbol izq. 

+ (positivo) -> der mas alto (profundo)

- (negativo) -> izq mas alto (profundo)

Un árbol binario es un AVL si y sólo si cada uno de sus nodos tiene un equilibrio de –1, 0, + 1.

Si alguno de los pesos de los nodos se modifica en un valor no válido (2 o -2) debe seguirse un esquema de rotación.

Operaciones sobre un AVL

Insertar

Balancear 

* Caso 1 Rotación simple izquierda RSI

* Caso 2 Rotación simple derecha RSD

* Caso 3 Rotación doble izquierda RDI

* Caso 4 Rotación doble derecha RDD

- Eliminar

- Calcular Altura

Insertar un Dato

Usamos la misma técnica para insertar un nodo en un ABB ordenado.

Trazamos una ruta desde el nodo raiz hasta un nodo hoja (donde hacemos la inserción).

Insertamos el nodo nuevo.

Volvemos a trazar la ruta de regreso al nodo raíz, ajustando el equilibrio a lo largo de ella.

Si el equilibrio de un nodo llega a ser + - 2, volvemos a ajustar los subárboles de los nodos para que su equilibrio se mantenga acorde con los lineamientos AVL (que son +- 1). 

Balancear el Árbol

Caso 1: Rotación simple izquierda RSI

Si esta desequilibrado a la izquierda y su hijo derecho tiene el mismo signo (+) hacemos rotación sencilla izquierda. 

Luego de la rotación:

Caso 2: Rotación simple derecha RSD

Luego de la rotación:

Hay varios puntos que cabe señalar aquí:

- Se conserva el orden apropiado del árbol.

- Restablece todos los nodo a equilibrios apropiados AVL

- Conserva el recorrido en orden que el árbol anterior.

- Sólo necesitamos modificar 3 apuntadores para lograr el nuevo equilibrio (con la de la raíz).

Caso 3: Rotación doble izquierda RDI

Si está desequilibrado a la izquierda (FE < –1), y su hijo derecho tiene distinto signo (+) hacemos rotación doble izquierda-derecha.

Otro ejemplo de esta rotación:

Caso 4: Rotación doble derecha RDD

Si esta desequilibrado a la derecha y su hijo izquierdo tiene distinto signo (–) hacemos rotación doble derecha-izquierda.

Otro ejemplo:

Eliminar un Dato

Al eliminar un nodo en un árbol AVL puede afectar el equilibrio de sus nodos. Entonces hay que hacer rotaciones simples o dobles.

Eliminas un nodo como lo hacemos en un árbol binario ordenado. Al localizar el nodo que queremos eliminar seguimos este procedimiento:

- Si el nodo es un nodo hoja, simplemente lo eliminamos.

- Si el nodo solo tiene un hijo, lo sustituimos con su hijo.

- Si el nodo eliminado tiene dos hijos, lo sustituimos por el hijo derecho y colocamos el hijo izquierdo en el subárbol izquierdo del hijo derecho.

Ahora que hemos eliminado el nodo, tenemos que volver a equilibrar el árbol:

- Si el equilibrio del padre del nodo eliminado cambia de 0 a +-1 el algoritmo concluye.

- Si el padre del nodo eliminado cambio de +-1 a 0, la altura del árbol ha cambiado y se afecte el equilibrio de su abuelo.

- Si el equilibrio del padre del nodo eliminado cambia de +- 1 a +- 2 hay que hacer una rotación.

- Después de concluirla, el equilibrio del padre podría cambiar, lo que, a su vez, podría forzarnos a hacer otros cambios (y probables rotaciones) en toda la ruta hacia arriba a medida que ascendemos hacia la raíz. Si encontramos en la ruta un nodo que cambie de 0 a +- 1 entonces terminamos.

simulador

manual simulador arbol avl
simulador inserción arboles avl 

ARBOLES B+

Los árboles-B+ se han convertido en la técnica mas utilizada para la organización de archivos indizados. La principal característica de estos arboles es que todas las claves se encen la misma longitud. En la figura  representamos un diagrama de un árbol-B+ de orden 2.uentran en las hojas y por lo tanto cualquier camino desde la raíz hasta alguna de las claves tien

Es de notar que los arboles-B+ ocupan un poco mas de espacio que los arboles-B, y esto ocurre al existir duplicidad en algunas claves. Sin embargo, esto es aceptable si el archivo se modifica frecuentemente, puesto que se evita la operación de reorganización del árbol que es tan costosa en los arboles-B.

Formalmente se define un árbol-B+ de la siguiente manera:

1. Cada pagina, excepto la raíz, contiene entre d y 2d elementos.
2. Cada pagina, excepto la raíz, tiene entre d + 1 y 2d + 1 descendientes. Se utiliza m para expresar el numero de elementos por pagina.
3. La pagina raíz tiene al menos dos descendientes.
4. Las paginas hojas están todas al mismo nivel.
5. Todas las claves se encuentran en las paginas hojas.
6. Las claves de las paginas raíz e interiores se utilizan como índices.
7. Búsqueda De Arboles-B+

La operación de búsqueda en árboles-B+ es similar a la operación de búsqueda en árboles-B. El proceso es simple, sin embargo puede suceder que al buscar una determinada clave la misma se encuentra en una pagina raíz o interior, en dicho caso no debe detenerse el proceso, sino que debe continuarse la búsqueda con la pagina apuntada por la rama derecha de dicha clave. Por ejemplo, al buscar la clave 55 en el árbol-B+ de la figura 8.4 se advierte que esta se encuentra en la pagina raíz. En este caso, debe continuarse el proceso de búsqueda en la pagina apuntada por la rama derecha de dicha clave

Inserción en árboles B+

El proceso de inserción en árboles-B+ es relativamente simple, similar al proceso de inserción en árboles-B. La dificultad se presenta cuando desea insertarse una clave en una pagina que se encuentra llena ( m = 2d ). En este caso, la pagina afectada se divide en 2, distribuyéndose las m + 1 claves de la siguiente forma: " las d primeras claves en la pagina de la izquierda y las d + 1 restantes claves en la pagina derecha ". Una copia de la clave del medio sube a la pagina antecesora. En la figura 8.5 hay dos diagramas que ilustran como funciona este caso.

Figura 8.5 Inserción de la clave 13 en un árbol B+.
a) Antes de insertar la clave.b)Después de insertarla.

Puede suceder que la pagina antecesora se desborde nuevamente, entonces tendrá que repetirse el proceso anterior. Es importante notar que el desbordamiento en una pagina que no es hoja no produce duplicidad de claves. El proceso de propagación puede llegar hasta la raíz, en cuyo caso la altura del árbol puede incrementarse en una unidad. En la figura 8.6 se presentan dos diagramas que clarifican y resuelven este caso.

Figura 8.6 Inserción de la clave 66 en un árbol-B+
a) Antes de insertar la clave b) Después de insertarla.

Ejemplo 8.5.1

Supóngase que se desea insertar las siguientes claves en un árbol-B+ de orden 2 que se encuentra vacío:

claves: 10-27-29-17-25-21-15-31-13-51-20-24-48-19-60-35-66

Los resultados parciales que ilustran el crecimiento del árbol se presentan en los siguientes diagramas correspondientes a la figura 8.7

Figura 8.7 Inserciones en un árbol-B+ de orden2
(primera parte)

Figura 8.7 Inserción de un árbol-B+ de orden 2
(Segunda parte)

 Borrado En Arboles-B+

La operación de borrado en árboles-B+ es mas simple que la operación de borrado en árboles-B. Esto ocurre porque las claves a eliminar siempre se encuentran en las paginas hojas. En general deben distinguirse los siguientes casos:

1. Si al eliminar una clave, m queda mayor o igual a d entonces termina la operación de borrado. Las claves de las paginas raíz o internas no se modifican por mas que sean una copia de la clave eliminada en las hojas. ( Se presenta un ejemplo de este caso en la figura 8.9 ).

Figura 8.9 Eliminación de la clave 25
a) Antes de eliminar la clave. b) Después de eliminarla.

2. Si al eliminar una clave, m queda menor a d entonces debe realizarse una redistribución de claves, tanto en el índice como en las paginas hojas. ( Hay dos ejemplos que ilustran como funciona este caso en la figura 8.10 ).

Figura 8.10 Eliminación de la clave 27
a) Antes de eliminar la clave. b) Después de eliminarla.

Nota: Al eliminar la clave 27 de la página A, m queda menor a d por lo que debe realizarse una redistribución de las claves. Se toma la clave que se encuentra más a la derecha en la rama izquierda de 25 (21 de la página B). Se coloca dicha clave en la página A y una copia de la misma, como índice, en la página C.

Figura 8.10 Eliminación de la clave 21
b) Antes de eliminar la clave. d) Después de eliminarla.

Nota: Al eliminar la clave 21 de la página A, m queda menor a d por lo que debe realizarse una redistribución de claves. Como no se puede tomar una clave de la página B puesto que m quedaría menor a d, entonces se realiza una fusión de las páginas A y B.

Puede suceder que al eliminar una clave y al realizar una redistribución de las mismas, la altura del árbol disminuya en una unidad. ( En la figura 8.11 se presentan dos diagramas que clarifican y resuelven este caso).

Figura 8.11 Eliminación de la clave 37
a) Antes de eliminarla. b) Después de eliminarla.

Nota: Al eliminar la clave 37 de la página A, m queda menor a d por lo que debe realizarse una redistribución de claves. Como no puede tomarse una clave de la página B puesto que m quedaría menor a d, entonces se realiza una fusión de las páginas A y B. Sin embargo, luego de está fusión m queda menor a d en la página C, por lo que debe bajarse la clave 29 de la página E y realizarse una nueva fusión, ahora de las páginas C y E. La altura del árbol disminuye en una unidad.

Ejemplo 8.5.3

Suponga que desea eliminar las siguientes claves del árbol-B+ de orden 2 de la figura 8.12:

claves: 15-51-48-60-31-20-10-25-17-24

Figura 8.12 Arbol-B+ de orden 2

Los resultados parciales que ilustran como funciona el procedimiento se presentan en los diagramas de la figura 8.13.

Figura 8.13
Eliminaciones en un árbol-B+ de orden 2
(Primera parte)

Figura 8.13
Eliminaciones en un árbol-B+ de orden 2
(Segunda parte)