004 - Árboles: Lista de adyacencia vs. Conjuntos anidados

Comparación empírica de los modelos de árbol implementados mediante una lista de adyacencia y mediante conjuntos anidados.
La implementación mediante una lista de adyacencia consiste en indicar en cada elemento cuál es el padre.
Por otro lado, los conjuntos anidados se basan en rangos disjuntos de números enteros, es decir, cada nodo padre contiene el rango de números entre los que se encuentran los hijos, nietos, etc.

La lista de adyacencia necesita un gran número de consultas para reconstruir el árbol, mientras que los conjuntos anidados sólo necesitan una. En cuanto a la velocidad, la lista de adyacencia es mucho más rápida que los conjuntos anidados (especialmente en inserción).

Si queremos combinar un número mínimo de consultas con la máxima velocidad, la combinación perfecta es una lista de adyacencia con caché y una gran cantidad de lógica. Además, se puede añadir a cada nodo una tabla hash con referencias inversas a los hijos para incrementar la velocidad. Esta posibilidad se tratará en profundidad en 005.

Cada uno de los métodos tiene implementadas las siguientes funcionalidades:

• Crear la tabla vacía en la base de datos
• Insertar elementos
• Ver una salida en modo texto

Las siguientes figuras ilustran el modelo de listas de adyacencia y conjuntos anidados respectivamente.

El rendimiento en escritura del método de conjuntos anidados (nest) tiene complejidad exponencial respecto al número de elementos (adli). La gráfica muestra que el rendimiento del modelo de la lista de adyacencia es muchísimo más rápido.

Sin embargo, en lectura es ligeramente más rápido el método de los conjuntos anidados.