Graficar árboles AVL con Graphviz y Java

En este tutorial se desarrolla un ejemplo sencillo en el que se grafica un árbol AVL con ayuda de la herramienta Graphviz. Es importante mencionar que para que ejemplo funcione correctamente debe estar instalado Graphviz. Este proyecto se desarrolló utilizando Ubuntu 14.04 y Netbeans 8.0. El proyecto completo del ejemplo puede descargarse del siguiente enlace:

Graficar árboles AVL con Graphviz y Java.

Todo el código dentro del proyecto está documentado con comentarios que contienen explicaciones sobre su funcionamiento.

Instalación de Graphviz

Lo primero que haremos será instalar Graphviz, en caso de que no lo hayamos instalado todavía, para ello abrimos una terminal, en Ubuntu puede hacerse con la combinación de teclas Ctrl+Alt+t o en Aplicaciones → Accesorios → Terminal, una vez abierta la terminal ingresamos el comando “sudo apt-get install graphviz”, autenticamos ingresando nuestra contraseña y aceptamos la descarga e instalación, con esto quedará instalado Graphviz. 

Funcionamiento del proyecto

El proyecto cuenta con la clase ArbolAVL, en el método principal de la aplicación, se instancian dos objetos de esta clase, es decir, dos árboles AVL, el primero almacena únicamente texto y el segundo únicamente números. El código de la clase principal de la aplicación es el siguiente:

/*
 * Ejemplo desarrollado por Erick Navarro
 * Blog: e-navarro.blogspot.com
 * Octubre - 2015
 */

package avlgraphviz;

import avl.ArbolAVL;

/**
 * Clase principal de la aplicación.
 * @author Erick Navarro
 */
public class AVLGraphviz {

    /**
     * Método principal de la aplicación
     * @param args los argumentos de la línea de comando.
     */
    public static void main(String[] args) {
        //Creamos un árbol cuyos nodos contendrán solamente texto
        ArbolAVL arbol_texto=new ArbolAVL();
        //Llenamos con información el árbol
        arbol_texto.insertar("Juan");
        arbol_texto.insertar("Pedro");
        arbol_texto.insertar("María");
        arbol_texto.insertar("Roberto");
        arbol_texto.insertar("Teodoro");
        arbol_texto.insertar("Manuel");
        arbol_texto.insertar("Diego");
        arbol_texto.insertar("Alejandro");
        arbol_texto.insertar("Margarita");
        arbol_texto.insertar("Luis");
        arbol_texto.insertar("Hernán");
        arbol_texto.insertar("Jaime");
        arbol_texto.insertar("Ana");
        arbol_texto.insertar("Francisco");
        arbol_texto.insertar("Andrea");
        //Graficamos el árbol generando la imagen arbol_texto.jpg
        arbol_texto.graficar("arbol_texto.jpg");
        //Imprimimos el contenido del árbol ordenado
        arbol_texto.inorden();
        
        System.out.println();
        //Creamos un árbol cuyos nodos contendrán solamente numeros
        ArbolAVL arbol_numeros=new ArbolAVL();
        //Llenamos con información el árbol
        arbol_numeros.insertar(12);
        arbol_numeros.insertar(5);
        arbol_numeros.insertar(26);
        arbol_numeros.insertar(33);
        arbol_numeros.insertar(59);
        arbol_numeros.insertar(27);
        arbol_numeros.insertar(15);      
        arbol_numeros.insertar(47);
        arbol_numeros.insertar(74);
        arbol_numeros.insertar(84);
        arbol_numeros.insertar(88);
        arbol_numeros.insertar(90);
        arbol_numeros.insertar(124);
        arbol_numeros.insertar(612);
        //Graficamos el árbol generando la imagen arbol_numeros.jpg
        arbol_numeros.graficar("arbol_numeros.jpg");
        //Imprimimos el contenido del árbol ordenado
        arbol_numeros.inorden();
    }   
}

Al ser ejecutada la aplicación, se generan dos imagenes, una para cada árbol la primera arbol_texto.jpg corresponde al árbol que solo almacena texto en sus nodos.

La segunda arbol_numeros.jpg corresponde al árbol que solo almacena números.

En la consola se verán los elementos de ambos árboles impresos en orden, esto se logra haciendo un recorrido enorden de los arboles AVL.

Árbol AVL

El árbol AVL es un árbol binario de búsqueda equilibrado. Recibió el nombre del árbol AVL en honor de Adelson, Velskii y Landis, que fueron los primeros científicos en estudiar esta estructura de datos.

“Un árbol AVL es un árbol binario de búsqueda en el que las alturas de los subárboles izquierdo y derecho de cualquier nodo difieren como máximo en 1.”

Fuente: Algoritmos y estructuras de datos, una perspectiva en C. Luis Joyanes Aguilar, Ignacio Zahonero Martínez.

En este árbol únicamente se desarrolla el método para insertar nodos, porque el objetivo de la aplicación es únicamente graficar el árbol, adicionalmente, podrían desarrollarse métodos para eliminar nodos, buscar nodos, vaciar el árbol, calcular la profundidad del árbol, etc. El único recorrido que se hace del árbol es el enorden, que muestra los nodos del árbol ordenados, pero existen otros recorridos que también podrían implementarse como el recorrido preorden, postorden o el recorrido por anchura.

Interfaz Comparable: El secreto tras la flexibilidad de este árbol

La razón por la cual este árbol puede utilizarse para almacenar cadenas o bien para almacenar números es la interfaz Comparable. Lo que almacena el nodo es la instancia de una clase que implementa la interfaz Comparable, por supuesto que todos los nodos tienen que poder compararse satisfactoriamente, por ejemplo no se podrían almacenar números enteros y también cadenas de caracteres en un mismo árbol, ya que no podrían comparase satisfactoriamente porque se daría un problema de tipos. Pero si todos los nodos almacenan números, el árbol funciona sin problemas, al igual cuando todos los nodos almacenan cadenas.
Si deseáramos almacenar otro tipo de información podríamos programar una clase que contenga los atributos que deseamos y que implemente la interfaz Comparable, entonces sin modificar el árbol podríamos almacenar esta información.

Fuentes consultadas

Algoritmos y estructuras de datos, una perspectiva en C. Luis Joyanes Aguilar, Ignacio Zahonero Martínez.