Árbol multicamino

Los árboles multicamino o árboles multirrama son estructuras de datos de tipo árbol usadas en computación.

Definición

Un árbol multicamino posee un grado g mayor a dos, donde cada nodo de información del árbol tiene un máximo de g hijos.


Sea un árbol de m-caminos A, es un árbol m-caminos si y solo si:

  • A está vacío
  • Cada nodo de A muestra la siguiente estructura: [nClaves,Enlace0,Clave1,...,ClavenClaves,EnlacenClaves]
nClaves es el número de valores de clave de un nodo, pudiendo ser: 0 <= nClaves <= g-1
Clavei, son los valores de clave, pudiendo ser: 1 <= i <= nClaves
Enlacei, son los enlaces a los subárboles de A, pudiendo ser: 0 <= i <= nClaves
  • Clavei < Clavei+1
  • Cada valor de clave en el subárbol Enlacei es menor que el valor de Clavei+1
  • Los subárboles Enlacei, donde 0 <= i <= nClaves, son también árboles m-caminos.


Existen muchas aplicaciones en las que el volumen de la información es tal, que los datos no caben en la memoria principal y es necesario almacenarlos, organizados en archivos, en dispositivos de almacenaminento secundario. Esta organización de archivos debe ser suficientemente adecuada como para recuperar los datos del mismo en forma eficiente.


Other Languages