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.

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.

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

Árboles binarios (recorridos).

   Una operación muy común en un árbol binario es la de recorrer todo el árbol en un orden específico pero ¿Cuál sería el orden natural de recorrido de un árbol binario? Piense por un momento en ello.

   A la operación de recorrer un árbol binario de una forma específica y de enumerar o visitar sus nodos, se le conoce como visitar el árbol, es decir, procesar el valor o dato de cada uno de los nodos para realizar algo con él.

   En general, se definen tres métodos de recorrido sobre un árbol binario, y para ello, se deberán tomar en cuenta las siguientes consideraciones:

1. No se necesita hacer nada para un árbol binario vacío.
2. Todos los métodos se definen recursivamente.
3. Siempre se recorren la raíz y los subárboles izquierdo y derecho, la diferencia radica en el orden en que se visitan.

   Para recorrer un árbol binario no vacío en orden previo (orden de primera profundidad), se ejecutan tres operaciones:

1. Visitar la raíz.
2. Recorrer el subárbol izquierdo en orden previo.
3. Recorrer el subárbol derecho en orden previo.

   Ahora bien, para recorrer un árbol binario no vacío en orden (orden simétrico), se ejecutan tres operaciones:

1. Recorrer el subárbol izquierdo en orden.
2. Visitar la raíz.
3. Recorrer el subárbol derecho en orden.

   Finalmente, para recorrer un árbol binario no vacío en orden posterior, se ejecutan tres operaciones:

1. Recorrer el subárbol izquierdo en orden posterior.
2. Recorrer el subárbol derecho en orden posterior.
3. Visitar la raíz.

   Tome en consideración que los tres recorridos anteriormente descritos son únicamente tres posibilidades de seis recorridos distintos que es posible realizar sobre un árbol binario; sin embargo, son los recorridos más comunes.

   Los otros tres recorridos posibles se describen a continuación, y a falta de un mejor nombre, se les denominará recorridos inversos.

Para recorrer un árbol binario no vacío en orden previo inverso, se ejecutan tres operaciones:

1. Visitar la raíz.
2. Recorrer el subárbol derecho en orden previo inverso.
3. Recorrer el subárbol izquierdo en orden previo inverso.

   Por otro lado, para recorrer un árbol binario no vacío en orden inverso, se ejecutan tres operaciones:

1. Recorrer el subárbol derecho en orden inverso.
2. Visitar la raíz.
3. Recorrer el subárbol izquierdo en orden inverso.

   Finalmente, para recorrer un árbol binario no vacío en orden posterior inverso, se ejecutan tres operaciones:

1. Recorrer el subárbol derecho en orden posterior inverso.
2. Recorrer el subárbol izquierdo en orden posterior inverso.
3. Visitar la raíz.

Árboles binarios (definición).

   Un árbol binario es un conjunto finito de elementos el cual está vacío, o dividido en tres subconjuntos disjuntos:

1. El primer subconjunto contiene un elemento único llamado raíz del árbol.
2. El segundo subconjunto es en sí mismo un árbol binario y se le conoce como subárbol izquierdo del árbol original.
3. El tercer subconjunto es también un árbol binario y se le conoce como subárbol derecho del árbol original.

   Tome en consideración que en un árbol binario, tanto el subárbol izquierdo como el subárbol derecho podrían estar vacíos.

Representación y conceptos.

   Respecto a su representación, es común denominar a cada elemento de un árbol binario como nodo del árbol. La siguiente figura muestra una posible representación para un árbol binario:

Abstracción de un árbol binario como una estructura de nodos.

 

    Ahora bien, la representación de árbol binario de la figura anterior resultará sumamente útil para desarrollar e ilustrar los siguientes conceptos:

• Si B es la raíz de un árbol binario y D es la raíz del subárbol izquierdo/derecho (todos los conceptos que sigan esta notación tienen una naturaleza simétrica debido a la característica inherente a los árboles y por lo tanto, aplica tanto para el subárbol izquierdo como para el subárbol derecho), se dice que B es el padre de D y que D es el hijo izquierdo/derecho de B.
• A un nodo que no tiene hijos como los nodos A o C, se le conoce como nodo hoja.
• Se dice que un nodo n1 es un ancestro de un nodo n2 (y que n2 es un  descendiente de n1) si n1 es el padre de n2 o el padre de algún ancestro de n2.
• Recorrer un árbol de la raíz hacia las hojas se denomina descender el árbol, y al sentido opuesto, ascender el árbol.
• El nivel de un nodo en un árbol binario se define del modo siguiente:

1. La raíz del árbol tiene el nivel 0.
2. El nivel de cualquier otro nodo en el árbol es uno más que el nivel de su nodo padre.

