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

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.

ABB (implementación).

   Esta entrada presenta la implementación de un ABB en base a dos enfoques respecto a la inserción de elementos:

1. Enfoque recursivo.
2. Enfoque iterativo.

   Para ambas implementaciones se utiliza la clase NodoABB definida en el Ejemplo NodoABB, por lo que será la primera clase que se describirá.

   La clase NodoABB define un nodo capaz de almacenar objetos genéricos. Cada nodo definido por la clase tiene la forma de cada uno de los nodos de la siguiente figura:

Árbol binario de búsqueda (ABB) conformado por objetos de la clase NodoABB.

 

    Observe además que cada objeto instanciado tendrá dos referencias a objetos como él, las cuales representarán referencias hacia el subárbol izquierdo (nodoIzquierdo) y hacia el subárbol derecho (nodoDerecho).

   Los detalles restantes deberían resultarle familiares al lector, ya que en esencia se refieren a un constructor y a los métodos de tipo set y get para cada uno de los atributos. Asegúrese de comprender el Ejemplo NodoABB en su totalidad antes de continuar.

Enfoque recursivo.

   Probablemente el enfoque más común para la implementación de un ABB debido a la naturaleza inherente a la definición de dicha estructura de datos, sea el enfoque basado en la recursividad.

   El Ejemplo ABBr muestra la definición de la clase ABBr, la cual es en esencia la implementación de la representación definida en el diagrama de clases UML presentado en la entrada ABB (representación y diseño).

   El estudio y la comprensión de la implementación de los métodos de recorrido para un árbol binario de búsqueda (líneas 34-68), se dejan como ejercicio para el lector.

   El método inserta (líneas 13-18), crea la raíz del árbol (línea 15) si el ABB está vacío (línea 14), i.e. no existe. En caso contrario, delega la responsabilidad de la inserción de elemento dentro de arbol al método privado recursivo insertaR (línea 17).

   Por su parte, la idea del método insertaR (líneas 21-32) es verificar la relación de orden de elemento respecto del dato almacenado en el nodo actual, y entonces:

• Si elemento es menor (línea 22), debe ser insertado en el subárbol izquierdo.
• Si el subárbol izquierdo está vacío o disponible (línea 23), se crea un nuevo nodo con elemento como dato y se asigna como hijo izquierdo (línea 24). Si no está vacío (línea 25), se recorre el subárbol izquierdo de manera recursiva (línea 26) para encontrar la posición apropiada para elemento dentro del subárbol.
• Si elemento es mayor (línea 27), debe ser insertado en el subárbol derecho.
• Si el subárbol derecho está vacío o disponible (línea 28), se crea un nuevo nodo con elemento como dato y se asigna como hijo derecho (línea 29). Si no está vacío (línea 30), se recorre el subárbol derecho de manera recursiva (línea 31) para encontrar la posición apropiada para elemento dentro del correspondiente subárbol.

   La clase de prueba para la clase ABBr del Ejemplo ABBr se muestra en el Ejemplo PruebaArbol.

   La clase PruebaArbol del Ejemplo PruebaArbol utiliza la clase Random del API para generar un número aleatorio (línea 14) dentro de un rango específico; el cual, además de presentarse en la salida estándar (línea 15), representa el valor a ser insertado dentro del árbol binario de búsqueda (línea 16).

   Finalmente, el Ejemplo PruebaArbol realiza los tres recorridos más convencionales definidos para un ABB (líneas 19-27). Es ampliamente recomendable que el lector realice varias ejecuciones de la clase PruebaArbol y corrobore la salida con inserciones y recorridos realizados a papel y lápiz.

Una posible salida de los Ejemplos PruebaArbol y Prueba ABB.

 

    Una posible salida para el Ejemplo PruebaArbol se muestra en la figura anterior.

