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

Te encuentras en la cuarta 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

Desarrollar primero las pruebas a lo largo de este proyecto nos ha ayudado a realizar la implementación y las mejoras a la misma de una forma mas ágil y confiable. A lo largo del desarrollo hemos podido verificar si ha ocurrido una regresión y con ello reparar errores rápidamente. Una regresión ocurre cuando algo que ya funcionaba deja de funcionar.

Una vez que empiezas a desarrollar bajo este tipo de paradigma los beneficios son inmediatos. En este proyecto que consta de seis clases y una lógica moderada, el crear primero las pruebas nos ha ayudado a entender mejor qué es lo que se tiene que implementar y durante la implementación nos ha permitido determinar cuando el código ha alcanzado un punto estable. Imagina lo importante que es el desarrollo de pruebas si empresas como Amazon, Google, Microsoft, entre otras, tienen puestos enfocados a esta tarea.

La implementación de la clase Red-Black Tree no fue la excepción en nuestra estrategia de desarrollo: 1) creación de pruebas; 2) implementación de la funcionalidad; 3) Refactoring en caso de ser necesario. Sin embargo, realizamos una ligera variación. Debido a que la lógica para árboles Red-Black es un poco más elaborada, fuimos creando una parte de prueba y luego una parte de código, ¿por qué? Al crear un poco de las pruebas aclarábamos partes de la implementación que no eran tan obvias, y decidimos aprovechar ese conocimiento mientras estaba fresco para escribir la parte del código que correspondía. Y nuevamente repetíamos el ciclo un poco de pruebas y poco de implementación.

Antes de cerrar esta serie, revisemos brevemente la diferencia entre un árbol binario simple, uno AVL y un Red-Black. En un árbol binario simple los valores se insertan directamente donde les toca y eso es todo. El problema con ello es que puede crear árboles "desbalanceados". Supongamos que insertamos los números del 1 al 15 en orden, esto resulta en un árbol como el que se muestra en la siguiente figura:

¿Qué pasa si queremos buscar el número 15 en este árbol? Tenemos que realizar 15 comparaciones (en otras palabras, el número de nodos desde la raíz hasta el nodo que contiene el número 15). La eficiencia de las operaciones en árboles binarios está relacionada directamente con la altura del árbol. Para ello, los árboles AVL y Red-Black implementan lógica que detecta cuando un árbol empieza a desbalancearse y lo corrigen rotando nodos del árbol. La siguiente figura ilustra el concepto básico de rotación:

La siguiente imagen muestra el árbol AVL resultante al insertar en orden los números del 1 al 15. Podemos observar que si queremos buscar el número 15, sólo nos toma 4 comparaciones. Además es claro que el árbol está perfectamente balanceado, ya que todos los nodos hoja se encuentran a la misma altura.

Obviamente todo tiene un precio, entre más balanceado se quiera un árbol mayor número de rotaciones se necesitan, y por ende mayor trabajo. Aquí es donde entran los árboles Red-Black, cuyo objetivo es ofrecer un equilibrio entre el balance del árbol y el trabajo requerido (es decir, el número de rotaciones realizadas). Veamos como luce el árbol Red-Black para el ejemplo que estamos manejando.

En este árbol Red-Black, nos toma 6 comparaciones encontrar el número 15. Podemos observar que este árbol es ligeramente más alto que el árbol AVL y con ello un poco más desbalanceado. Sin embargo, requirió un menor número de rotaciones. En general, los árboles Red-Black son más eficientes en la inserción y borrado de nodos que un árbol AVL, sin sacrificar considerablemente el balanceo del árbol.

Muy bien, con esto cerramos esta serie. Hay otros aspectos relacionados a pruebas que trataremos en otros posts. Por ejemplo, cómo determinamos si nuestras pruebas son representativas para garantizar que la implementación funciona correctamente. Además, para todas las pruebas generamos los datos de entrada y calculamos la salida manualmente, ¿podemos hacerlo de otra forma?

Por último los dejamos con una liga al código (tanto pruebas como implementación, lo pueden abrir directamente con NetBeans), el código está en bitbucket y en la parte superior derecha existe una opción para descargarlo en formato zip. Para aprender más de bitbucket puedes visitar el siguiente post.

Y no lo olvides, desarrollo de pruebas primero y después implementación.