• La profundidad o altura de un árbol binario, es el máximo nivel de cualquier hoja en el árbol.

   Por otro lado, se dice que un árbol estrictamente binario es aquel en el que cada nodo que no es hoja, tiene sus subárboles izquierdo y derecho no vacíos. En términos coloquiales, un árbol estrictamente binario es un árbol binario en el que cada nodo, tiene dos hijos o simplemente no tiene; es decir, no se vale tener un solo hijo: dos o nada.

   De lo anterior, observe que un árbol estrictamente binario con n hojas, siempre contiene 2n - 1 nodos (¿Por qué?).

   Otro tipo de árboles binarios son los árboles binarios completos. Un árbol binario completo de profundidad p, es un árbol estrictamente binario que tiene todas sus hojas en el nivel p.

Árboles binarios (operaciones primitivas).

   Respecto a las operaciones primitivas para un árbol binario considere lo siguiente:

Sea p una referencia a un nodo cualquiera (nd) de un árbol binario. Se definen las siguientes operaciones primitivas sobre dicho árbol:

• obtenDato regresa el contenido (datos) de nd cuando se le envía el mensaje correspondiente al objeto p, es decir:
• p.obtenDato( ).
• obtenNodoIzquierdo regresa una referencia al hijo izquierdo de nd cuando se le envía el mensaje correspondiente al objeto p, es decir:
• p.obtenNodoIzquierdo( ).
• obtenNodoDerecho regresa una referencia al hijo derecho de nd cuando se le envía el mensaje correspondiente al objeto p, es decir:
• p.obtenNodoDerecho( ).
• estableceDato asigna un valor específico representado por d a nd cuando se le envía el mensaje correspondiente al objeto p, es decir:
• p.estableceDato(d).
• estableceNodoIzquierdo asigna un nodo representado por n, como hijo izquierdo de nd cuando se le envía el mensaje respectivo al objeto p, es decir:
• p.estableceNodoIzquierdo(n).
• estableceNodoDerecho asigna un nodo representado por n, como hijo derecho de nd cuando se le envía el mensaje respectivo al objeto p, es decir:
• p.estableceNodoDerecho(n).

   Por otro lado y siguiendo las consideraciones planteadas con anterioridad, algunas otras operaciones que podrían ser útiles en la implementación de un árbol binario, son las siguientes:

1. La operación obtenPadre regresa una referencia al padre de nd.
2. La operación obtenHermano regresa una referencia al hermano de nd.
3. La operación esIzquierdo regresa true si nd es un hijo izquierdo de algún otro nodo en el árbol binario, y false en caso contrario.
4. La operación esDerecho regresa true si nd es un hijo derecho de algún otro nodo en el árbol binario, y false en caso contrario.

   Dichas operaciones no son las únicas posibles; sin embargo, son deseables como los servicios adicionales que podría proporcionar un árbol binario.

Consideraciones adicionales.

   Una de las aplicaciones más útiles de las colas, las colas de prioridad y de las listas vinculadas es la simulación.

   Un programa de simulación modela una situación del mundo real para aprender u obtener algo de ella. En una simulación, cada objeto y acción del mundo tiene su representación en el programa.

   Si la simulación es precisa, el resultado del programa reflejará el resultado de las acciones que se simulan, por lo que será posible comprender lo que ocurre en una situación del mundo real sin la necesidad de observar su ocurrencia en el mundo real.

   Algunos de los contextos en los que es posible aplicar técnicas de simulación utilizando las estructuras de datos anteriormente mencionadas son:

• Bancos.
• Líneas aéreas.
• Casetas de cobro de autopistas.
• Terminal de autobuses.
• Líneas de espera en general.
• Un largo etcétera.

   Las listas enlazadas completan el espectro de las estructuras de datos lineales que se estudiarán en este blog, mismo que dio inició con las pilas. Debe notar que en éste sentido se ha ido avanzando de lo particular hacia lo general, ya que como pudo apreciarse, las listas enlazadas son las estructuras de datos que menos restricciones tienen en su definición y operaciones.

   Tanto los usos como las aplicaciones de las pilas, las colas de espera y las listas enlazadas son prácticamente infinitas, ya que están limitadas únicamente por la imaginación o la capacidad del programador.

 

Iteradores.

    Un iterador es un objeto que permite al programador recorrer un contenedor de una manera determinada. Puede verse también como la entidad que le permite a un programa "caminar" o recorrer una estructura de datos desde el exterior.

 

Diagrama de clases de la estructura del patrón de diseño de un iterador [Wikipedia].

 

    En el contexto en que se ha venido manejado en el blog, un iterador regresará el valor almacenado (dato) en los nodos internos de la estructura de datos.

    Iteradores en Java.

    El API de Java proporciona distintas colecciones que pueden ser recorridas con iteradores. Cualquier clase que implemente la interfaz Iterator debe ser capaz de regresar un iterador que permita recorrer los elementos que almacena.

    A modo de ejemplo se hará una modificación al Ejemplo Lista estudiado en la entrada correspondiente a la implementación. Por simplicidad y para tener un ejemplo completamente funcional, se proporcionará como una carpeta comprimida que contiene todos los archivos necesarios para su ejecución. Sólo se resaltarán los cambios en dos clases, y se deja como ejercicio al lector hacer la comparación correspondiente con el ejemplo original:

