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,

...