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

Ejercicios selectos (árboles binarios).

Representación de un ABB.

1. Siguiendo las consideraciones descritas en el blog respecto a un ABB (entrada Árbol binario de búsqueda (ABB)), realice manualmente, es decir, en papel y lápiz, la inserción de la siguiente secuencia de elementos: 14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17.
1. Aplique el recorrido en pre orden al árbol resultante.
2. Aplique el recorrido en orden al árbol resultante.
3. Aplique el recorrido en post orden al árbol resultante.
4. Aplique también el recorrido en pre orden inverso.
5. Aplique el recorrido en orden inverso al árbol resultante.
6. Aplique finalmente el recorrido en post orden inverso.
2. Realice lo mismo que en el ejercicio anterior pero con la secuencia de números invertida, i.e.: 17, 20, 4, 16, 5, 3, 18, 7, 9, 4, 15, 14.
1. Aplique el recorrido en pre orden al árbol resultante.
2. Aplique el recorrido en orden al árbol resultante.
3. Aplique el recorrido en post orden al árbol resultante.
4. Aplique también el recorrido en pre orden inverso.
5. Aplique el recorrido en orden inverso al árbol resultante.
6. Aplique finalmente el recorrido en post orden inverso.
3. Modifique el Ejemplo PruebaArbol para que permita leer números desde la entrada estándar. Corrobore con el programa y los recorridos obtenidos en los ejercicios anteriores, que el árbol que genera el programa es el mismo que generó en papel y lápiz.
4. Basándose en el Ejemplo NodoABB, el Ejemplo ABBr, y el Ejemplo ABB, realice las modificaciones correspondientes en ambos tipos de implementación (recursiva e iterativa) para que, a través de métodos, proporcione solución a lo siguiente:
1. Dadas dos referencias a dos nodos cualesquiera de un árbol binario, determine si r1 es padre de r2 (vea la figura que aparece al inicio de esta entrada).
2. Dadas dos referencias a dos nodos cualesquiera de un árbol binario, determine si r2 es hijo de r1 (vea la figura que aparece al inicio de esta entrada).
3. Dada una referencia a un nodo cualquiera de un árbol binario, determine si dicho nodo es o no un nodo hoja.
4. Dadas dos referencias a dos nodos cualesquiera de un árbol binario, determine si r1 es ancestro de r2.
5. Dadas dos referencias a dos nodos cualesquiera de un árbol binario, determine si r2 es descendiente de r1.
6. Dada una referencia a un nodo cualquiera de un árbol binario, determine su nivel.
7. Determinar la altura o profundidad de un árbol binario.
8. Determinar si un árbol binario es o no un árbol estrictamente binario.
9. Determinar si un árbol binario es o no un árbol binario completo de profundidad p.
10. La implementación de las operaciones complementarias:
1. obtenPadre: regresa una referencia al padre de nd.
2. obtenHermano: regresa una referencia al hermano de nd.
3. esIzquierdo: regresa true si nd es un hijo izquierdo de algún otro nodo en el árbol binario, y false en caso contrario.
4. esDerecho: regresa true si nd es un hijo derecho de algún otro nodo en el árbol binario, y false en caso contrario.
5. Donde nd es una referencia a un nodo cualquiera de un árbol binario.
11. Determinar el número de nodos de un árbol binario.
12. La suma (se asume que el árbol binario almacena números) de todos los nodos del árbol binario.
5. Modifique el Ejemplo PruebaArbol para que almacene otro tipo de objetos además de los de la clase Integer. Pruebe con al menos las siguientes clases:
1. Float.
2. String.
3. Persona (del Ejemplo Persona).
4. Cientifico (del Ejemplo Cientifico).
6. Realice lo mismo que se pide en el ejercicio anterior, pero para el Ejemplo PruebaABB.
7. Modifique el Ejemplo PruebaABB para que:
1. En lugar de insertar números aleatorios en el árbol binario de búsqueda, solicite al usuario un número de datos n. Posteriormente deberá leer de la entrada estándar cada uno de los n datos, mismos que serán insertados en el ABB correspondiente.
2. Realice las comprobaciones de los recorridos y árboles generados manualmente. Un recorrido en preorden o postorden le hará saber si el árbol generado es correcto, tome en consideración que un recorrido en orden no le arrojará información útil al respecto.
3. Implemente los recorridos inversos descritos en la entrada (Árboles binarios (recorridos)). Nota: respecto a los recorridos inversos, resultaría sumamente conveniente que, previo a su implementación, realizara el diagrama de clases UML correspondiente basándose en el presentado en la entrada ABB (representación y diseño).
8. Con base en las consideraciones planteadas en el blog respecto a la eliminación de un ABB y al diagrama de clases UML presentado en la entrada ABB (eliminación), implemente la eliminación de elementos para un árbol binario de búsqueda, así como las modificaciones correspondientes mostradas en dicho diagrama.
9. Dada la siguiente secuencia de números: 4, 5, 7, 2, 1, 3, 6, genere en papel y lápiz su correspondiente ABB. Se deberá ilustrar paso a paso el proceso de inserción y realizar la comprobación de cada árbol con el programa generado en el Ejercicio 7.
10. Realice lo mismo que en el ejercicio anterior pero con la secuencia de números invertida, i.e.: 6, 3, 1, 2, 7, 5, 4.
11. Dada la siguiente secuencia de números: 4, 5, 7, 2, 1, 3, 6, genere en papel y lápiz su correspondiente árbol AVL. Se deberá ilustrar paso a paso el proceso de inserción y rebalanceo.
12. Realice lo mismo que en el ejercicio anterior pero con la secuencia de números invertida, i.e.: 6, 3, 1, 2, 7, 5, 4.
13. Dada la siguiente secuencia de números: 8, 9, 11, 15, 19, 20, 21, 7, 3, 2, 1, 5, 6, 4, 13, 14, 10, 12, 17, 16, 18, generar:
1. El correspondiente ABB.
2. El correspondiente árbol AVL.
3. El correspondiente ABB pero con la secuencia de números invertida.
4. El correspondiente árbol AVL pero con la secuencia de números invertida.
5. En cada caso se deberá ilustrar paso a paso en cada uno de los árboles generados, el correspondiente proceso de inserción.
14. Respecto al ejercicio anterior:
1. ¿Qué conjeturas puede obtener?
2. ¿En qué tipo de árbol se genera el árbol de altura mínima?
3. ¿Cuáles serían las ventajas y desventajas de uno y otro esquema de representación de árbol y por qué?
15. Considere la figura (a) que aparece al final de esta entrada de ejercicios, misma que representa un árbol AVL. Utilizando papel y lápiz:
1. Elimine la siguiente secuencia de elementos: 4, 8, 6, 5, 2, 1, 7.
2. Deberá ilustrar paso a paso:
1. Los balances de cada uno de los nodos.
2. La identificación del nodo a eliminar y el proceso de rebalanceo a aplicar en caso de ser necesario.
3. El correspondiente árbol AVL.
3. La solución final al ejercicio se presenta en la figura (b).
16. Genere el diagrama de clases UML que represente el diseño de un árbol AVL en base a lo expuesto en el blog. Puede basarse en el diagrama de la entrada ABB (representación y diseño). La idea de este ejercicio es que su diseño derive en una implementación.
17. Realice la implementación de un árbol AVL. Tome en consideración que, además de mantener los elementos ordenados como en un ABB, en cada inserción deberá verificar el balance de los nodos, y que en caso de ser necesario, deberá aplicar los mecanismos de rebalanceo descritos en el blog para asegurar que el árbol generado es siempre un árbol AVL.
18. En la entrada Árboles binarios balanceados (AVL) se discuten los aspectos de los árboles AVL relacionados con el rebalanceo después de la inserción. Sin embargo, ¿qué pasa con la eliminación de elementos? Apoyándose en el blog y en el ejercicio anterior, analice y resuelva los aspectos implicados en la eliminación de nodos en un árbol AVL, e implemente una operación que permita realizar la eliminación de un elemento. Asegúrese de mantener siempre un árbol AVL.