1. Lista:
1. Linea 10: implementación de la interfaz Iterator.
2. Línea 13: objeto que se regresará como iterador (referencia externa).
3. Línea 22: inicialización del iterador en el constructor.
4. Líneas 104-109: implementación del método next de la interfaz Iterator. Este método se encarga de obtener el siguiente dato de la lista, regresarlo y avanzar hacia el siguiente nodo.
5. Líneas 111-113: implementación del método hasNext de la interfaz Iterator. Este método se encarga de determinar si hay más elementos (true) o no (false) en la estructura de datos.
6. Líneas 115-118: implementación del método iterator de la interfaz Iterator. Este método se encarga de iniciar un iterador al principio de la estrictura de datos para poderla recorrer desde el exterior. Note que el método regresa una referencia al mismo objeto (this) ya que su clase (Lista) implementa la interfaz Iterator y en ella están definidos los métodos requeridos para gestionar el iterador.
   
2. PruebaLista:
1. Línea 5: inclusión de la interfaz Iterator del paquete java.util.
2. Líneas 19-22: uso del iterador implementado en la clase Lista.

    Adicional a la interfaz Iterator, existe también en el API la interfaz Iterable (más reciente), que permite hacer uso de ciclos del tipo for-each. El Ejemplo ListaIterable muestra su implementación y uso y, dado que los cambios son menores y relativamente simples respecto del ejemplo anterior, se deja su análisis y estudio como ejercicio para el lector.

    Iteradores en C++. 

    La idea de un iterador debería ser el poder recorrer la colección o estructura de datos en cuestión desde el exterior sin tener que conocer los detalles de su implementación. En este sentido, un iterador será un objeto que haga referencia a un elemento dentro del contenedor (la lista) y, dado que finalmente es un apuntador, puede ser utilizado para acceder al elemento al que se refiere y para moverse a través de todos los elementos del contenedor.

    El Ejemplo lista_iterador se basa en general en el Ejemplo lista estudiado con anterioridad. Ahora bien, el primero ha sido rediseñado en su totalidad, por lo que podría resultar conveniente al lector comprender y analizar antes el Ejemplo lista2.

    Para el ejemplo en turno se han incorporado también algunas de las características más recientes del lenguaje C++, por lo que los cambios más sobresalientes se enuncian a continuación, manteniendo el énfasis en la implementación respecto al iterador:

• Implementación básica del iterador (líneas 67-94):
• Apuntadores que representan las referencias la nodo actual y anterior de la lista (líneas 69-70).
• Constructores y mecanismos de inicialización del iterador (líneas 73-74).
• Implementación de los tres operadores fundamentales (se puede y deben implementar otros):
• Operador de preincremento: ¿qué debe hacer el iterador cuando se incremente? (líneas 77-83).
• Operador de diferencia: ¿cómo sabe un iterador que es distinto de otro? (líneas 86-88).
• Operador de desreferencia: ¿qué regresa el iterador cuando se acceda a lo que apunta? (líneas 91-93).
• Incorporación de mecanismos que permitan obtener un iterador al inicio de la colección y poder determinar su fin (líneas 184-186).
• Uso del iterador:
• Uso del esquema para cada (for-each) en las líneas 206-207.
• Uso del esquema tradicional del iterador en las líneas 211-216.

    El ejemplo en turno incorpora algunas características nuevas en las que vale la pena documentarse, como el uso de noexcept, inline, auto, etc., se deja como ejercicio para el lector su documentación.

 

    Finalmente, cabe mencionar que una implementación más robusta de iteradores requiere de un conocimiento más amplio, sobre todo si se espera que nuestra estructura de datos pudiese ser utilizada por otros programadores o por los algoritmos de la biblioteca estándar. Lo expuesto aquí es sólo una implementación básica, ya que existen distintos tipos de iteradores, operadores de acceso, consideraciones de recorrido, etcétera. Un punto inicial y de buena referencia puede ser la sección de iteradores de cplusplus, en dónde podrá encontrar además la información referente a los otros aspectos utilizados en el ejemplo.

Listas doblemente enlazadas.

   Aunque una lista enlazada circular tiene ventajas sobre una lista simplemente enlazada (vea la entrada Listas circulares), también tiene algunas desventajas:

• No es posible recorrer la lista enlazada circular hacia atrás (o hacia la izquierda); es decir, sólo puede recorrerse en un sentido.
• Dada una referencia a un nodo determinado de la lista enlazada circular, no es posible eliminar dicho nodo utilizando únicamente dicha referencia (¿Por qué?).

   En este sentido, una estructura de datos conveniente para subsanar dichas desventajas es precisamente, la lista doblemente enlazada.

