Árbol multicamino

Árbol multicamino

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

Contenido

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
Enlacei, son los enlaces a los subárboles de A, pudiendo ser: 0 <= i <= nClaves
Clavei, son los valores de clave, pudiendo ser: 1 <= 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.


Ventajas e inconvenientes

La principal ventaja de este tipo de árboles consiste en que existen más nodos en un mismo nivel que en los árboles binarios con lo que se consigue que, si el árbol es de búsqueda, los accesos a los nodos sean más rápidos.

El inconveniente más importante que tienen es la mayor ocupación de memoria, pudiendo ocurrir que en ocasiones la mayoría de los nodos no tengan descendientes o al menos no todos los que podrían tener desaprovechándose por tanto gran cantidad de memoria. Cuando esto ocurre lo más frecuente es transformar el árbol multicamino en su binario de búsqueda equivalente.

Nota

Un tipo especial de árboles multicamino utilizado para solucionar el problema de la ocupación de memoria son los árboles B.

Véase también


Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Árbol multicamino — Los árboles multicamino o árboles multirrama son estructuras de datos de tipo árbol usadas en computación …   Enciclopedia Universal

  • Árbol (informática) — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

  • Árbol 2-3 — Este artículo o sección sobre informática necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 2 de febrero de 2009. También puedes… …   Wikipedia Español

  • Estructura de datos — En programación, una estructura de datos es una forma de organizar un conjunto de datos elementales con el objetivo de facilitar su manipulación. Un dato elemental es la mínima información que se tiene en un sistema. Una estructura de datos… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”