Arboles B

ARBOLES B:
DEFINICION:
La idea tras los árboles-B es que los nodos internos deben tener un número variable de nodos hijo dentro de un rango predefinido. Cuando se inserta o se elimina un dato dela estructura, la cantidad de nodos hijo varía dentro de un nodo. Para que siga manteniéndose el número de nodos dentro del rango predefinido, los nodos internos se juntan o se parten. Dado que sepermite un rango variable de nodos hijo, los árboles-B no necesitan re-balancearse tan frecuentemente como los árboles binarios de búsqueda auto-balanceables. Pero, por otro lado, pueden desperdiciarmemoria, porque los nodos no permanecen totalmente ocupados. Los límites (uno superior y otro inferior) en el número de nodos hijo son definidos para cada implementación en particular. Por ejemplo, en unárbol-B 2-3 (A menudo simplemente llamado árbol 2-3 ), nodo sólo puede tener 2 ó 3 nodos hijo. Un árbol-B se mantiene balanceado porque requiere que todos los nodos hoja se encuentren a la mismaaltura.

PROPIEDADES:
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árbol-B de orden M (el máximo número de hijos que puede tener cada nodo) es un árbol que satisface las siguientes propiedades:
1. Cada nodo tiene como máximo M hijos.
2. Cada nodo (excepto raíz) tienecomo mínimo (M-1)/2 claves.
3. La raíz tiene al menos 2 hijos si no es un nodo hoja. (según M)
4. Todos los nodos hoja aparecen al mismo nivel.
5. Un nodo no hoja con k hijos contiene k-1 elementosalmacenados.
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 quer2, etc.
3. El último hijo tiene valor mayor que rm.
4.
ALTURA (MEJOR Y PEOR CASO):
En el mejor de los casos, la altura de un árbol-B es: logMn
En el peor de los casos, la altura de un...