Definición, primitivas y representación.

   Una lista doblemente enlazada es una colección lineal de nodos auto referidos en donde cada nodo tiene dos referencias:

1. Una referencia al sucesor del nodo actual (siguiente).
2. Una referencia al antecesor del nodo actual (anterior).

   La representación de una lista doblemente enlazada se muestra en la figura (a). Observe cómo al igual que en una lista enlazada, una lista doblemente enlazada puede ser también doblemente enlazada circular (figura (b)). Esta última, sigue también las mismas consideraciones que se hicieron en su momento para una lista enlazada circular.

(a) Abstracción de una lista doblemente enlazada.

(b) Abstracción de una lista doblemente enlazada circular.

   Adicionalmente, las operaciones primitivas para una lista doblemente enlazada son exactamente las mismas que para una lista simplemente enlazada, por lo que no se repetirán aquí.

   Por otro lado, los diagramas de clases UML para los lenguajes Java y C++ de una lista doblemente enlazada se presentan a continuación. Los diagramas complementan la definición de la estructura de datos a través de su correspondiente diseño de clases:

Diagrama de clases UML para una lista doblemente enlazada (Java).

 

Diagrama de clases UML para una lista doblemente enlazada (C++).

 

    Por ultimo, note que dichos diagramas de clases son sustancialmente distintos de los que en general se han utilizado hasta ahora para el diseño de las anteriores estructuras de datos y que, exceptuando la clases ExcepcionEDVacia (excepcion_ED_vacia), tanto las clases ListaDoble (lista_doble) como las clases NodoDobleG (Nodo_doble) han sufrido cambios significativos. Consulte la sección de ejercicios correspondiente para obtener más detalles al respecto.

Listas circulares.

   Las listas enlazadas, también denominadas listas simplemente enlazadas, son sumamente útiles y convenientes para diferentes usos y aplicaciones; algunas de las cuales ya han sido mencionadas. Aunque las listas simplemente enlazadas son muy dinámicas presentan, como casi todo en la vida, ciertos inconvenientes.

   Algunas de las situaciones indeseables que se tienen con una lista simplemente enlazada son las siguientes:

• Dada una única referencia a un nodo determinado de la lista enlazada y suponiendo que éste no sea el primero, no se puede llegar a ninguno de los nodos que lo preceden, es decir, no pueden alcanzarse los nodos anteriores a él.
• Si por alguna razón se recorre la lista enlazada, siempre debe conservarse una referencia externa (además de la que se utilizó para el recorrido) al inicio de dicha lista enlazada con la finalidad de poder volver a recorrer la lista nuevamente en caso de ser necesario.

   Con base en lo anterior, considere la siguiente modificación respecto a la estructura de una lista simplemente enlazada:

El elemento siguiente en el último nodo hará referencia al primer nodo y no a null; siendo en esto diferente a lo que se define para una lista simplemente enlazada convencional.

   Al tipo de lista enlazada que adopta dicha modificación se le denomina lista simplemente enlazada circular. Su representación se muestra en la siguiente figura:

Abstracción de una lista simplemente enlazada circular representada como una secuencia de nodos.

 

    Es importante hacer notar que en una lista enlazada circular es posible llegar a cualquier otro nodo de la estructura de datos partiendo de un nodo distinto cualquiera, lo cual subsana los dos inconvenientes enunciados al principio de esta sección para una lista simplemente enlazada.

   Observe también que una lista enlazada circular no tiene un “primer” o “último” nodo natural, por lo que se debe establecer un primer y último nodo por convención, lo cual es más una conveniencia que una característica inherente a la estructura de datos.

   Finalmente, tome en cuenta que una referencia a null/nullptr (Java/C++) representa una lista circular vacía, y que una lista circular de un solo nodo es un nodo cuyo atributo de auto referencia contiene una referencia hacia sí mismo como lo muestra la siguiente figura:

Lista circular de un solo elemento.

   El problema de Josephus.

   El siguiente es un problema clásico en el área de las estructuras de datos, y su solución utilizando listas enlazadas circulares es una aplicación clave:

   Un grupo de soldados se encuentra rodeado por una abrumadora fuerza enemiga. No hay esperanza de victoria sin refuerzos. Lamentablemente, sólo hay un caballo disponible para ir en su busca (o escapar).

   Los soldados realizan un pacto de honor para determinar cuál de ellos tomará el caballo y, en el mejor de los casos, pedirá ayuda. Para ello, forman un círculo y van eligiendo un número de un sombrero (n). También se elige uno de los nombres de los soldados de otro sombrero.

   Iniciando con el soldado cuyo nombre se eligió, se empieza a contar en el sentido de las manecillas del reloj alrededor del círculo. Cuando la cuenta llega a n el soldado correspondiente se retira del círculo y la cuenta vuelve a empezar con el soldado que se encontraba a su derecha.

   El proceso continúa análogamente hasta que sólo queda un soldado, mismo que tomará al caballo y pedirá ayuda (o escapará trágica e irremediablemente para los demás soldados).

   En resumen el problema de Josephus es: dado un número entero positivo n, el ordenamiento de los soldados en el círculo, y el soldado a partir del que comienza la cuenta, determinar:

