Arboles Binarios

Arboles Multicaminos

Puntos del Programa Relacionados
1. Investigación
2. Documentación
3. Presentación

Justificación:
Después de estudiados los temas a desarrollar nos pareció importante consolidar en un documento todo lo correspondiente a la documentación a desarrollar, ya que el mismo contendrá información importante para el conocimiento de los arboles multicaminos y suaplicación.

Objetivos de Aprendizaje

* El propósito principal es elaborar un documento que sustente la información general de los arboles multicaminos como conocimientos generales.

* El propósito de la documentación es el conocimiento de los diferentes tipos de arboles que se pueden manejar y su aplicación en la vida real.

* Teniendo claro cual es la utilización evaluar en quetipos de problemas pueden ser aplicados y de que forma.

Índice
Introducción 1
I. Capitulo Teórico 2
1. Arboles Multicaminos B 2
2. Arboles Multicaminos B+ 3
3. Arboles Multicaminos B* 5
II. Capitulo Practico 6
1. Ejemplos de Arboles Multicaminos B 6
2. Ejemplos de Arboles Multicaminos B+ 9
3. Ejemplos de Arboles Multicaminos B* 11
Bibliografía 15


Introducción

El trabajo que sepresentará a continuación, fue desarrollado en base a la elaboración de una documentación la cual tiene como objetivo el conocimiento y la aplicación de los arboles multicaminos, la documentación fue elaborada e3n base a investigaciones por parte de los integrantes del grupo.

I. Capitulo Teórico

Se define como árbol multicamino aquel árbol cuyo grado es mayor que 2. Los árbolesmulticamino también son llamados n-arios, siendo n el grado máximo de nodos del árbol. Por ejemplo para un grado 3 se llamará 3-ario o terciario; para un grado 4 se llamará 4-ario o cuaternario, etc...

1. Arboles Multicaminos B

Todas las páginas excepto la raíz contienen n nodos, siendo n una constante llamada orden. La raíz debe tener al menos dos hijos de lo contrario es un nodo hoja. Cadanodo tiene como máximo n hijos. Siempre está ordenado y balanceado por lo tanto los nodos hoja siempre están al mismo nivel.

Estructura de los nodos: Se ha encontrado la sugerencia de tratar al árbol B como un arreglo de nodos (como se ve en la siguiente imagen)

Inserción de elementos:
Para la inserción en importante saber que todas las hojas están al mismo nivel, por eso es que cualquiercamino desde la raíz hasta alguna hoja tiene la misma longitud, por otro lado, la forma de crecer de estos árboles es de abajo hacia arriba, para la inserción hemos encontrado los siguientes pasos:

1. Localizar la página donde corresponde, esto es por el valor, para no alterar el orden; insertar clave.

2. Si el número de elementos de la página anterior es menor a 2d (m<2d, la letra drepresenta el grado y la m representa el número de elementos por página),

3. La inserción se realiza en el lugar que le corresponde. De lo contrario, si el número de paginas es igual a 2d la página afectada se divide en 2 y se distribuyen los m+1 elementos de la página, equitativamente entre ellas. El elemento del medio se sube a la página antecesora.

2. Arboles Multicaminos B+
Los arbolesB+ son una variante de los arboles B, se diferencian  en que los arboles B+ toda la información se encuentra almacenada en las hojas. En la raíz y en las páginas internas se encuentran almacenado índices o claves para llegar a un dato.
 
Principales características de los arboles B+ de orden m son:

-La raíz almacena como mínimo un dato y como máximo m-1 datos.
-La pagina raíz tiene comomínimo dos descendientes.
-Las paginas intermedias tienen como mínimo (m-1)/2(Parte entera) datos.
-Las páginas intermedias tienen como máximo m-1 datos.
-Todas las paginas hojas tienen la misma altura
-La información se encuentra ordenada.
-Toda la información se encuentra almacenada en  las páginas hoja, por lo que en las páginas internas se puede duplicar las claves.
 

Ejemplo de un...