Enfoque iterativo.

   Un enfoque alternativo para la implementación de la operación de inserción en un árbol binario de búsqueda, es utilizar un ciclo en lugar de recursividad.

   El enfoque propuesto es casi tan compacto como el recursivo pero mucho más eficiente. La implementación sin recursividad del ABB representado en el diagrama de clase de la entrada ABB (representación y diseño) se presenta en el Ejemplo ABB.

   Al igual que antes, el estudio y la comprensión de la implementación de los métodos de recorrido (líneas 34-68), se dejan como ejercicio para el lector.

   El método inserta (líneas 13-32), crea la raíz del árbol (línea 15) si el ABB está vacío (línea 14), i.e. no existe. En caso contrario, se genera una referencia alterna (línea 17) para recorrer el árbol (línea 18).

   Al igual que antes, la idea es verificar la relación de orden de elemento respecto del dato almacenado en el nodo actual, y entonces:

• Si elemento es menor (línea 19), debe ser insertado en el subárbol izquierdo.
• Si el subárbol izquierdo está vacío o disponible (línea 20), se crea un nuevo nodo con elemento como dato y se asigna como hijo izquierdo (línea 21). Si no está vacío (línea 22), se cambia la referencia del subárbol en cuestión (abb), y se recorre el subárbol izquierdo (línea 23) para encontrar la posición apropiada para elemento dentro del árbol.
• Si elemento es mayor (línea 24), debe ser insertado en el subárbol derecho.
• Si el subárbol derecho está vacío o disponible (línea 25), se crea un nuevo nodo con elemento como dato y se asigna como hijo derecho (línea 26). Si no está vacío (línea 27), se cambia la referencia del subárbol en cuestión (abb), y se recorre el subárbol derecho (línea 28) para encontrar la posición apropiada para elemento dentro del ABB.
• Finalmente, si el elemento no fue menor ni mayor, entonces por tricotomía de los números no le queda otra más que ser igual, en cuyo caso no hay nada por hacer mas que terminar (líneas 29 y 30).

   La clase de prueba para la clase ABB del Ejemplo ABB se muestra en el Ejemplo PruebaABB.

   Al igual que antes, la clase PruebaABB del Ejemplo PruebaABB utiliza la clase Random del API para generar un número aleatorio (línea 14) dentro de un rango específico, el cual además de presentarse en la salida estándar (línea 15), representa el valor que será insertado dentro del árbol binario de búsqueda (línea 16).

   Finalmente, el Ejemplo PruebaABB también realiza los tres recorridos más convencionales definidos para un ABB (líneas 19-27). Una vez más, se recomienda ampliamente que el lector realice varias ejecuciones de la clase PruebaABB y corrobore la salida con inserciones y recorridos realizados a papel y lápiz.

ABB (representación y diseño).

   La representación de un árbol binario como la que se mostró en la entrada Árboles binarios (definición), es en realidad un árbol binario de búsqueda (ABB). La siguiente figura es también una representación (abstracción) de un ABB en un diagrama del estilo de los que se han utilizado a lo largo del blog. Dicho diagrama muestra elementos auxiliares (referencias) que serán de utilidad para trabajar con los distintos nodos del ABB, tal y como se detallará en la sección de Ejercicios para árboles binarios.

Representación de un ABB.

 

    Para complementar dicha abstracción, el diagrama de clases UML de las siguientes figuras muestran otro tipo de representación (que en sí misma es también una abstracción) para un ABB pero desde el punto de vista del diseño de clases:

Diagrama de clases UML para un ABB (Java).

 

Diagrama de clases UML para un ABB (C++).

 

    Observe cómo ha cambiado por completo la representación del nodo utilizado para un árbol binario de búsqueda (NodoABB) en comparación con el nodo que se había estado utilizando (NodoG) para las anteriores estructuras de datos lineales presentadas en el blog (consulte la sección Contenido temático para mayor información al respecto).

   La clase NodoABB define los atributos correspondientes para los subárboles izquierdo y derecho (representados por los atributos nodoIzquierdo y nodoDerecho respectivamente), y el dato a almacenar (dato). Adicionalmente, la clase define los servicios o comportamiento que deberá implementar la clase, los cuales corresponden a los métodos de tipo set y get; en este sentido, es de resaltar que éstos coinciden con las operaciones primitivas definidas para un árbol binario (consulte la sección Árboles binarios (operaciones primitivas)).

   Por otro lado, la clase ABB describe la abstracción correspondiente para la implementación del árbol binario de búsqueda y establece los servicios o el comportamiento que se espera en función de las operaciones primitivas definidas para un ABB (consulte la sección Operaciones primitivas del tema Árbol binario de búsqueda (ABB)).

   Tanto la definición en un diagrama de clases UML como la implementación correspondiente de los recorridos inversos, se dejan como ejercicios para el lector.