1. El orden en el cual se eliminan los soldados del círculo.
2. Cuál soldado es el que escapa.

   La solución al problema de Josephus se deja como ejercicio para el lector.

Herencia vs. composición (listas).

   Uno de los aspectos más importantes de la programación orientada a objetos es la conveniencia de la reutilización de código por medio de la abstracción. En este sentido, dos de los esquemas más comunes al respecto son: la herencia y la composición.

   Esta entrada muestra, por medio de un ejemplo ya conocido y presentado previamente al lector, la implementación de una pila utilizando una lista enlazada. Dicha implementación se realiza empleando los dos esquemas mencionados con anterioridad. Así mismo, se analizan las ventajas y desventajas de cada uno de ellos.

   Implementación de una pila utilizando herencia.

   La implementación de una pila por medio de una lista con un enfoque basado en la herencia es en realidad bastante simple. Para muestra, basta con ver el código del código del Ejemplo PilaH.

   Observe que la clase del Ejemplo PilaH no define atributos, y que únicamente define dos constructores y los métodos push y pop; lo cual también ha sido representado en el diagrama de clases UML de la siguiente figura.

Diagrama de clases UML para la implementación de una pila utilizando herencia y una lista enlazada.

 

    Insto nueva y amablemente al lector a que compare, contraste, y analice con detenimiento antes de continuar, a la figura anterior con el Ejemplo PilaH.

   Note que los métodos push (líneas 14-16) y pop (líneas 18-20) del Ejemplo PilaH no hacen otra cosa más que encapsular el comportamiento de los métodos insertaAlInicio y eliminaDelInicio respectivamente, los cuales son servicios o comportamiento definidos en la clase Lista del Ejemplo Lista. Note también que es posible acceder a dichos métodos debido a que la clase PilaH hereda de la clase Lista (línea 5).

   Observe que como parte del mecanismo de la herencia, tampoco es necesario definir el comportamiento de los métodos estaVacia e imprime dentro de la clase PilaH, ya que se encuentran definidos en la clase Lista.

   El primero de dichos comportamientos forma parte de la definición de las primitivas de la estructura de datos pila, mientras que el segundo es utilizado en la clase PruebaPilaH del Ejemplo PruebaPilaH (líneas 11 y 20), la cual es la clase de prueba del Ejemplo en cuestión.

La salida del Ejemplo PruebaPilaH se muestra en la siguiente figura:

Salida del Ejemplo PruebaPilaH.

 

    Consideraciones.

   Al menos en apariencia, el mecanismo de la herencia resulta sumamente conveniente con base en lo expuesto con anterioridad; sin embargo, presenta algunos inconvenientes potenciales que vale la pena considerar.

   Las instancias de la clase PilaH, al heredar las características y el comportamiento inherentes a una lista enlazada, pueden hacer uso de los métodos de inserción y de eliminación correspondientes a ésta, por lo que desde esta perspectiva, un objeto de dicha clase podría permitir inserciones y eliminaciones, no únicamente del tope de la pila (representado por inicio), sino también de la base de la pila ("representada" por fin) a la que se supone, por definición de pila, no se debe tener acceso.

   Tome en consideración que todavía se podría transgredir más la definición de una pila, ya que potencialmente es posible también insertar en, o eliminar de cualquier parte de la estructura de datos con las modificaciones correspondientes (vea el Ejercicio 2.2 de los Ejercicios selectos), lo cual queda completamente fuera tanto de la definición que se hizo de la pila, como de las operaciones primitivas que le son inherentes.

Implementación de una pila utilizando composición.

   La implementación de una pila utilizando el enfoque de composición, se basa en la idea de que una lista enlazada contiene ya definidas las operaciones que necesita una pila, pero que también, como se discutió con anterioridad, contiene otras operaciones que no deberían ser utilizadas por la misma.

   En función de lo anterior y de manera conveniente, lo que puede hacerse es encapsular las operaciones de la lista enlazada dentro de las de la pila con la finalidad de proporcionar una interfaz o un conjunto de servicios ad hoc con la definición de la estructura de datos en cuestión: la pila.

Diagrama de clases UML para la implementación de una pila utilizando composición y una lista enlazada.

 

    La figura anterior muestra el diseño en diagrama de clases UML la definición de una pila que utiliza o contiene (has-a) una lista enlazada para su implementación. Observe y compare con detenimiento dicho diagrama con el respectivo diagrama UML para la implementación con herencia, y note que el cambio principal está en la clase PilaC y en la relación entre ésta y la clase Lista.

   Ahora bien, la definición de la clase PilaC se muestra en el Ejemplo PilaC. Insto una vez más al lector a que ponga atención en dos aspectos:

