Estructura de datos avanzadas : clases disjuntas, montículos, árboles de búsqueda

Abstract

En aquest treball s'amplia la implementació en Java de les estructures de dades iniciada per Esteve Mariné, utilitzant el seu disseny bàsic. Concretament, s'ha fet la programació de les estructures de a) classes disjuntes, utilitzant els algorismes de llistes encadenades i amb estructura d'arbre, b) monticles, amb els algorismes binari, binomial i de Fibonacci, i c) arbres de recerca basats en l'algorisme d'arbre binari vermell-negre, el qual complementa els dos ja existents amb algorismes d'encadenaments i AVL. Per a examinar l'evolució de les estructures, s'ha preparat un visualitzador gràfic interactiu amb l'usuari que permet fer les operacions bàsiques de l'estructura. Amb aquest entorn és possible desar les estructures, tornar a reproduir-les i desfer i tornar a repetir les operacions fetes sobre l'estructura. Finalment, aporta una metodologia, amb visualització mitjançant gràfics, de l'avaluació comparativa dels algorismes implementats, que permet modificar els paràmetres d'avaluació com ara nombre d'elements que s'han de tractar, algorismes que s'han de comparar i nombre de repeticions. Les dades obtingudes es poden exportar per a analitzar-les posteriorment.

En este trabajo se amplía la implementación en Java de las estructuras de datos iniciada por Esteve Mariné, utilizando su diseño básico. Concretamente, se ha realizado la programación de las estructuras de a) clases disjuntas, utilizando los algoritmos de listas encadenadas y con estructura de árbol, b) montículos, con los algoritmos binario, binomial y de Fibonacci, y c) árboles de búsqueda basados en el algoritmo de árbol binario rojo-negro, el cual complementa los dos ya existentes con algoritmos de encadenamientos y AVL. Para examinar la evolución de las estructuras, se ha preparado un visualizador gráfico interactivo con el usuario que permite realizar las operaciones básicas de la estructura. Con este entorno es posible grabar las estructuras y volver a reproducirlas, así como deshacer y volver a repetir las operaciones realizadas sobre la estructura. Finalmente, se aporta una metodología, con visualización mediante gráficos, de la evaluación comparativa de los algoritmos implementados, que permite modificar los parámetros de evaluación tales como número de elementos a tratar, algoritmos a comparar y número de repeticiones. Los datos obtenidos se pueden exportar para analizarlos posteriormente.

The implementation in Java of the data structures begun by Esteve Mariné is expanded in this work, which uses his basic design. In concrete terms, the programming has been done for the structures of a) disjointed classes, using the algorithms of chained lists, and with the tree structure; b) stacks, with binary, binomial, and Fibonacci algorithms; and c) research trees based on the red-black binary tree algorithm, which complements the two already-existing ones with algorithms of chains and AVL. To examine the evolution of the structures, a user-interactive graphic visualizer has been prepared that allows the basic operations of the structure to be performed. With this environment it is possible to save the structures, produce them anew, undo them, and repeat the operations performed on the structure. Finally, it provides a methodology, with visualization by means of graphics, for the comparative evaluation of the implemented algorithms, which allows modification of the parameters of evaluation, such as the number of elements that must be dealt with, algorithms that have to be compared, and the number of repetitions. The data obtained can be exported for subsequent analysis.