Juan Garcés

Personal Blog

Estructuras de Datos No Lineales

enero 30th, 2013

(Un apunte de otra ayudantía de la universidad)

Árboles B

Los árboles B son estructuras no lineales que fueron introducidos por R. Bayer y E. McCreight en 1972, con el principal objetivo de mejorar el tiempo de acceso en estructuras de datos manejadas en memoria externa.

Los árboles B son una generalización de los árboles balanceados, con una estructura jerárquica que beneficia considerablemente la búsqueda de un elemento en específico, reduciendo el número de nodos o archivos accesados.

En un árbol B se debe procurar:

  1. Conservar la altura del árbol al mínimo, por lo que no deben existir subárboles vacíos al interior del árbol.
  2. Que todos los nodos, excepto la raíz, tengan un mínimo número de llaves (quizás la mitad del máximo).
  3. Que todas las hojas se mantengan al mismo nivel, garantizando así que las búsquedas se consigan con aproximadamente el mínimo número de accesos.

Luego, un árbol B de «orden d» se puede formalizar de la siguiente forma:

  1. Cada página (nodo), exceptuando la raíz contiene entre d y 2d elementos.
  2. Cada página (nodo), excepto la página raíz y las páginas hojas, tienen entre d+1 y 2d+1 descendientes. Se utiliza m para expresar el número de elementos pos cada página.
  3. La página raíz posee al menos dos descendientes.
  4. Las páginas hojas están todas al mismo nivel.

___________________________________

 

La inserción en árboles B: Para insertar elementos en un árbol B se debe:

  1. Determinar el máximo y mínimo número de elementos por nodo, de acuerdo al orden del árbol B:

    Key mínimo = d

    Key máximo = 2*d

  2. Hacer una búsqueda en el árbol B del lugar donde debe insertarse la llave.
  3. Toda inserción en un árbol B tiene lugar siempre en una hoja del árbol. Si la hoja no está llena, la llave es añadida en ésa hoja.
  4. Si el nodo hoja está lleno, entonces, éste se divide en dos (requiriendo la creación de un nuevo nodo) y la llave de valor medio se promueve como padre de los nodos. Si el nodo padre también está lleno, se repite el proceso, teniendo cuidado de mantener el orden de las llaves entre los subárboles.

Ejemplo de inserción en un árbol B de orden 2:

Para un árbol B de orden 2 (d=2) se utilizarán nodos que podrán contener hasta d (2) elementos como mínimo y 2*d (2*2=4) elementos como máximo.

Insertemos los siguientes elementos en el árbol:

10 – 20 – 5 – 25 – 30 – 35 – 34 – 9 – 40 – 45 – 18 – 2 –

70 – 65 – 27 – 50 – 42 – 17 – 13 – 1 – 54 – 12 – 22 – 67

Paso 1) Para el primer paso se insertan los elementos en forma ordenada en el primer nodo hasta que se llene y se deba insertar uno que sobrepase el número de elementos máximo por nodo. Como se muestra en el ejemplo, se insertan los elementos 10, 20, 5 y 25 hasta que llega el número 30, que produce que el nodo se rebalse y se aumente en un nivel como se muestra en el paso 2.

Paso 2) La inserción del número 30 produce que el nodo se rompa en dos y que el número que se encuentra en el centro de todos pase a se padre, como se aprecia, al ingresar el número 30 es el número 20 el que queda en el centro de los 5 (los cuatro del nodo y el que viene ingresando), por lo que es el 20 el que se transforma en padre de los demás nodos. Se continúa insertando hasta que llega el 40, que produce un nuevo quiebre del nodo, pasando el 34 al nodo padre.

Paso 3) Como se aprecia, al ingresar el 40, el 34 pasa al nodo padre, separándose el nodo formado por los números 25, 30, 34 y 35. Lo mismo ocurre al ingresar el número 2, pasando al paso 4.

Paso 4) Se continúa la inserción hasta que llega el número 65, que produce un nuevo quiebre y que el 45 llegue al nodo padre.

Paso 5) Se continúa la inserción de elementos hasta que llega el número 12, lo que provoca que el 13 pase al nodo padre que en este momento esta lleno, por lo que llegamos a la situación vista en el paso 1, donde el nodo que esta lleno, al recibir otro elemento se divide en dos, volviéndose a subir un nivel, como se aprecia en el paso 6.

Paso 6) La inserción del número 12 provocó que el 13 subiera al nodo padre y se dividiera en dos, con lo que el número 20, que quedó en el centro, pasa a ser el padre, incrementándose en un nivel la altura del árbol.

Paso 7) Se continúa la inserción de elementos hasta que se llega al árbol final que se muestra a continuación.

_______________________________________

La eliminación en árboles B: Para eliminar elementos de un árbol B se deben tener presente los siguientes puntos:

  1. Si la llave a eliminar está o no en un nodo hoja, y
  2. El mínimo número de elementos que puede tener un nodo hoja (d).

