Á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).

ABB (eliminacion).

   La eliminación de un elemento de un árbol binario de búsqueda consiste básicamente en, dado un elemento a eliminar:

• Identificar si dicho elemento se encuentra en el ABB (identificación de duplicados), si no existe, se podría regresar un valor que indique dicha situación y dejar el ABB sin cambios.
• Si el elemento existe en el ABB, entonces existen tres posibilidades:
1. Si el elemento está almacenado en un nodo hoja, la eliminación es directa.
2. Si el elemento está almacenado en un nodo con un solo hijo, el hijo sustituye al padre y se elimina el nodo correspondiente.
3. Si el elemento está almacenado en un nodo con dos hijos, la regla que se adoptará será la de sustituirlo por el hijo más a la derecha del subárbol izquierdo (el mayor de los menores). También existe la regla simétrica del hijo más a la izquierda del subárbol derecho (el menor de los mayores), pero no se utilizará en el blog, por convención, se utilizará la primera.

Observe también que con el proceso de eliminación descrito con anterioridad:

1. Se conserva la relación de orden que debe mantener un ABB.
2. Se podría incurrir en un intento de eliminación de un ABB vacío lo cual, desde el punto de vista de la implementación generaría una excepción, por lo que sería conveniente tener una forma de verificar dicha situación.

Diagrama de clases UML para un ABB con eliminación (Java).

 

 

Diagrama de clases UML para un ABB con eliminación (C++).

 

    En función de lo anterior, los diagramas de clases UML de las figuras anteriores complementan al presentado en la entrada ABB (representación y diseño). Observe que se han realizado las siguientes modificaciones en la clase ABB:

1. La incorporación de un atributo privado numérico (n) con la finalidad de llevar el control del número de elementos insertados en el ABB. Respecto a la implementación de éste, se debe considerar:
1. Inicializar explícitamente dicho atributo a cero en el constructor.
2. Proporcionar únicamente el método de tipo get para dicho atributo: obtenN( ) (obten_n( )).
2. La adición del método elimina, el cual realiza la eliminación de elemento si éste existe en el ABB devolviendo true como caso de éxito; en caso contrario, el método regresa false. Respecto a la implementación de este método, se debe considerar:
1. Seguir las reglas de eliminación descritas con anterioridad.
2. Lanzar la excepción ExcepcionEDVacia (excepcion_ED_vacia) ante un intento de eliminación de un ABB vacío, tal y como lo describe la relación que se muestra en los diagramas de clases.
3. La incorporación del método estaVacio (esta_vacio( )), el cual regresa true si el ABB está vacío y false en caso contrario.

   La implementación de las clases descritas en el diagrama UML correspondiente al lenguaje que utilice como medio, así como su correspondiente prueba, se dejan como ejercicio para el lector.

Encuesta kahoot.

   Esta encuesta es con fines estrictamente cualitativos, no afecta en ningún sentido los resultados de su evaluación o del curso en general.

   Puede ser contestada de manera anónima utilizando un seudónimo. Para iniciarla, da clic aquí y espera las instrucciones del profesor.