Diseño de un array bidimensional dinámico implementado mediante listas enlazadas y árboles AVL

Resumen

Un array o matriz bidimensional tradicional es una estructura utilizada para el almacenamiento de informacion homogenea dispuesta en forma tabular, que garantiza el acceso inmediato a cada elemento de la misma en base a dos indices que referencian su posicion, esta estructura presenta los problemas siguientes: su naturaleza estatica exige prefijar su dimensionamiento previamente a la incorporacion de los elementos; la definicion de las series de indices tiene restricciones que derivan en la infrautilizacion del espacio; se producen anomalias por accesos incorrectos con indices fuera de su rango; y el desperdicio de espacio en memoria originado, para matrices con un bajo porcentaje de ocupacion, junto con tiempos de respuesta elevados en procesos de recorrido. En este trabajo de investigacion se ha diseñado una nueva estructura: el array bidimensional dinamico (abd), que es un tipo abstracto de datos construido en base a punteros, lo que determina su caracter versatil. Esta estructura supera todos los inconvenientes del array estatico, permitiendo ademas su reajuste dinamico en tiempo de ejecucion en funcion de las actualizaciones de sus componentes. El mayor rendimiento se obtiene en matrices poco densas debido a la reduccion en el espacio de almacenamiento y en el tiempo de ejecucion de los procesos, al no existir posiciones reservadas inutilizadas. En primer lugar, se ha implementado el abd en base a listas enlazadas ortogonales, constituyendo una red de listas dobles con insercion al final entrelazadas para representar los elementos y listas simples para los indices. En las listas, la busqueda de un componente presenta un orden o(n), lo que significa que el tiempo es proporcional al numero de elementos procesados. Los tratamientos de busqueda intervienen en bastantes operaciones de manejo de la estructura, por lo que para mejorar su rendimiento se ha diseñado una segunda implementacion del abd utilizando arboles binarios de b