1. La relación entre el diagrama de clases de la figura anterior y el Ejemplo PilaC.
2. Los métodos push (líneas 16-18), pop (líneas 20-22) e imprime (líneas 24-26) no hacen otra cosa más que encapsular de manera conveniente, los mensajes enviados al objeto tope (línea 6), mismos que son llevados a cabo por los métodos correspondientes definidos en la clase Lista.

   Con base en lo anterior, los objetos instanciados de la clase PilaC sólo podrán acceder a los servicios definidos explícitamente en dicha clase y a ningún otro más independientemente de los métodos que posea la clase Lista, lo cuál hace que, desde el punto de vista de la abstracción y la representación de la estructura de datos, el enfoque de la composición sea mucho más conveniente, aunque un poco más laborioso, que el de la herencia. Por otro lado, para implementar una pila utilizando una lista enlazada la cantidad nueva de código se reduce significativamente; sin embargo, si bien es cierto que uno de los enfoques del paradigma orientado a objetos se basa en la reutilización del código, es importante que el lector se haga consciente de estos dos aspectos, ya que cada uno de ellos tiene sus ventajas y desventajas, y la decisión final de implementación debería tomarse con pleno conocimiento de causa, ya que no siempre es mejor tomar el camino más fácil (herencia).

   La clase de prueba del Ejemplo PilaC se muestra en el Ejemplo PruebaPilaC y sigue el mismo mecanismo de inserción que el los ejemplos de prueba anteriores. Finalmente, compruebe que la salida del Ejemplo PruebaPilaC coincide exactamente con la salida correspondiente del Ejemplo PruebaPilaH, y que desde el punto de vista de la ejecución, no podría saberse cuál fue el enfoque de diseño elegido.

Listas (implementación).

   La implementación de una lista enlazada se muestra en el Ejemplo Lista. Note que con base en lo descrito en el diagrama de clases UML de la siguiente figura y a lo definido en el código fuente de dicho ejemplo, se hace uso de las clases NodoG y ExcepcionEDVacia, mismas que ya han sido explicadas y analizadas en entradas anteriores por lo que ya no se presentan ni se describen aquí (si el lector desea una descripción de dichas clases, refiérase a la entrada Pilas (implementación)).

Diagrama de clases UML para una lista enlazada.

 

    Adicionalmente a lo anterior, el Ejemplo Lista muestra la definición de los métodos estaVacia e imprime, los cuales también han sido presentados y descritos en ejemplos anteriores; de hecho, se han reutilizado aquí con toda la intención, ya que el comportamiento representado por ellos cumple con los requerimientos necesarios para una lista enlazada.

   Con base en lo anterior, únicamente se describirán los siguientes métodos:

• insertaAlInicio (líneas 18-23) como su nombre lo indica, el método inserta elementos en la parte referida por inicio.

   Si la estructura de datos está vacía (línea 19), se crea el nodo (objeto) con el elemento correspondiente, el cual será referido tanto por inicio como por fin (línea 20). En caso contrario, se inserta el elemento siguiendo la misma idea que se utilizó para la pila (línea 22).

• insertaAlFinal (líneas 25-32) como su nombre lo indica, el método inserta elementos en la parte referida por fin.

   Si la estructura de datos está vacía (línea 26), se crea el nodo (objeto) con el elemento correspondiente, el cual será referido tanto por inicio como por fin (línea 27; observe que hasta aquí se hace exactamente lo mismo que para el método anterior: insertaAlInicio). En caso contrario, se inserta el elemento siguiendo la misma idea que se utilizó para la cola de espera (líneas 29-30).

• eliminaDelInicio (líneas 34-47) como su nombre lo indica, este método elimina elementos en la parte referida por inicio.

   Si la estructura de datos está vacía (línea 35), se lanza la excepción ExcepcionEDVacia (línea 36). En caso contrario, se procede a la eliminación del elemento de manera análoga a como se hizo para la cola de espera (líneas 38-46).

• eliminaDelFinal (líneas 49-68) como su nombre lo indica, elimina elementos en la parte referida por fin.

   Si la estructura de datos está vacía (línea 50), se lanza la excepción ExcepcionEDVacia (línea 51). En caso contrario, se procede a la eliminación del elemento correspondiente, para ello:

1. Si sólo existe un elemento (línea 56), se actualizan las referencias (línea 57). En caso contrario (línea 58):
2. Se realiza un recorrido (líneas 59-61) por la estructura de datos desde el inicio (línea 59), para determinar el elemento anterior al referido por fin (¿Por qué?).
3. Se actualizan las referencias correspondientes (líneas 63-64).

   La clase de prueba para el Ejemplo Lista se muestra en el Ejemplo PruebaLista. Note que se insertan diez números enteros, y que para los números pares se utiliza el método insertaAlInicio, mientras que para los números impares se utiliza el método insertaAlFinal. Observe también cómo para la eliminación ocurre lo correspondiente.

   Finalmente, la siguiente figura muestra la salida del Ejemplo PruebaLista.

