Los árboles se
clasifican de la siguiente manera:
-
Árboles
binarios.
o
Distintos
o
Similares
o
Equivalentes
o
Equilibrado
o
Completo
-
Árboles
Multicaminos.
o
B
o
B+
o
B*
o
R
o
2-4
Un árbol binario sería un conjunto de 0 o más nodos
en el cual existe
un nodo raíz y cada uno de los nodos, incluido el r
aíz podrán tener 0, 1
o dos subárboles:
) Subárbol izquierdo y subárbol derecho.
) Cada nodo es como máximo de grado 2.
un árbol binario es una estructura de datos
en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho.
No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún
hijo tiene como referencia a null, es decir que no almacena
ningún dato, entonces este es llamado un nodo externo. En el caso
contrario el hijo es llamado un nodo interno. Usos comunes de los
árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.
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:
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.
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.
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.
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.
Autor del video: KARLA GARCIA (youtube)
No hay comentarios:
Publicar un comentario