Desarrollo de Software dirigido por Pruebas: árboles binarios (Parte 1)

Te encuentras en la primera parte de la serie "Desarrollo de Software dirigido por Pruebas":

1. Diseño de las pruebas
2. Implementación
3. Refactoring
4. Conclusiones y código

El Desarrollo de Software dirigido por Pruebas (Test Driven Development, en inglés) es una técnica que se basa en la elaboración de pruebas para el software previas a la implementación del código. Puede parecer extraño, ya que normalmente estamos acostumbrados a implementar un código y después probar que funcione. Sin embargo, esto tiene sentido ya que antes de la implementación, ya conocemos el funcionamiento del programa y podemos estar seguros de cuál o cuáles son los resultados esperados a la hora de correr dicho programa.

El desarrollo de las pruebas antes del desarrollo del software es muy útil para comprender a profundidad la funcionalidad y el comportamiento del mismo. Realizar test cases utilizando JUnit es muy conveniente ya que a la hora de probar la aplicación, se puede estar seguro de que cumple con el objetivo establecido desde un principio si pasa todas las pruebas y además, es posible realizar cambios con mayor seguridad ya que al correr nuevamente las pruebas, si éstas fallan, se puede tener una muy buena idea de dónde está el error para corregirlo rápidamente. Una vez que las pruebas han pasado satisfactoriamente, aún con la implementación de cambios, es muy probable que dicha aplicación esté desarrollada correctamente. Además, si se desarrollan pruebas de forma creativa, tal y como se explica en el post Prueba Unitaria (Unit Testing) con Netbeans, es muy posible que se estén cubriendo escenarios que quizá no se consideren al realizar las pruebas manualmente.

En esta ocasión, voy a ilustrar el proceso de desarrollo dirigido por pruebas utilizando un conjunto de clases que servirán para implementar árboles binarios. Dos de las operaciones básicas para un árbol binario son la inserción y el borrado de nodos. En esta serie, utilicé valores enteros como el tipo de dato que almacenan los árboles, pero esta información puede ser de cualquier otro tipo.

En este punto, aún no he implementado los cuerpos de los métodos, solamente he creado los esqueletos de las clases, ya que comenzaré por implementar las pruebas. Por ejemplo, para probar el método de inserción (al que llamé insertion), utilizaré los tres recorridos por profundidad de un árbol básicos: recorrido preorden, recorrido inorden y recorrido postorden. Realizaré tres pruebas dentro de las cuales insertaré valores de manera que las estructuras de los árboles sean lo más distintas posibles. Una vez instanciado un objeto árbol, "insertaré" (es decir, haré varias llamadas al método de inserción) ciertos valores, llamaré a los métodos que realizan los recorridos y que devuelven un arreglo con los resultados y los compararé con otro arreglo que contiene esos mismos valores pero que yo ordené de acuerdo con lo que espero obtener de cada recorrido. Un primer caso de prueba para la inserción podría ser insertar los siguientes valores: 10, 6, 7, 5, 4, 11, 13, 12, 15, 3. El árbol binario que se obtiene como resultado es el siguiente:

De acuerdo con esta información, la implementación de esta primera prueba luciría de la siguiente manera:

@Test
    public void insertion01() {
        //Crea una instancia de tipo SimpleBinaryTree para el test
        SimpleBinaryTree simpleTree = new SimpleBinaryTree();

        //Verificar que el arbol esta vacio al inicio
        assertTrue(simpleTree.isEmpty());

        //Insertar elementos al arbol
        simpleTree.insertion(10);
        simpleTree.insertion(6);
        simpleTree.insertion(7);
        simpleTree.insertion(5);
        simpleTree.insertion(4);
        simpleTree.insertion(11);
        simpleTree.insertion(13);
        simpleTree.insertion(12);
        simpleTree.insertion(15);
        simpleTree.insertion(3);

        //Corroborar que todos los datos se hayan insertado
        assertArrayEquals(simpleTree.preOrder(),
                     new int[]{10, 6, 5, 4, 3, 7, 11, 13, 12, 15});
        assertArrayEquals(simpleTree.inOrder(),
                     new int[]{3, 4, 5, 6, 7, 10, 11, 12, 13, 15});
        assertArrayEquals(simpleTree.postOrder(),
                     new int[]{3, 4, 5, 7, 6, 12, 15, 13, 11, 10});
    }

El método de borrado (al que llamé deletion)  se probará de manera muy similar: primero se "insertarán" algunos valores, después se hará una llamada al método de borrado y finalmente se comparará el resultado obtenido de los recorridos contra arreglos que contienen los valores esperados.

El proyecto que estoy utilizando para demostrar el desarrollo de software dirigido por pruebas consta de cinco clases: BinaryTree, TreeNode, SimpleBinaryTree, AVLTree y RedBlackTree. Esta estructura y los resultados de las pruebas se discutirán con mayor detalle en el siguiente post.