Atrapando y manejando excepciones.

   Esta entrada se basa en la descripción del siguiente ejemplo:

      // Note: This class will not compile yet.
      import java.io.*;
      import java.util.List;
      import java.util.ArrayList;

      public class ListOfNumbers {
          private List<Integer> list;
          private static final int SIZE = 10;

          public ListOfNumbers ( ) {
              list = new ArrayList<Integer>(SIZE);
              for (int i = 0; i < SIZE; i++) {
                   list.add(Integer.valueOf(i));
              }
          }

          public void writeList( ) {
// The FileWriter constructor throws IOException, which must be caught.
              PrintWriter out = new PrintWriter(new FileWriter("OutFile.txt"));

              for (int i = 0; i < SIZE; i++) {
               // The get(int) method throws IndexOutOfBoundsException, which must be caught.
                  out.println("Value at: " + i + " = " + list.get(i));
              }
              out.close();
          }
      }

   El ejemplo ha sido tomado y adaptado para cumplir con las nuevas especificaciones del API de The Java Tutorials (Catching and Handling Exceptions). Puede descargar la versión ListOfNumbers1, misma que no compila debido a que no realiza el adecuado manejo de las excepciones que podrían generarse, y la versión corregida ListOfNumbers, la cual contiene ya los elementos necesarios para el adecuado manejo de dichas excepciones.

    Recomiendo al lector remitirse en este momento al Ejercicio 3 de la entrada de Ejercicios selectos para comparar este ejemplo con una versión alternativa que compacta las cláusulas catch en una sola.

Ventajas de las excepciones.

   Pueden mencionarse esencialmente tres ventajas principales en el uso de excepciones (vea Advantages of Exceptions):

1. Separación del código "regular" del de manejo de errores.
2. Propagación de errores hacia la pila de métodos.
3. Agrupación y diferenciación de tipos de errores.

Separación del código "regular" del de manejo de errores.
   Las excepciones proporcionan un mecanismo para separar los detalles de la lógica principal del programa, respecto a lo que hay que hacer cuando ocurre algo fuera de lo ordinario.

   Considere el siguiente pseudocódigo para leer un archivo completo en la memoria:

          readFile {
              open the file;
              determine its size;
              allocate that much memory;
              read the file into memory;
              close the file;
          }

   El flujo principal parece bastante simple pero (las cosas a veces salen mal):