Salida del Ejemplo PruebaLista.

Ejercicios selectos (listas).

Media aritmética (promedio).

Desviación estándar.

Regresión lineal.

Coeficiente de correlación.

1. Modifique el Ejemplo PruebaLista para que permita leer datos (Integer) desde la entrada estándar (teclado).
2. Considerando la definición de una lista enlazada, modifique el Ejemplo Lista para que:
1. Incorpore un atributo privado numérico (n) que lleve el control del número de elementos insertados en la lista enlazada. Al respecto no olvide:
1. Inicializar explícitamente dicho atributo a cero en el constructor.
2. Proporcionar únicamente el método de tipo get para el atributo n: obtenN( ).
2. Considere otras operaciones de inserción para la lista enlazada, como por ejemplo:
1. insertaDespuesDe(e1, e2) inserta al elemento e1 después del elemento e2. Si e1 pudo ser insertado, se debe regresar true para notificar éxito. En caso contrario (quizá el elemento e2 ni siquiera exista dentro de la lista enlazada), se deberá regresar false.
2. insertaAntesDe(e1, e2) inserta al elemento e1 antes del elemento e2. Si e1 pudo ser insertado, se debe regresar true para notificar éxito. En caso contrario (quizá el elemento e2 ni siquiera exista dentro de la lista enlazada) se deberá regresar false.
3. insertaOrdenado(elemento) inserta al elemento en orden ascendente dentro de la lista enlazada.
3. De preferencia genere, como parte de su diseño, el diagrama de clases UML para la nueva definición de la lista enlazada. Puede apoyarse de los diagramas de clases presentados en el blog.
3. Modifique el Ejemplo PruebaLista para que almacene otro tipo de objetos además de los de la clase Integer. Pruebe con al menos las siguientes clases:
1. Double.
2. String.
3. Persona (del Ejemplo Persona).
4. Cientifico (del Ejemplo Cientifico). Revise las consideraciones hechas para el Ejercicio 7 de colas, sobre todo para insertar los elementos de manera ordenada (Ejercicio 2.2.3).
   
