Procesos

ESTRUCTURA DE DATOS
ÁRBOLES B
NOMBRE: Alejandro Aguilar
El árbol B es un árbol de búsqueda, con algunas restricciones adicionales, que resuelve hasta cierto punto los dos problemas anteriores. Estas restricciones adicionales garantizan que el árbol siempre estará equilibrado y que el espacio desperdiciado por la eliminación, si lo hay, nunca será excesivo. Los algoritmos para insertar y eliminarse hacen más complejos para poder mantener estas restricciones. No obstante, la mayor parte de las inserciones y eliminaciones son procesos simples, se complican sólo en circunstancias especiales
* Operaciones básicas en árboles B
Las operaciones básicas que se pueden realizar en un árbol B son básicamente tres:
1. Buscar
2. Insertar
3. Eliminar
1.- Búsqueda
La búsqueda de unallave Y se realiza de manera análoga a la búsqueda en un árbol binario de búsqueda. Se comienza buscando por el nodo raíz y se compara la llave Y con las llaves Ki que se encuentran en ese nodo. Si Y es igual a algún Ki, termina la búsqueda satisfactoriamente, si no, se debe seguir el puntero adecuado hacia un nodo hijo en el que se continuará la búsqueda.
En la búsqueda en un árbol B el número deacceso a página es (h) = (log t n) donde h es la altura del árbol, n la cantidad de llaves, n<p y t=p/2. La búsqueda lineal de la llave en una página es O (t) por lo tanto el tiempo total es O (t*h)=O (t*log t n).
2.- Inserción
Lo primero que debe hacerse es un proceso de búsqueda, para localizar el nodo en el que se va a insertar. Si este proceso de búsqueda da por resultado que el elemento yaexiste, no se realizará ninguna operación, pues el árbol B no permite elementos repetidos.
La búsqueda de un elemento inexistente y que, por tanto, pueda ser insertado en el árbol, terminará en el momento en que, tratando de buscar un puntero Pi que apunte al nodo donde debería estar el elemento, encontremos un puntero nulo, siendo insertado el nuevo elemento en el nodo actual. Cuando se inserta enun nodo que no está lleno, solo debemos preocuparnos por el lugar que debe ocupar la nueva llave en ese nodo y hacer un corrimiento de las restantes.
El problema surge cuando ya se han insertado varias llaves en un mismo nodo hasta que este queda completo. Una vez lleno un nodo con p-1 valores de la clave de búsqueda, si intentamos insertar una entrada más en él, debemos seguir el siguienteprocedimiento:
1. Insertar la llave como si realmente tuviese sitio libre.
2. Extraer el nodo que ocupa la posición del medio e insertarlo en la página padre.
3. Si no hubiese página padre se crearía una nueva página con ese nodo.
4. Dividir equitativamente la página original en dos nuevas páginas Estas páginas serán los hijos derechos e izquierdos del nodo que promocionó a la páginasuperior.
5. Si la página a la que promociona el nodo mediano también se encuentra completa, se repetiría la misma operación de división y promoción.
La división puede propagarse hasta llegar al nodo raíz. En caso que el nodo raíz deba dividirse también, el elemento que es promocionado para ser insertado en el padre, será insertado en un nuevo nodo que se debe crear, que pasará a ser la nueva raízdel árbol, creando un nuevo nivel cada vez que se divida la raíz.

Ej. 1 Supongamos que queremos insertar la clave 52 en el árbol siguiente.

No hay espacio para almacenar la clave en nodo, por lo tanto, este nodo debe dividirse, promocionando la llave que queda en el medio, en este caso, el 65:

Ahora tenemos que promocionar la clave intermedia, insertándola en el nodo padre. Como la llavepromocionada, pudo insertarse sin dificultad en el nodo padre, el proceso termina.

Ej. 2 Implicará que aumente la altura del árbol. Supongamos que tenemos un árbol con esta estructura, y queremos insertar la clave 68:

En primer lugar, dividimos nodo en dos, repartimos las claves y promocionamos el valor intermedio, el 69:

Ahora estamos de nuevo en la misma situación, cuando tratamos de insertar el 69...