• ¿Qué pasa si el archivo no se puede abrir?
• ¿Qué pasa si su longitud no puede ser determinada?
• ¿Qué pasa si no se puede obtener memoria suficiente para contenerlo?
• ¿Qué pasa si falla su lectura?
• ¿Qué pasa si el archivo no se puede cerrar?

   Para manejar dichas situaciones, se debe introducir más código para la detección y manejo correspondiente utilizando técnicas tradicionales:

          errorCodeType readFile {
              initialize errorCode = 0;
    
              open the file;
              if (theFileIsOpen) {
                  determine the length of the file;
                  if (gotTheFileLength) {
                      allocate that much memory;
                      if (gotEnoughMemory) {
                          read the file into memory;
                          if (readFailed){
                              errorCode = -1;
                          }
                      } else
                          errorCode = -2;
                  } else
                      errorCode = -3;
                  close the file;
                  if (theFileDidntClose && errorCode == 0)
                      errorCode = -4;
                  else
                      errorCode = errorCode and -4;
              else
                  errorCode = -5;
              return errorCode;
          }

   Las excepciones no ahorran el trabajo del manejo de errores, pero permiten mantener el flujo principal del programa limpio y realizar dicho manejo de errores en otra parte:

          readFile {
              try {
                     open the file;
                     determine its size;
                     allocate that much memory;
                     read the file into memory;
                     close the file;
              } catch (fileOpenFailed) {
                     doSomething;
              } catch (sizeDeterminationFailed) {
                      doSomething;
              } catch (memoryAllocationFailed) {
                      doSomething;
              } catch (readFailed) {
                      doSomething;
              } catch (fileCloseFailed) {
                      doSomething;
              }
          }

Propagación de errores hacia la pila de métodos.

   La segunda ventaja es la capacidad de propagar un error. Considere lo siguiente y suponga que method1 es el único interesado en los errores que pudieran ocurrir dentro de readFile:

          method1 {
              call method2;
          }

          method2 {
              call method3;
          }

          method3 {
              call readFile;
          }

   Para la detección y manejo correspondiente utilizando técnicas tradicionales:

          method1 {
              errorCodeType error;
              error = call method2;
              if (error)
                  doErrorProcessing;
              else
                  proceed;
          }

          errorCodeType method2 {
              errorCodeType error;
              error = call method3;
              if (error)
                  return error;
              else
                  proceed;
          }

          errorCodeType method3 {
              errorCodeType error;
              error = call readFile;
              if (error)
                  return error;
              else
                  proceed;
          }

  Por el mecanismo que tiene la máquina virtual de Java de buscar en la pila de métodos uno que esté interesado en realizar el manejo de una excepción en particular, sólo los métodos interesados se preocupan del manejo de errores:

          method1 {
              try {
                  call method2;
              } catch (exception e) {
                  doErrorProcessing;
              }
          }

          method2 throws exception {
              call method3;
          }

          method3 throws exception {
              call readFile;
          }

Agrupación y diferenciación de tipos de errores.

   Debido a que todas las excepciones lanzadas por un programa son objetos, la agrupación y caracterización en categorías de excepciones es un resultado natural de la jerarquía de clases.

   Un método puede considerar un manejador específico para una excepción determinada:

          catch (FileNotFoundException e) {
                 ...
          }

o bien puede atrapar una excepción basándose en su grupo o tipo general es decir, alguna de sus super clases en la línea de generalización / herencia:

          catch (IOException e) {
                 ...
          }

en este sentido, se pueden encontrar los detalles particulares de lo que ocurrió a través de una consulta al argumento enviado al manejador de excepción:

          catch (IOException e) {
                 // Output goes to System.err.
                 e.printStackTrace();
                 // Send trace to stdout.
                 e.printStackTrace(System.out);
          }

incluso se puede hacer un manejador de excepciones que gestione cualquier excepción:

          // A (too) general exception handler
          catch (Exception e) {
                 ...
          }

   En resumen, se pueden crear grupos de excepciones y darles un manejo general, o se pueden utilizar categorías especificas de excepciones para diferenciarlas y manejarlas de una manera más precisa.

Lanzado y encadenamiento.

Lanzar una excepción.
    Antes de poder atrapar una excepción, debe haber en alguna parte un código que cree y lance una. Cualquier código puede lanzar una excepción, pero independientemente de qué o quién lance una excepción siempre es lanzada con la sentencia o cláusula throw.

    El Ejemplo Excepciones muestra lo anterior. Se tienen básicamente dos métodos además de main, uno de ellos (líneas 9-23) crea y lanza una excepción (línea 12) y el otro no (líneas 25-35). Note cómo la excepción lanzada en la línea 12 es atrapada en la línea 13 y relanzada en la línea 16 para que a su vez vuelva a ser atrapada en la línea 40. Es importante que el lector comprenda también los comentarios de las líneas 17 y 22, mismos que se dejan como ejercicio para que se validen y verifiquen.

    En este mismo orden de ideas, resulta conveniente que el lector revise el Ejemplo descrito en la entrada Implementación del ADT Racional en donde también se crea y lanza una excepción en un contexto particular.

   Adicionalmente a lo anterior, se recomienda también revisar la sección Excepciones de la entrada Ejemplos selectos de transición y la de Pila primitiva de la entrada Pilas (implementación), en las que encontrará respectivamente, la jerarquía de clases relacionadas con las excepciones y un ejemplo de creación de una excepción definida por el programador.

Excepciones encadenadas.
   Frecuentemente una aplicación responde a una excepción lanzando otra excepción, dicho de otra forma: la primera excepción causa la segunda. En este sentido puede ser muy útil el saber cuando una excepción causa otra. Las excepciones encadenadas ayudan al programador a realizar ésto.

   Los siguientes son una lista de métodos y constructores de la clase Throwable que dan soporte a las excepciones encadenadas:
          Throwable getCause( )
          Throwable initCause(Throwable)
          Throwable(String, Throwable)
          Throwable(Throwable)

   El argumento Throwable en initCause y en los constructores es la excepción que causó la excepción actual. getCause regresa la excepción que causó la excepción actual e initCause establece la causa de la excepción actual.

   El siguiente fragmento de código muestra un esqueleto de cómo utilizar una excepción encadenada:
           try {
                       . . .

           } catch (IOException e) {
                  throw new SampleException("Other IOException", e);
           }

    En el Ejemplo Excepciones2 se muestra un ejemplo de lanzado y encadenamiento que está en directa relación y continuación con lo expuesto en la sección anterior. Note particularmente las líneas 19 y 20, en donde se crea respectivamente la nueva excepción a partir de otra, y se incorpora al entorno de ejecución de la máquina virtual de Java (relanza). Asegúrese de comprender en su totalidad el ejemplo y de compararlo con el de la sección anterior (Ejemplo Excepciones). 

    Finalmente considere el Ejemplo Excepciones3. Aquí se tiene lo que se conoce como una pila de invocación de métodos, en donde el último en ser llamado es el que provoca o genera la excepción (creaExcepcion( )). Note cómo todos los métodos indican que pueden lanzar una excepción (throws Exception) pero que ninguno de ellos, exceptuando main, hace una manejo o atrapa alguna: todos la dejan pasar. El nivel de profundidad en la pila de invocación de métodos puede ser mayor o menor que el mostrado en el ejemplo en cuestión, aquí lo importante es asegurarse que se comprende el funcionamiento general, el relanzado implícito, y el encadenamiento de una sola excepción transferida entre los métodos involucrados.

Especificación de excepciones lanzadas por un método.

   La mayoría de las veces, es más conveniente atrapar las excepciones que ocurren dentro un método; sin embargo, en otros casos lo mejor es que el método deje pasar la excepción para que algún manejador de excepciones, en algún otro nivel en la pila de invocación de métodos, se encargue de ella.

   Así por ejemplo, si se estuviera construyendo una clase Lista<T> (vea la entrada Listas (implementación)) como parte de un paquete de clases que conforman toda una gama de estructuras de datos, es poco probable que se puedan prever y anticipar todos los posibles escenarios y las necesidades de uso en los que su paquete de clases podría utilizarse.

   Es precisamente en este tipo de casos en los que sería mejor no atrapar la excepción dentro del método, y mejor permitir que éste lance a su vez la excepción para que sea atrapada por algún manejador de excepciones en algún otro nivel en la pila de invocación de métodos.

   El siguiente método atrapa y maneja dos posibles excepciones que podrían generarse:

      public void writeList( ) {
              PrintWriter out = null;

              try {
                  System.out.println("Entering try statement");
                  out = new PrintWriter(new FileWriter("OutFile.txt"));
        
                  for (int i = 0; i < SIZE; i++)
                      out.println("Value at: " + i + " = " + list.get(i));
              } catch (IndexOutOfBoundsException e) {
                  System.err.println("Caught IndexOutOfBoundsException: " +
                                       e.getMessage());
              } catch (IOException e) {
                  System.err.println("Caught IOException: " + e.getMessage( ));
              } finally {
                  if (out != null) {
                      System.out.println("Closing PrintWriter");
                      out.close();
                  } else {
                      System.out.println("PrintWriter not open");
                  }
              }
          }

   Si el método no atrapara las excepciones que pueden ocurrir dentro de él, entonces debe especificar que puede lanzar dichas excepciones:

      public void writeList( ) throws IOException, IndexOutOfBoundsException {
              PrintWriter out = new PrintWriter(new FileWriter("OutFile.txt"));

              for (int i = 0; i < SIZE; i++) 
                  out.println("Value at: " + i + " = " + list.get(i));
              out.close();
      }

   Como IndexOutOfBoundsException es una excepción no verificada (unchecked exception), no es obligatorio incluirla en la cláusula throws, por lo que el método podría quedar como:

      public void writeList( ) throws IOException {
              PrintWriter out = new PrintWriter(new FileWriter("OutFile.txt"));

              for (int i = 0; i < SIZE; i++) 
                  out.println("Value at: " + i + " = " + list.get(i));
              out.close();
      }

   De esta manera, la excepción tendrá que ser manejada en algún otro lado, en aquella parte del código en que haga uso del método writeList( ).

    Conviene en este momento al lector revisar el Ejercicio 4 de la entrada Ejercicios selectos, con la finalidad de ampliar su perspectiva al revisar un ejemplo adicional respecto a la especificación de excepciones lanzadas por un método.

Excepciones.

   El lenguaje de programación Java utiliza excepciones para manejar errores y otros eventos excepcionales. Un programa en Java puede utilizar excepciones para indicar que ha ocurrido un evento excepcional, de hecho, el término excepción es la forma corta de decir evento excepcional.

   En este sentido, una excepción es un evento que ocurre durante la ejecución de un programa en Java, que interrumpe el flujo normal de ejecución del programa (vea What is an Exception).

   Cuando un error ocurre dentro de un método, el método crea un objeto (objeto de excepción) y lo coloca en el entorno de ejecución, el cual contiene información acerca del error, incluyendo su tipo y el estado del programa cuando ocurrió el error. A éste proceso se le denomina lanzar una excepción.

   Después de que un método lanza una excepción el entorno de ejecución intenta encontrar a alguien (manejador de excepción) que la atrape y la maneje:

La pila de invocación de métodos y la búsqueda del manejador de excepción (adaptada de What is an Exception).

   Para lanzar un excepción se debe hacer uso de la cláusula throw adjunta a un objeto de excepción (descendiente de la clase Throwable) para proporcionar información específica acerca del evento excepcional que ocurrió.

   Un código válido en el lenguaje de programación Java debe respetar la cláusula catch (también llamado requisito de especificación), lo cual significa que el código que podría lanzar ciertas excepciones debe estar encerrado por alguna de las siguientes:

• Una sentencia try que atrapa la excepción.
• Un método que especifica que puede lanzar la excepción.

  Cabe mencionar que no todas las excepciones están sujetas a esta situación, y la razón es que existen tres categorías básicas de excepciones y sólo una de ellas está sujeta a dicho requisito (excepción comprobada):

1. Excepción comprobada (checked exception): condiciones excepcionales que un programa o aplicación bien escrita debe considerar.
2. Error: condiciones excepcionales que son externas al programa o la aplicación; usualmente no es posible anticiparlas o recuperarse de ellas (mal funcionamiento del hardware o del sistema).
3. Excepción en tiempo de ejecución (runtime exception): condiciones excepcionales que son internas al programa o la aplicación sin que la aplicación pueda anticiparlas o recuperarse de ellas (errores lógicos a bugs).

   Las excepciones de error y de tiempo de ejecución se conocen comúnmente como excepciones no comprobadas o verificadas (unchecked exceptions).

   Un programa puede atrapar excepciones por medio de la combinación de los bloques try, catch y finally:

1. El bloque try identifica un bloque de código en el que una excepción puede ocurrir.
2. El bloque catch identifica un bloque de código, conocido como manejador de excepción (exception handler), que puede atrapar y manejar un tipo específico de excepción.
3. El bloque finally identifica un bloque de código que en general se garantiza que se ejecutará independientemente de si se generó (catch) o no (try) la excepción, por lo que es el lugar preciso para cerrar archivos, liberar recursos y cualquier tarea de limpieza que se requiera como parte de la ejecución del código que se ejecutó en el try.

   Una cláusula try podría contener al menos un bloque catch o finally, y múltiples bloques catch.

    Como un primer acercamiento, considere inicialmente el Ejemplo DivisionSinManejoExcepcion el cual muestra la posible generación de una excepción no verificada (unchecked) si se intenta hacer una división por cero (línea 16). La excepción que podría generarse es de la clase ArithmeticException; pero todavía más: ¿Qué sucede si en lugar de un número se introduce una letra o una cadena? Se conmina al lector a probar lo hasta aquí expuesto.

    El Ejemplo DivisionConManejoExepcion toma ya en consideración lo expuesto en el párrafo anterior e ilustra el uso de la cláusula try-catch líneas (27-43). El manejo de excepciones consiste en hacer que un programa, ante una situación anormal o fuera del flujo esperado de ejecución, pueda recuperarse y continuar y no simplemente terminar. Note que con excepción de las cláusula en cuestión, el programa es esencialmente el mismo que el anterior, con la consideración del ajuste de una bandera para determinar o no la continuación del programa (líneas 24, 35 y 44). Este ejemplo, además del manejo de la excepción aritmética, también considera la excepción InputMismatchException para el caso de que no se proporcionen los números enteros como entrada sino alguna otra cosa.

    ¿En qué orden debería colocarse las excepciones?, ¿cuál debemos poner primero? Las recomendaciones, una vez que se asume que se han localizado las excepciones más pertinentes, serían dos:

1. Atrape primero la excepción que a su consideración tenga más probabilidad de ocurrir, después la segunda y así sucesivamente.
2. Coloque primero las excepciones más específicas y al final las más generales; para ello, deberá consultar la jerarquía de clases correspondiente.
   

   Finalmente, además de invitar al lector a revisar el API de Java para la revisión y familiarización de las excepciones comentadas en esta entrada, es importante resaltar que la decisión de utilizar excepciones propias comprobadas (checked) o no (unchecked) debería seguir esta guía: si un cliente o usuario de nuestras clases tiene una expectativa de recuperarse razonablemente de una excepción, entonces la excepción debería ser del tipo comprobada (checked); por otro lado, si no puede hacerse nada para recuperarse de la excepción ésta debería ser no comprobada (unchecked). Para más información vea Unchecked Exceptions - The controversy.

POO (Consideraciones adicionales).

Respecto al envío de mensajes.

   La sintaxis general en Java para el envío de mensajes a un objeto es la siguiente:

objeto.mensaje(lista_de_argumentos);

donde objeto es un objeto de una clase previamente definida, y mensaje es uno de los métodos públicos definidos para dicha clase. La lista_de_argumentos es una lista de argumentos separada por comas, en donde cada argumento puede ser un objeto, o un tipo de dato primitivo.

Respecto a la sobrecarga de operadores.
   Algunos lenguajes de programación soportan un concepto relacionado con sobrecarga de operadores. La idea general del concepto de sobrecarga se ha planteado en la entrada POO (mensajes y métodos). El lenguaje de programación Java no soporta la sobrecarga de operadores, y por consiguiente, se ha omitido su descripción; sin embargo, es importante que el lector conozca que el concepto de sobrecarga no es exclusivo de los métodos o constructores, ni mucho menos de un lenguaje de programación en particular.

 

    La sobrecarga de operadores en C++ sí existe. En la sección correspondiente a las consideraciones adicionales para las colas de espera, se proporcionan un par de ejemplos al respecto. Para comprenderlos se requiere tener claros los aspectos relacionados con la implementación de la herencia, el funcionamiento de las colas de espera, y su respectiva especialización en la forma de colas de prioridad.

Respecto al paradigma.
   El establecimiento de niveles de acceso como private para los atributos de una clase, así como el uso de métodos de tipo set y get están directamente relacionados con el principio de ocultación de información (information hiding).

   Ahora bien, es probable que el lector haya notado que en la descripción del Ejemplo PruebaHerencia, en distintas ocasiones se hizo referencia a los objetos persona y científico como si fueran en sí mismos personas o entidades existentes. Lo anterior se hizo de manera deliberada, ya que como se comentó en la entrada referente al paradigma orientado a objetos, ésto eleva el nivel de abstracción y permite que se haga referencia a las entidades fundamentales del paradigma (los objetos), como elementos comunes de nuestro lenguaje natural, lo cual permite que los problemas se puedan expresar, al menos en principio, de una manera más natural e intuitiva.

   En este sentido, al dotar a los objetos de una personalidad propia con características y responsabilidades, en lugar de pensar en términos de datos, variables, y funciones o procedimientos que operen sobre dichos datos, se eleva el nivel de abstracción, facilitando con ello el análisis y la comprensión, ya que el problema y su solución pueden ser expresados y analizados en términos de su propio dominio, y no en el del medio (lenguaje de programación) de la solución. Ésta es una de las formas en la que las personas abstraemos, procesamos y utilizamos la información.

   Es sumamente importante que el lector tenga presente que en el paradigma orientado a objetos no se piensa en términos de datos, sino en términos de entidades con características y responsabilidades específicas, por lo que, cuando defina una clase, puede resultar útil el plantearse al menos un par de preguntas que le permitan determinar si los objetos derivados de su clase tienen o no sentido. Adicionalmente, las preguntas pueden ayudar también a establecer o coadyuvar en la meta de mantener una alta cohesión como parte del proceso de diseño e implementación:

1. ¿Los atributos representan características o propiedades, o definen un estado para los objetos que serán instanciados?
2. ¿La clase representa en sus métodos servicios, comportamiento, acciones o responsabilidades inherentes a los objetos que deriven de ella?

   Cabe mencionar que las preguntas propuestas son sólo una guía y una sugerencia al lector, no pretenden ser de ninguna manera una lista completa y absoluta. Con estas dos sencillas preguntas, además de validar y verificar su diseño de clases, estará reforzando también el concepto de encapsulamiento.

Respecto al polimorfismo.
   El polimorfismo es la cualidad de objetos heterogéneos de responder de distinta manera a un mismo mensaje. El tipo de polimorfismo más común se da en la herencia, pero no es el único.

   El Ejemplo Heterogéneo es un conjunto de clases (Automóvil, Motocicleta, Perro, Planta, Plomero, Profesor) heterogéneas que contienen un método de servicios. La idea es que, al menos en principio, cada una de dichas entidades ofrecen servicios distintos en función de su constitución y comportamiento general.

   Por otro lado, el Ejemplo Composición contiene tres clases: Libro, Publicación y Revista, las cuales presentan un comportamiento de polimorfismo en la forma en que se auto describen (imprimen), a través del método toString( ).

   En directa relación con el párrafo anterior, el tipo de polimorfismo más común se presenta en el Ejemplo Herencia, el cual contiene también las tres clases Libro, Publicación y Revista pero con un enfoque de polimorfismo basado en la herencia para la forma en que se auto describen (imprimen) a través del método toString( ).

   Existe un concepto en programación denominado latebinding, dynamic bindig o dynamic linkage, el cual se refiere a un mecanismo de programación en el cual el método que responderá al mensaje (el método que será invocado) es determinado en tiempo de ejecución. Como un ejemplo muy simple de esto, tómese el tiempo de comparar y analizar el Ejemplo PruebaHerencia (descrito en la entrada POO (Herencia)) y el Ejemplo PruebaPolimorfismo, en donde se muestra dicho concepto de programación, así mismo, es importante comprender tanto las diferencias de dichos ejemplos como los comentarios que aparecen en el código del Ejemplo PruebaPolimorfismo.

   Considere ahora el siguiente Ejemplo de late binding y tómese el tiempo que considere necesario para comprenderlo con base en el concepto de polimorfismo y  la comprensión de todos y cada uno de los ejemplos anteriores.

 

    Finalmente, una vez que se tengan madurados y comprendidos los ejemplos enunciados y su relación con el polimorfismo, se recomienda revisar también el tema de clases abstractas e interfaces (Java) para complementar dicho concepto.

Árboles binarios balanceados (AVL).

   Existen diferentes tipos y variaciones de los árboles binarios, y una de las más importantes es la de los árboles binarios balanceados, árboles binarios de búsqueda balanceados, o simplemente, árboles AVL.

Definición y conceptos.

   Un árbol binario balanceado (también conocidos simplemente como árboles AVL en honor a sus creadores Adelson-Velski y Landis) es un árbol binario de búsqueda (ABB) en el que las alturas de los dos subárboles de cada nodo difieren a lo más en 1.

   El balance de un nodo en un árbol binario en general y de un árbol AVL en particular, se define como la altura de su subárbol izquierdo menos la altura de su subárbol derecho:

| altura(arbolIzquierdo) - altura(arbolDerecho) | < 2

   También existe la correspondiente definición simétrica: la altura de su subárbol derecho menos la altura de su subárbol izquierdo; pero en este blog se adoptará la primera. Por convención, la altura de un árbol AVL nulo o vacío se define como -1.

   Durante el proceso de inserción o eliminación puede ocurrir un desbalance, es decir, que el valor absoluto de la altura de alguno de los nodos del árbol AVL sea mayor que 1.

   En caso de existir desbalance en alguno de los nodos, es decir, una condición que incumpla lo establecido por la expresión anterior, se tiene que rebalancear el árbol para que éste siga siendo un árbol AVL válido.

   En este sentido, existen cuatro casos que corrigen el balanceo de un árbol AVL:

1. Caso 1: rotación simple derecha.
2. Caso 2: rotación simple izquierda.
3. Caso 3: rotación doble izquierda derecha.
4. Caso 4: rotación doble derecha izquierda.

   A continuación se describen dos de estos cuatro casos, debido a que los otros dos son simétricos y pueden derivarse fácilmente a partir de los que se presentan.

Rotación simple.

   El primer caso de rebalanceo, la rotación derecha también conocida como rotación simple, se ilustra en la siguiente figura:

Caso 1: rotación derecha (adaptada de Wirth).

 

    La figura (a) muestra hasta antes de la inserción del elemento representado por el cuadrado rojo (cuadrado más obscuro), un árbol AVL balanceado. El balance puede determinarse gráficamente por los niveles representados por líneas horizontales punteadas: el balance para los nodos A y B es 0 y 1 respectivamente. Al insertar el elemento representado por el cuadrado rojo (cuadrado más obscuro), se presenta un desbalance sobre el nodo B: ahora el balance para los nodos A y B es 1 y 2 respectivamente.

   Por otro lado, la figura (b) muestra la solución al desbalanceo descrito en el párrafo anterior. Para visualizarlo mejor, imagine que en la figura (a), en el nodo representado por B existe una polea fija, de tal forma que al "jalar" z hacia abajo, el subárbol izquierdo de B representado por A sube, mientras que B baja convirtiéndose en el subárbol derecho de A. Note cómo y pasa de ser subárbol derecho de A, a ser subárbol izquierdo de B.

   Para el caso de la rotación izquierda el proceso es análogo pero de manera simétrica, al de la rotación derecha descrita en esta sección.

   Ejemplo.

   Considere el árbol AVL (asegúrese de que en efecto sea un árbol AVL y determine que el balance de cada uno de los nodos que se presenta es correcto) que aparece en la siguiente figura en (a):

Ejemplo de la aplicación de la rotación simple.

 

    La rotación simple derecha se presenta al insertar los elementos 1 o 3, los cuales se resaltan y presentan en la figura (b).

   El nodo desbalanceado es el que contiene al elemento 8 (¿Por qué?). La aplicación del Caso 1 de rotación dará como resultado el árbol AVL que aparece en la figura (c) dependiendo del elemento (1 o 3) que se haya insertado, de tal forma que la rotación simple derecha se realiza sobre el nodo que contiene al elemento 8 de la figura (b).

   Observe cómo la aplicación de la rotación simple corrige el balance general del árbol, de tal forma que el balance obtenido es casi perfecto.

   Antes de continuar, asegúrese de comprender el proceso de rebalanceo aplicado a la figura anterior, así como de determinar por su propia cuenta, el balance de cada uno de los nodos para los tres incisos.

Rotación doble.

   El caso de rebalanceo que implica una rotación doble es un proceso un poco más elaborado que el de la rotación simple, ya que como su nombre lo indica, implica dos rotaciones. La rotación doble izquierda derecha se muestran en la siguiente figura:

Caso3: rotación doble izquierda derecha (adaptada de Wirth).

 

    Ante una situación como la que se presenta en la figura (a) la solución está dada por la figura (c). Ahora bien, existe un paso intermedio entre éstas, mismo que está representado por la figura (b) y es el que se explicará a continuación:

• La figura (a) muestra, hasta antes de la inserción del elemento representado por el cuadrado rojo (cuadrado más obscuro), un árbol AVL balanceado. El balance puede determinarse gráficamente por los niveles representados por líneas horizontales punteadas: el balance para los nodos A, B y C es 0, 0 y 1 respectivamente. Al insertar cualquiera de los elementos representados por el cuadrado rojo (cuadrado más obscuro), se presenta un desbalance sobre el nodo C: ahora el balance para los nodos A, B y C es -1, (1 o -1 según sea el elemento insertado) y 2 respectivamente.
• Aunque C es el nodo desbalanceado, observe que el balance no se corrige si se realiza una rotación derecha sobre C (asegúrese de comprobarlo). Por otro lado, note los signos de los balances generados por la inserción del elemento que provoca el desbalance.
• En base a lo anterior, la figura (b) muestra una rotación izquierda sobre A aunque el nodo A no está desbalanceado. Note que el balance no se ha corregido todavía, ya que el balance de A es 0 o 1, el de B es 2 o 1, y el de C 2.
• Ahora bien, partiendo de la figura (b), una nueva rotación derecha sobre C generará el árbol de la figura (c) mejorando significativamente el balance general de la mayoría de los nodos.

    Asegúrese de comprender la doble rotación izquierda derecha explicada hasta aquí antes de continuar.

   El caso de la rotación doble derecha izquierda es simétricamente análogo o lo descrito con anterioridad.

   Ejemplo.

   Para ilustrar la rotación doble, considere el árbol AVL que aparece en la siguiente figura en (a). Una vez más y antes de continuar, compruebe que dicho árbol es un árbol AVL y que los balances propuestos son correctos.

Ejemplo de aplicación de la rotación doble.

   La rotación doble se presenta al insertar cualquiera de los elementos 5 o 7 (figura (b)).

   La aplicación de la rotación doble dará como resultado el árbol AVL que aparece en la figura (c) dependiendo del nodo que se haya insertado. Se deja como ejercicio para el lector generar el paso intermedio y comparar su resultado con el de la figura (c). El paso intermedio consiste en hacer una rotación izquierda sobre 4 en la figura (b), y posteriormente una rotación derecha sobre 8; estas dos rotaciones deberán generar la figura (c). Una vez más observe los signos de los balances en la rotación simple y en la doble; y asegúrese de comprender los procesos de balanceo aplicados en los ejemplos.

Consideraciones finales.

   Los árboles binarios tienen muchas y muy variadas aplicaciones. En este blog sólo se ha presentado una introducción tanto a los conceptos, como a algunos de los árboles binarios más comunes, pero es importante que el lector esté consciente de que los árboles binarios estudiados en esta sección no son los únicos tipos de árboles binarios.

   Otro tipos de árboles binarios son, por ejemplo:

• Árbol perfectamente balanceado.
• Árbol rojo negro.
• Árbol AA.
• Árbol biselado (splay).

   Se recomienda ampliamente al lector buscar información relacionada con al menos estos tipos de árboles binarios, con la finalidad de complementar y ampliar de mejor manera tanto sus conocimientos, como su visión de esta poderosa, versátil y útil estructura de datos.

Pilas (implementación).

   La representación de una pila, como una secuencia de nodos, se muestra en la siguiente figura. Los detalles de su implementación se desarrollarán a continuación.

Abstracción de una pila como una secuencia de nodos.

 Pila primitiva.

   Esta sección describe la implementación de una pila primitiva. Se ha denominado de esta forma debido a que implementa una estructura de datos que almacena un tipo de dato primitivo: int.

   La definición de la clase fundamental para la implementación de la estructura de datos se muestra en el Ejemplo NodoPrimitivo. Los detalles de este tipo de implementación de clases autorreferidas se han discutido con anterioridad en la entrada Abstracción de estructuras de datos y no se repetirán aquí, por lo que se sugiere al lector que la revise nuevamente y se tome el tiempo necesario para comparar el Ejemplo NodoPrimitivo con el Ejemplo Nodo antes de continuar.

   La implementación de la estructura de datos pila se muestra en el Ejemplo PilaPrimitiva, y su explicación se centrará únicamente en los métodos push, pop, estaVacia e imprime.

   El método estaVacia (líneas 37-39) realiza una verificación bastante simple: si el tope de la pila es igual a null, regresa verdadero (está vacía), si no, regresa falso (existe al menos un elemento).

   El método push por su parte (líneas 18-23), recibe como argumento el elemento a insertar en la pila (elemento), y se apoya del método estaVacia y de los constructores para realizar la inserción:

• Si la pila está vacía (línea 19), se crea un nuevo nodo con el elemento correspondiente (línea 20) para el atributo dato, y null en su atributo siguiente.
• Si la pila no está vacía (línea 21), se crea un nuevo nodo con el elemento correspondiente para el atributo dato y con el tope actual en su atributo siguiente (línea 22). Así mismo, note que el tope es actualizado para hacer referencia al nodo recién creado.

   Ahora bien, observe que el método pop (líneas 26-34) posee una característica particular: el método lanza (throws) una excepción ExcepcionEDVacia (línea 26) lo cual quiere decir que, en determinadas condiciones, el método puede lanzar una excepción; para el caso del método pop, la condición consiste en intentar eliminar un elemento de la pila cuando ésta está vacía.

   La excepción ExcepcionEDVacia definida en el Ejemplo ExcepcionEDVacia es en realidad bastante simple, ya que delega toda la responsabilidad a RuntimeException que es la clase de la que deriva, y lo único que hace es establecer un identificador para la excepción a través de sus constructores, los cuales en realidad utilizan el constructor de la super clase (clase padre) a través de la cláusula super. Es importante que el lector recuerde esta excepción, ya que será la excepción que utilizarán todas las estructuras de datos que se implementan en el blog.

   Ahora bien, cuando el programador se enfrenta a la necesidad de lanzar una excepción cabe la pregunta ¿y de qué tipo? Se puede utilizar una excepción escrita por alguien más o se puede hacer una propia. Se debería hacer clases de excepción propias cuando se responda de manera afirmativa a alguna de las siguientes preguntas, de otra forma, debería usarla una excepción escrita por alguien más (vea Creating Exception Classes):

• ¿Necesita un tipo de excepción que no está representada en el API de Java?
• ¿Sus usuarios se verán beneficiados si pueden diferenciar sus excepciones de aquellas lanzadas por clases escritas por alguien más?
• ¿Su código lanza más de una excepción relacionada?
• Si utiliza una excepción escrita por alguien más, ¿sus usuarios tendrán acceso a esas excepciones?
• ¿Su paquete de clases debería ser independiente y auto contenido?

   Continuando con el Ejemplo PilaPrimitiva, el método pop verifica (línea 27) si la pila está vacía, si lo está, crea y lanza la excepción correspondiente (línea 28); en caso contrario, recupera el dato almacenado (línea 30), y desecha el nodo correspondiente al hacer que el tope haga ahora referencia al elemento siguiente del tope actual (línea 31), para finalmente regresar el dato recuperado (línea 33). En Java no hay una eliminación o liberación explícita de memoria, dicha labor es delegada al recolector de basura el cual se encarga, grosso modo, de identificar aquellos objetos que no estén siendo referidos para entonces liberar la memoria que utilizan.

   Por último, en el método imprime (líneas 42-57), si la estructura de datos está vacía (línea 43), se reporta (línea 44); en caso contrario, se realiza un recorrido por todos los nodos de la estructura para imprimir su contenido (líneas 47-54).

   La clase de prueba para la pila primitiva del Ejemplo PilaPrimitiva, se presenta en el Ejemplo PruebaPila. Observe cómo en la línea 6 se crea la pila y se utiliza un constructor sin argumentos.

   Las líneas 9-12 realizan la inserción en la pila de los números del cero al nueve; por cada inserción se imprime todo el contenido de la pila, como se muestra en la siguiente figura:

Ejemplo de inserción de elementos en la pila primitiva. Se muestra la salida del Ejemplo PruebaPila.

    Por otro lado, las líneas 15-24 realizan la eliminación de los elementos de la pila. Dicho fragmento de código intenta eliminar once elementos (líneas 17-18) de la pila (recuerde que sólo fueron insertados diez elementos, por lo que al intentar eliminar el décimo primero, se generará la excepción ExcepcionEDVacia), y dado que el método pop puede lanzar una excepción, el código involucrado en la eliminación debe estar dentro de una cláusula try-catch-finally, la cual permite atrapar (cachar) las excepciones que un método pudiera lanzar.

   Si se genera un excepción ExcepcionEDVacia, ésta es atrapada y el flujo de control se envía al ámbito de la cláusula catch en donde se realiza el correspondiente tratamiento de la excepción. Para el caso del Ejemplo PruebaPila el manejo de la excepción consiste únicamente en imprimir la secuencia de eventos (en forma de pila) que dieron lugar a la excepción; sin embargo, es importante aclarar que el manejo de una excepción puede ser tan elaborado como en un momento dado se requiera.

   La salida correspondiente a la eliminación de elementos de la pila primitiva, se muestra en la siguiente figura:

Ejemplo de eliminación de elementos en la pila primitiva. Se muestra la salida del Ejemplo PruebaPila.

Pila genérica.

   Esta sección generaliza la implementación de una pila de tal forma que la estructura de datos tenga la capacidad de almacenar objetos genéricos; es decir, objetos de cualquier clase.

   Como primer paso, es preciso que el lector se tome el tiempo que considere necesario para comparar el Ejemplo NodoPrimitivo discutido en la sección anterior, con el Ejemplo NodoG. Es importante resaltar que, aunque distintos, ambos ejemplos son esencialmente equivalentes.

La primera diferencia que salta a la vista, además del nombre de la clase, es la notación <T>. Dicha notación se utiliza en Java para especificar que la clase gestiona objetos genéricos, es decir, que el tipo o la clase de los objetos que almacena no está especificada en la definición de la misma, sino que se especifica en el momento de la instanciación del objeto (observe la línea 6 del Ejemplo PruebaPilaGenerica).

   La línea 7 del Ejemplo NodoG define que la clase del atributo dato es T, es decir, un genérico, y por lo tanto el atributo siguiente es una referencia a un objeto que almacena objetos genéricos.

   Observe cómo ahora los constructores y los métodos de tipo set reciben como argumentos objetos genéricos T (líneas 10, 14 y 19), y referencias a objetos que a su vez almacenan objetos genéricos (líneas 14 y 27); mientras que los métodos de tipo get regresan genéricos (línea 23), o referencias a objetos que almacenan objetos genéricos (línea 31).

   Ahora bien, las consideraciones hechas para el Ejemplo NodoG respecto a los genéricos, son las mismas que debe tomar en cuenta para el Ejemplo Pila, por lo que una vez más se pide encarecidamente al lector que compare este último con el Ejemplo PilaPrimitiva discutido en la sección anterior tomando en consideración lo explicado hasta este momento para los genéricos.

   Observe que en ninguna parte del Ejemplo Pila se hace explícita una clase específica para el genérico T, por lo que también aquí se hace una gestión de genéricos en directa relación con los genéricos utilizados en el Ejemplo NodoG.

   En resumen, la clase NodoG del Ejemplo NodoG define nodos que almacenan objetos genéricos (nodos genéricos), los cuales son utilizados de manera conveniente por la clase Pila del Ejemplo Pila para conformar una estructura de datos dinámica que almacena objetos o nodos genéricos en forma de pila.

   El Ejemplo PruebaPilaGenerica muestra la clase de prueba para la pila genérica del Ejemplo Pila. La línea más importante del Ejemplo PruebaPilaGenerica es la línea 6, ya que es en ella en donde finalmente se define la clase de objetos que contendrá (almacenará) la pila: Integer.

   Consulte la sección Genéricos de la entrada Ejemplos selectos de transición para ampliar un poco más la información y los detalles acerca de los genéricos en Java. En el Ejemplo PilaC se muestra la implementación alternativa de una pila utilizando un ArrayList del API de Java; mientras que en el EjemploPruebaPilaC se presenta su correspondiente clase de prueba. Adicionalmente, se proporcionan al lector dos ejemplos adicionales que utilizan colecciones (estructuras de datos) del API: Stack y ArrayDeque (Deque); tómese el tiempo de estudiarlos y revisar la información correspondiente en el API.

   Finalmente, asegúrese de comprobar que la salida del Ejemplo PruebaPilaGenerica corresponde, en esencia, con la salida del Ejemplo PruebaPila para la inserción de datos (push), y que lo correspondiente ocurre también para la eliminación de elementos (pop).