Durante el proceso de eliminación nos podemos encontrar con los siguientes casos:

  • Si la llave a eliminar está en una hoja, y el nodo tiene más del mínimo número de elementos, la eliminación es trivial, simplemente se borra el elemento.
  • Si la llave a eliminar está en una hoja y el nodo tiene el mínimo número de elementos, pero uno de los nodos adyacentes tiene más del mínimo número de elementos entonces:

    En este caso se lleva a cabo la combinación de tres nodos:

    • El nodo donde está el elemento a eliminar.
    • El nodo padre y
    • El nodo adyacente

    El proceso de borrado consiste en hacer un recorrido de los elementos en los nodos combinados, de tal forma que uno de estos elementos (el correspondiente según el orden) pase a tomar el lugar del elemento borrado

  • Si la llave a eliminar está en una hoja y el nodo tiene el mínimo número de elementos, pero ninguno de los nodos adyacentes tiene más del mínimo número de elementos.

    Entonces se tiene que perder una vía, creándose un nuevo nodo compuesto por los elementos de la combinación de tres nodos:

    • El nodo donde está el elemento a eliminar.
    • El nodo padre y
    • Uno de los nodos adyacentes
  • Finalmente, si la llave a eliminar no está en un nodo hoja, entonces el predecesor o sucesor en InOrden debe estar en un nodo hoja.

    El proceso de borrado consiste en sustituir el elemento borrado por el sucesor o predecesor en InOrden, verificando que se cumpla con la condición de un árbol B después de la sustitución.

Ejemplo de eliminación en un árbol B de orden 2:

    Dado el árbol anterior, eliminaremos los siguientes elementos:

30 – 35 – 40 – 5 – 22 – 67 – 13

    El proceso de eliminar los elementos anteriores se aprecia en los siguientes pasos:

Paso 1) Eliminar los elementos 30 y 35 produce que el árbol continúe con la misma estructura, conservándose el nivel de éste, ya que los elementos eliminados no pasa a llevar la regla del mínimo de elementos por nodo.

Paso 2) Al eliminar el elemento 40, el nodo contendrá el mínimo de elementos, pero el nodo adyacente izquierdo tiene más del mínimo de elementos, con lo que se puede realizar una combinación entre el nodo donde está el elemento a eliminar, el nodo padre y el nodo adyacente izquierdo, obteniéndose el resultado que se muestra.

Paso 3) La eliminación del número 5 es trivial, ya que el nodo contiene más del número mínimo de elementos.

Paso 4) Al eliminar el número 22 se produce la pérdida de una vía, deviéndose combinar el nodo donde se eliminará el elemento, el nodo padre y uno de los nodos adyacentes, que en este caso es el derecho.

Paso 5) La eliminación del número 67 produce nuevamente el caso anterior, con lo que se repite la combinación entre el nodo en el que se encuentra el elemento a eliminar, el nodo padre y en este caso, el nodo adyacente izquierdo. Pero aquí ocurre además otro efecto, ya que al combinar, queda el nodo padre con un solo elemento, lo cual no está permitido, con lo que se realizan los movimientos que se muestran con las flechas hasta llegar al árbol que se muestra más abajo.

Árbol resultante de eliminar el elemento 67:

Paso 6) La eliminación del elemento 13 produce que el nodo padre quede con un solo hijo, algo parecido al paso anterior, pero ahora no hay elementos que puedan reemplazar a la raíz, con lo que se pierde un nivel, bajándose el 20 y uniéndolo con los nodos formados con el 9 y 13 y con el formado por el 42 y 54 como se muestra a continuación:

El árbol B resultante de la eliminación del número 13 es el siguiente:

Los Árboles B+

Los árboles B+ son una variación de los árboles B que presentan las mismas características, pero con la salvedad de que en los árboles B+, la clave que pasa a ser padre, se debe repetir en su hijo derecho.

Con lo anterior se tendrá que en un árbol B+, todos los elementos que se insertarán se encontrarán al nivel de hoja, por lo que los elementos de niveles superiores servirán como índices para llegar a los elementos que se encuentran en las hojas.

Por ejemplo, veamos como resultaría el árbol B+ con los elementos que hemos utilizado para crear el árbol B de más arriba.

Los elementos eran los siguientes:

10 – 20 – 5 – 25 – 30 – 35 – 34 – 9 – 40 – 45 – 18 – 2 –

70 – 65 – 27 – 50 – 42 – 17 – 13 – 1 – 54 – 12 – 22 – 67

El resultado final de la inserción de los elementos anteriores es el siguiente:

(los pasos intermedios se dejan de tarea)

Ejercicio dePráctica:

Cree un árbol B de orden 2 con los siguientes elementos:

5

7

15

2

18

30

25

37

43

36

1

10

32

55

13

17

19

50

70

63

23

8

9

45

77

Una vez creado el árbol final, elimine los siguientes elementos:

7

30

9

19

63

Juan Garcés

Personal Blog