Arboles

Arboles B

Son árboles multicamino con una construcción especial en forma ascendente,

permite mantener el árbol balanceado a bajo costo.

Definición:

Los árboles B son árboles cuyos nodos pueden tener un número múltiple de hijos.

Tienen por objetivo agrupar en cada nodo más de un elemento de manera que el acceso a un elemento cualquiera tenga lugar visitando.

Esto es útil cuando el árbol se halla almacenado en un dispositivo de acceso lento, como disco duro, y acceder a un nodo implica acceder a un sector distinto del disco.

Operaciones básicas

• Búsqueda (similar a los árboles multicamino de búsqueda)

• Inserción (se realiza en las hojas. Se pueden producir reestructuracionesdel árbol en el camino de vuelta)

• Borrado (se realiza en las hojas. Se pueden producir reestructuraciones del árbol en el camino de vuelta)

Insercion

Pasos necesarios:

1) Búsqueda del nodo hoja correspondiente en orden a la clave a insertar, x, la cual será insertada si no existe en el árbol

2) Si el nodo hoja correspondiente no está lleno, es decir, el número de claves o entradas es menor que “m-1”, se insertará en ese nodo, respetando el orden de las claves

3) Si el nodo hoja está lleno (número de claves es igual a “m-1”), se

procede a la división celular:

• Se crea un nuevo nodo, repartiéndose el contenido del nodo lleno entre los dos nodos, y la clave intermedia sube un nivel, es decir, se le añade una nueva entrada al padre

• Si cabe en el padre, ya está, si no se procederá a la división celular de éste

Borrado:

1) Búsqueda del nodo correspondiente.

2) a) La clave a suprimir es una hoja.

• Si tras la supresión de la clave correspondiente la hoja se queda con (m-1)/2 ó más claves no hay problemaSino, //nº claves < (m-1)/2

• Si una hoja vecina hija del mismo padre tiene más o igual de m/2 claves, éstas se reparten entre los dos: la clave intermedia entre los dos hijos para la hoja donde se ha hecho el borrado, y éste es sustituida por una etiqueta del otro nodo (u hoja).

Rotación: Sino, de la hoja de la cual se ha hecho el borrado, de una vecina, y de la clave del padre que las separaba antes de la supresión, se hace una sóla.

Combinación: Si el padre se queda con menos de m/2 hijos (m/2 - 1 claves), se fusiona con otro hermano de la misma manera, y así sucesivamente.

Árbol B*

Una variante del árbol B es el árbol B*, cuya peculiaridad consiste en que se aumenta el número mínimo de valores de clave que puede contener un nodo que no sea la raíz, de forma que en lugar de garantizar un 50% de utilización de espacio como en el árbol B, se aproveche como mínimo las dos terceras partes del mismo. Se puede definir a un árbol B* de orden m como sigue:

1. Cada nodo, excepto la raíz, tiene como máximo m hijos.

2. Cada nodo, excepto la raíz tiene como mínimo [2m-1]/3.

3. Todas las hojas están en el mismo nivel.

4. Un nodo con q hijos, contiene q-1 valores de clave.

5. La raiz puede tener

...