4. En el blog (entrada Herencia vs. composición) se hace mención de los inconvenientes de la implementación de una pila por medio de la herencia de una lista enlazada. Compruebe con al menos un ejemplo, la posibilidad de realizar una operación no válida  para una pila. Puede basarse en el Ejemplo PruebaPilaH.
5. Con base en lo descrito en el blog (entrada Herencia vs. composición), realice la implementación de una cola de espera utilizando una lista enlazada. Para lo anterior, siga los enfoques de:
1. Herencia (apóyese del Ejemplo PilaH).
2. Composición (apóyese del Ejemplo PilaC).
6. Respecto al ejercicio anterior, determine sus propias conclusiones respecto al mecanismo de herencia vs. composición para ambos tipos de implementación.
7. Modifique el Ejemplo PruebaPilaH y el Ejemplo PruebaPilaC para realizar las clases de pruebas respectivas del Ejercicio 5. Posteriormente, asegúrese de que es posible almacenar otro tipo de objetos además de los de la clase Integer. Pruebe con al menos las siguientes clases:
1. Double.
2. String.
3. Persona (del Ejemplo Persona).
4. Cientifico (del Ejemplo Cientifico).
8. Con base en la descripción hecha en el blog (entrada Listas circulares) ¿Cuáles son las consideraciones necesarias para la implementación de una lista enlazada circular? ¿Cómo deben hacerse las inserciones? ¿Cómo deben hacerse las eliminaciones? ¿Cuáles serían las operaciones primitivas respecto de una lista simplemente enlazada? ¿Qué otras operaciones, además de las presentadas en el blog se podrían definir? En este sentido, implemente una lista enlazada circular y pruébela, ya que será necesaria para la solución del siguiente ejercicio.
9. Utilice la implementación de la lista enlazada circular del ejercicio anterior para resolver el problema de Josephus descrito en el blog (entrada Listas circulares). Para ello:
1. Considere que existen N soldados (se deberá solicitar y leer). Para cada uno de dichos soldados deberá solicitar su nombre, por lo que se recomienda que la lista enlazada circular almacene objetos de la clase String.
2. En cada iteración (determinación de la eliminación de un soldado), genere un número aleatorio n, donde 0 < n <= N.
3. De manera paralela al almacenamiento de los soldados en la lista enlazada circular, almacene el nombre de los soldados en un arreglo y genere otro número aleatorio m, de tal forma que m sea el índice correspondiente al arreglo de nombres de los soldados, y servirá para elegir al soldado inicial. Tome en cuenta que 0 <= m < N.
10. Con base en la descripción y la definición de una lista doblemente enlazada que se realizó en la entrada Listas doblemente enlazadas y considerando lo descrito en el diagrama de clases UML correspondiente, realice la implementación de una lista doblemente enlazada. Para realizar lo anterior, considere la siguiente descripción para los métodos a implementar:
1. insertaAlInicio(elemento) agrega elemento al inicio de la lista doblemente enlazada.
2. insertaAlFinal(elemento) agrega elemento al fin de la lista doblemente enlazada.
3. eliminaDelInicio( ) elimina un elemento del inicio de la lista doblemente enlazada.
4. eliminaDelFinal( ) elimina un elemento del fin de la lista doblemente enlazada.
5. estaVacia( ) regresa verdadero o falso dependiendo de si la lista doblemente enlazada contiene o no elementos respectivamente.
6. imprime( ) imprime en la salida estándar (pantalla) los elementos de la lista doblemente enlazada.
7. obtenN( ) regresa el número de elementos actualmente almacenados en la lista doblemente enlazada.
8. insertaDespuesDe(e1, e2) inserta al elemento e1 después del elemento e2. Si e1 pudo ser insertado, se debe regresar true para notificar éxito. En caso contrario (quizá el elemento e2 ni siquiera exista dentro de la lista doblemente enlazada), se deberá regresar false.
9. insertaAntesDe(e1, e2) inserta al elemento e1 antes del elemento e2. Si e1 pudo ser insertado se debe regresar true para notificar éxito. En caso contrario (quizá el elemento e2 ni siquiera exista dentro de la lista doblemente enlazada) se deberá regresar false.
10. insertaOrdenado(elemento) inserta al elemento en orden ascendente dentro de la lista doblemente enlazada.
11. Con base en la implementación de la lista doblemente enlazada del ejercicio anterior ¿Qué cambios habría que realizar para la implementación de una lista doblemente enlazada circular?
12. Considere las fórmulas de media aritmética, desviación estándar, regresión lineal y coeficiente de correlación presentadas al inicio de la entrada de ejercicios, donde n es el número de elementos en el conjunto de datos y x e y son elementos del conjunto de datos. Utilizando la implementación de la lista doblemente enlazada del Ejercicio 10, escriba un programa que realice el cálculo de cada una de las formulas mencionadas. Sugerencia: formule cada una de las expresiones como un método dentro de una clase que se llame Formulas.
13. Considere el Ejercicio 6 (Round robin) de la entrada Ejercicios selectos (colas) y la figura que aparece al final de la presente lista de ejercicios. Se tiene una lista enlazada (vertical) con tres nodos y en cada uno de ellos una referencia a una cola de espera representada en dicha figura por inicio. La figura muestra un estado determinado de tres colas de espera con números enteros que representan las cantidades a considerar (quantum). Utilizando cada una de las colas de espera referidas por la lista enlazada, implemente el algoritmo de Round robin por niveles tomando en consideración lo siguiente:
1. La atención de los elementos formados en la cola de espera consiste en restarle uno al quantum del nodo que se encuentra al inicio de la cola, y volverlo a formar al final de la misma para atender de manera análoga a los siguientes nodos. Tome en consideración que, una vez que el número llega a cero, el nodo correspondientes es eliminado.
2. La atención se realiza con base en la prioridad de los elementos de la cola de espera, la cual está representada por los números 1, 2 y 3 de la lista enlazada vertical, donde 3 y 1 son la prioridad más alta y más baja respectivamente. No es posible atender a los elementos formados en un cola de espera cuya prioridad sea menor siempre que existan elementos que necesitan ser atendidos en alguna cola de espera de prioridad mayor.
3. El proceso anteriormente descrito continúa hasta atender o despachar a todos los nodos formados en las tres colas de espera. Para lo anterior, considere:
1. Genere un número aleatorio entre 1 y 3, mismo que representará la prioridad para seleccionar la cola de espera correspondiente (Suponga que salió el 3).
2. Para cada cola de espera, genere un número aleatorio entre 10 y 50, el cual representará el número de nodos que contendrá la cola de espera en cuestión (Si el nuevo número aleatorio es 48 por ejemplo, se tendrán que generar 48 nodos que se formaran en la cola asociada al nivel 3).
3. Por cada nodo, genere nuevamente un número aleatorio entre 1 y 500, mismo que representará el quantum asignado a cada nodo.
4. No olvide construir también una clase de prueba para su implementación. La salida de su programa puede ser en la salida estándar o en un archivo de texto.
5. Quizá pueda resultar útil al lector revisar el siguiente Ejemplo de implementación de una lista de listas como apoyo para la generación de su propio diseño en la resolución de este interesante problema.
   

Representación de Round robin por niveles de prioridad.