ARBOLES B

Definición breve [editar]

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, tal como muestra el dibujo .

Un arbol-B de orden M (el máximo número de hijos que puede tener cada nodo) es un arbol que satisface las siguientes propiedades:

1. Cada nodo tiene como máximo M hijos.

2. Cada nodo (excepto raiz y hojas) tiene como mínimo M/2 hijos.

3. La raiz tiene al menos 2 hijos si no es un nodo hoja.

4. Todos los nodos hoja aparecen al mismo nivel.

5. Un nodo no hoja con k hijos contiene k-1 elementos almacenados.

6. Los hijos que cuelgan de la raíz (r1, • • • rm) tienen que cumplir ciertas condiciones :

1. El primero tiene valor menor que r1.

2. El segundo tiene valor mayor que r1 y menor que r2 etc.

3. El último hijo tiene mayor que rm .

Altura: El mejor y el peor caso [editar]

En el mejor de los casos,la altura de un arbol-B es:

logMn

En el peor de los casos,la altura de un arbol-B es:

Donde M es el número máximo de hijos que puede tener un nodo.

Estructura de los nodos [editar]

Cada elemento de un nodo interno actúa como un valor separador, que lo divide en subárboles. Por ejemplo, si un nodo interno tiene tres nodos hijo, debe tener dos valores separadores o elementos a1 y a2. Todos los valores del subárbol izquierdo deben ser menores a a1, todos los valores del subárbol del centro deben estar entre a1 y a2, y todos los valores del subárbol derecho deben ser mayores a a2.

Los nodos internos de un árbol B, es decir los nodos que no son hoja, usualmente se representan como un conjunto ordenado de elementos y punteros a los hijos. Cada nodo interno contiene un máximo de U hijos y, con excepción del nodo raíz, un mínimo de L hijos. Para todos los nodos internos exceptuando la raíz, el número de elementos es uno menos que el número de punteros a nodos. El número de elementos se encuentra entre L-1 y U-1. El número U debe ser 2L o 2L-1, es decir, cada nodo interno está por lo menos a medio llenar. Esta relación entre U y L implica que dos nodos que están a medio llenar pueden juntarse para formar un nodo legal, y un nodo lleno puede dividirse en dos nodos legales (si es que hay lugar para subir un elemento al nodo padre). Estas propiedades hacen posible que el árbol B se ajuste para preservar sus propiedades ante la inserción y eliminación de elementos.

Los nodos hoja tienen la misma restricción sobre el número de elementos, pero no tienen hijos, y por tanto carecen de punteros.

El nodo raíz tiene límite superior de número de hijos, pero no tiene límite inferior. Por ejemplo, si hubiera menos de L-1 elementos en todo el árbol, la raíz sería el único nodo del árbol, y no tendría hijos.

Un árbol B de altura n+1 puede contener U veces por elementos más que un árbol B de profundidad n, pero el costo en la búsqueda, inserción y eliminación crece con la altura del árbol. Como todo árbol balanceado, el crecimiento del costo es más lento que el del número de elementos.

Algunos árboles balanceados guardan valores sólo en los nodos hoja, y por lo tanto sus nodos internos y nodos hoja son de diferente tipo. Los árboles B guardan valores en cada nodo, y pueden utilizar la misma estructura para todos los nodos. Sin embargo, como los nodos hoja no tienen hijos, una estructura especial para éstos mejora el funcionamiento.

class nodo árbol B en c++ [editar]

#include <iostream.h>

#include <stdlib.h>

#define TAMANO 1000

struct stclave {

int valor;

long registro;

};

class bnodo {

public:

bnodo (int nClaves); // Constructor

~bnodo (); // Destructor

private:

int clavesUsadas; // Claves usadas en el nodo

stclave *clave; // Matriz de claves del nodo

bnodo **puntero; // Matriz de punteros a bnodo

bnodo *padre; // Puntero al nodo padre

friend class btree;

};

Algoritmos [editar]

Búsqueda [editar]

La búsqueda es similar a la de los árboles binarios. Se empieza en la raíz, y se recorre el árbol hacia abajo, escogiendo el sub-nodo de acuerdo a la posición relativa del valor buscado respecto a los valores de cada nodo. Típicamente se utiliza la búsqueda binaria para determinar esta posición relativa.

Procedimiento [editar]

ejemplo2 inserción en árbol B

1. . Situarse en el nodo raíz.

2. (*). Comprobar si contiene la clave a buscar.

1. . Encontrada fin de procedimiento .

2. . No encontrada:

1. Si es hoja no existe la clave.

2. En otro caso el nodo actual es el hijo que corresponde:

1. . La clave a buscar k < k1 :hijo izquierdo.

2. . La clave a buscar k > ki y k < ki+1 hijo iesimo.

3. . Volver a paso 2(*).

Inserción [editar]

Todas las inserciones se hacen en los nodos hoja.

1. Realizando una búsqueda en el árbol, se halla el nodo hoja en el cual debería ubicarse el nuevo elemento.

2. 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.

3. De otra forma, el nodo debe ser dividido en dos nodos. La división se realiza de la siguiente manera:

1. Se escoge el valor medio entre los elementos del nodo y el nuevo elemento.

2. 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.

3. El valor separador se debe colocar en el nodo padre, lo que puede provocar que el padre sea dividido en dos, y así sucesivamente.

Si las divisiones de nodos suben hasta la raíz, se crea una nueva raíz con un único elemento como valor separador, y dos hijos. Es por esto por lo que la cota inferior del tamaño de los nodos no se aplica a la raíz. El máximo número de elementos por nodo es U-1. Así que debe ser posible dividir el número máximo de elementos U-1 en dos nodos legales. Si este número fuera impar, entonces U=2L, y cada uno de los nuevos nodos tendrían (U-2)/2 = L-1 elementos, y por lo tanto serían nodos legales. Si U-1 fuera par, U=2L-1, así que habría 2L-2 elementos en el nodo. La mitad de este número es L-1, que es el número mínimo de elementos permitidos por nodo.

Un algoritmo mejorado admite una sola

...