Árbol binario de búsqueda (ABB).

   Un árbol binario es una estructura de datos sumamente útil en muchos aspectos, en particular, cuando deben tomarse decisiones en dos sentidos en cada punto de un proceso determinado.

   Con base en lo anterior, suponga que por alguna razón se desea encontrar todos los duplicados de una secuencia de números. Para ello, considere lo siguiente:

1. El primer número de la secuencia se coloca en un nodo que se ha establecido como la raíz de un árbol binario, cuyos subárboles izquierdo y derecho estarán inicialmente vacíos.
2. Cada número sucesivo en la secuencia se compara con el número que se encuentra en la raíz del árbol binario. En este momento, se tienen tres casos a considerar:
1. Si coincide, se tiene un duplicado.
2. Si es menor, se examina el subárbol izquierdo.
3. Si es mayor, se examina el subárbol derecho.
3. Si alguno de los subárboles esta vacío, el número no es un duplicado y se coloca en un nodo nuevo en dicha posición del árbol binario.
4. Si el subárbol correspondiente no está vacío, se compara el número con la raíz del subárbol en cuestión, y se repite todo el proceso nuevamente con dicho subárbol.

   Un árbol binario de búsqueda (ABB) es un árbol binario que no tiene valores duplicados en los nodos, y además, tiene las siguientes características:

1. Los valores en cualquier subárbol izquierdo son menores que el valor en su nodo padre.
2. Los valores en cualquier subárbol derecho son mayores que el valor en su nodo padre.

   Tome en cuenta que un ABB es un árbol binario, pero un árbol binario no es necesariamente un ABB. En este sentido, todo lo que se ha dicho y definido para árboles binarios, es aplicable también a los árboles binarios de búsqueda.

Operaciones primitivas.

   Respecto a las operaciones primitivas, se definen cuatro operaciones primitivas para un ABB:

• inserta: inserta un nuevo nodo al árbol binario de búsqueda. La inserción se realiza de manera ordenada respecto del elemento a insertar, por lo que debe existir una relación de orden definida para el conjunto de datos al que pertenece dicho elemento.

   En resumen, la operación inserta de manera ordenada a elemento en el ABB cuando el objeto abb recibe el mensaje correspondiente, es decir: abb.inserta(elemento).

• recorre en preorden: recorre el ABB no vacío en orden previo, de tal forma que cuando el objeto abb recibe el mensaje: abb.recorrePreorden( ) se imprime en la salida estándar el recorrido en orden previo de abb.

• recorrido en orden: recorre el árbol binario de búsqueda no vacío en orden, de tal forma que cuando el objeto abb recibe el mensaje: abb.recorreEnorden( ) se imprime en la salida estándar el recorrido en orden de abb.

   Note cómo un recorrido en orden, como su nombre lo indica, imprime en la salida estándar los elementos almacenados en el árbol ordenados de manera ascendente.

• recorrido en postorden: recorre el ABB no vacío en orden posterior, de tal forma que cuando el objeto abb recibe el mensaje: abb.recorrePostorden( ) se imprime en la salida estándar el recorrido en orden posterior de abb.

   Para el caso de un árbol binario de búsqueda, también serían deseables otras operaciones, como aquellas que se definieron para los árboles binarios: primitivas, operaciones adicionales que podrían ser útiles y recorridos inversos por ejemplo (vea las entradas Árboles binarios (operaciones primitivas) y Árboles binarios (recorridos)).

   En este sentido, es importante resaltar que siempre que una operación no viole la relación de orden intrínseca a los ABB, es factible de ser implementada y que la decisión final respecto a su implementación estará en directa función de si ésta tiene o no sentido en la aplicación que se esté desarrollando.