(a) Árbol AVL inicial para la eliminación (adaptada del libro Algoritmos y Estructuras de Datos de Niklaus Wirth).

(b) Árbol AVL final después del proceso de eliminación.

Orientación a Objetos (conceptos).

Objetos.
   Los objetos son esencialmente abstracciones. Son entidades que tienen un determinado estado, un comportamiento (determinado por sus responsabilidades), y una identidad.

• El estado está representado por los datos o los valores que contienen los atributos del objeto, los cuales son a su vez otros objetos o variables que representan las características inherentes del objeto.
• El comportamiento está determinado por las responsabilidades o servicios del objeto los cuales son definidos por los métodos, mismos que se solicitan a través de mensajes a los que dicho objeto sabe responder.
• La identidad es la propiedad que tiene un objeto que lo distingue o hace diferente de los demás. La identidad está representada por un identificador.

   Un objeto es una entidad que contiene en sí mismo, al menos en principio, toda la información necesaria que permite definirlo, identificarlo, y accederlo respecto a otros objetos pertenecientes a otras clases, e incluso respecto a objetos de su misma clase. La forma de acceder a un objeto es a través de su interfaz. La interfaz de un objeto es el conjunto de servicios públicos que ofrece el objeto, mismos que se solicitan a través de mensajes o solicitudes realizadas a dicho objeto.

   Los objetos se valen de mecanismos de interacción llamados métodos que favorecen la comunicación entre ellos. Dicha comunicación favorece a su vez el cambio de estado en los propios objetos. Esta característica define a los objetos como unidades indivisibles en las que no se separa el estado del comportamiento.

   Orientación a objetos vs. enfoque estructurado.
   La orientación a objetos difiere del enfoque estructurado básicamente en que en la programación estructurada los datos y los procedimientos están separados y sin relación explícita, ya que lo único que se busca en la programación estructurada es el procesamiento de los datos de entrada para obtener los datos de salida.

   La programación estructurada utiliza en primera instancia un enfoque basado en procedimientos o funciones, y en segunda instancia, las estructuras de datos que dichos procedimientos o funciones manejan, cumpliendo así con la ecuación planteada por Niklaus Wirth:

Algoritmos + Estructuras de Datos = Programas

   Por otro lado, un programa en un enfoque OO solicita estructuras de datos (las cuales son otros objetos) para llevar a cabo un servicio.

   La perspectiva OO también define programas compuestos por algoritmos y estructuras de datos esencialmente; sin embargo, lo hace desde un enfoque diferente. En la orientación a objetos la descripción del objeto se da en términos de responsabilidades y características; y así, al analizar un problema en dichos términos, se eleva el nivel de abstracción.

   Lo anterior permite una mayor independencia entre los objetos, lo cual es un factor crítico en la solución de problemas complejos. Cabe mencionar por último en este sentido, que al conjunto completo de responsabilidades asociadas a un objeto se le refiere comúnmente como protocolo.

Objetos y clases.
   Todos los objetos son instancias de una clase (categoría). Esta relación de un objeto con una clase, hace que los objetos tengan las siguientes características:

• El método invocado por un objeto en respuesta a un mensaje es determinado por la clase del objeto receptor.
• Todos los objetos de una clase determinada utilizan el mismo método en respuesta a mensajes similares.
• Las clases pueden ser organizadas en una estructura jerárquica de herencia como la que se muestra en la figura de abajo.
• Una clase hija o subclase heredará todas las características de la clase de la que deriva (clase padre clase madre o súper clase).
• Una clase abstracta es una clase de la que no se derivan instancias directamente, sino que es utilizada únicamente para crear subclases.
• La búsqueda del método a invocar en respuesta a un mensaje determinado inicia en la clase del receptor. Si no se encuentra el método apropiado, la búsqueda se realiza en la clase padre, si no se encuentra ahí, se busca en la clase padre de la clase padre y así sucesivamente hasta encontrar el método correspondiente.
• Si se encuentran métodos con el mismo nombre dentro de la jerarquía de clases, se dice que el método procesado sobre escribe (override) el comportamiento heredado.

Diagrama de ejemplo de jerarquía de clases.

   La figura anterior presenta una posible jerarquía de clases para un Ser Vivo. Más que una clasificación o taxonomía completa, la figura muestra el concepto de herencia a través de un árbol. En la figura puede observarse que los elementos que se derivan comparten características (atributos) y comportamientos (métodos) semejantes.

   Así por ejemplo, es posible decir que Flipper es una instancia particular de todos los posibles delfines que podrían existir. A su vez, un Delfín comparte características comunes con una Ballena en cuanto a que ambos son Cetáceos pero difieren en otras (si un delfín y una ballena coincidieran en todo (características y comportamiento) serían de la misma clase).

   Un Delfín es un Cetáceo, y un Cetáceo es un Mamífero. En muchas ocasiones a éste tipo de relaciones se le denomina "es un" (is a), y es una característica útil para identificar herencia pero no es la única.

   Existe otro tipo de relación y se denomina "tiene" (has-a). Estas relaciones son dos formas importantes de abstracción en la orientación a objetos:

1. La idea de división en partes (has-a): un automóvil tiene un motor, tiene una transmisión, tiene un sistema eléctrico, etc.
2. La idea de división en especializaciones (is-a): un automóvil es un medio de transporte, es un objeto de cuatro ruedas, es un objeto que se dirige con un volante, etc.

   Finalmente, la figura anteriormente presentada muestra que Flipper es un Delfín, que un Delfín es un Cetáceo, y que éste a su vez es un Mamífero; que un Mamífero pertenece al Reino Animal, y que el Reino Animal es parte de los seres vivos representados por la súper clase de todas las clases o clase base Ser Vivo.