Arboles Tipo B

ARBOLES TIPO-B
Árboles Tipo-B:
Los árboles tipo-B son árboles cuyos nodos pueden tener un número multiple de hijos.
Cada página en un árbol-B de orden d contiene:
- 2d claves como máximo y
- dclaves como mínimo.
Cada página de un árbol-B de orden d contiene:
- 2d+1 hijos como máximo y
- d+1 hijos como mínimo.
Excepto la raíz que puede tener como mínimo 1 clave y por consiguientesolamente 2 hijos

Un árbol B de orden d cumple con las siguientes propiedades:
1. Un parámetro muy importante en los árboles B es el orden(d), el orden de un árbol es el número máximo de ramas quepueden partir de un nodo.
2. El árbol está ordenado.
3. Todos los nodos terminales (nodos hojas), están en el mismo nivel.
4. Cada página, excepto la raíz, contiene entre d y 2d elementos (recuerde qued representa el grado del árbol).
5. Cada página, excepto la página raíz y las páginas hojas, tiene entre d+1 y 2d+1 descendientes. Se utilizara m para expresar el número de elementos por página.6. La página raíz tiene al menos dos descendientes.
7. Todas las hojas están en el mismo nivel.

Ejemplo de un árbol tipo-B de orden 2


Búsqueda en Árboles-B:

Localizar una clave en unárbol-b es una operación simple pues consiste en situarse en el nodo raíz del árbol, si la clave se encuentra ahí hemos terminado y si no es así seleccionamos de entre los hijos el que se encuentra entredos valores de clave que son menor y mayor que la buscada respectivamente y repetimos el proceso hasta que la encontremos. En caso de que se llegue a una hoja y no podamos proseguir la búsqueda laclave no se encuentra en el árbol.
Inserción en Árboles-B:

Primero debe localizarse la página donde corresponde insertar la clave. Si el número de elementos de la página es menor a 2d (m= d{verificamos m}

Entonces
Termina la operación de borrado.

Si no
Debe bajarse la clave lexicográficamente adyacente de la página antecedente y sustituir esta clave por la que se encuentra más a la...