Estructuras de datos y algoritmos en Java

1. El Propósito Fundamental: Software Robusto, Adaptable y Reutilizable

Las implementaciones de software deben alcanzar robustez, adaptabilidad y reutilización.

Los objetivos definitivos. En el núcleo del diseño de estructuras de datos y algoritmos reside la búsqueda de la excelencia en ingeniería de software. Aspiramos a soluciones que no solo funcionen, sino que encarnen tres cualidades críticas: robustez, para manejar con gracia entradas inesperadas; adaptabilidad, que permita evolucionar con requisitos cambiantes; y reutilización, que posibilite que los componentes sirvan en aplicaciones diversas. Estos principios guían cada decisión de diseño, desde el arreglo más simple hasta el árbol más complejo.

Principios orientados a objetos. Alcanzar estos objetivos se facilita enormemente con los principios del diseño orientado a objetos:

• Abstracción: Destilar sistemas complejos a sus partes fundamentales, a menudo expresadas como Tipos Abstractos de Datos (TAD) o interfaces en Java.
• Encapsulación: Ocultar detalles internos de implementación, proteger la integridad de los datos y permitir cambios internos sin afectar a los usuarios externos.
• Modularidad: Dividir sistemas en unidades funcionales separadas y bien organizadas, simplificando pruebas y depuración.
  Estos principios, combinados con patrones de diseño, ofrecen un marco poderoso para construir software de alta calidad.

Patrones de diseño como plantillas. Los patrones de diseño brindan soluciones probadas a problemas comunes en el diseño de software, actuando como plantillas reutilizables. Proporcionan un vocabulario y estructura compartidos para abordar desafíos recurrentes, ya sea en diseño de algoritmos (como recursión o divide y vencerás) o en ingeniería de software (como adaptador o método fábrica). Al aprovechar estos patrones, podemos crear código más elegante, eficiente y mantenible.

2. Los Pilares de Java: Objetos, Clases y Estructuras Fundamentales

Existe una distinción importante en Java entre el tratamiento de variables de tipo base y variables de tipo clase.

La base de Java. Comprender la sintaxis central de Java es fundamental. Esto incluye tipos básicos como int, boolean y char, y el concepto crucial de clases y objetos. Los objetos son instancias de clases, que funcionan como planos que definen datos (variables de instancia) y comportamientos (métodos). Las variables de tipo clase son referencias, es decir, almacenan direcciones de memoria, permitiendo que múltiples variables apunten al mismo objeto.

Arreglos y cadenas. Los arreglos ofrecen colecciones ordenadas e indexadas de elementos del mismo tipo, con acceso directo a elementos mediante a[k]. La clase String de Java representa secuencias de caracteres inmutables, mientras que StringBuilder ofrece una alternativa mutable para manipulación eficiente de texto. Los tipos envoltorio (wrapper) conectan los tipos primitivos con objetos, permitiendo su uso en colecciones genéricas.

Características orientadas a objetos. Las características orientadas a objetos de Java van más allá de las clases básicas. La herencia permite que nuevas clases (subclases) extiendan otras existentes (superclases), fomentando la reutilización y especialización del código. Las interfaces definen contratos de comportamiento, mientras que las clases abstractas ofrecen implementaciones parciales, promoviendo diseños flexibles y extensibles. Las excepciones manejan eventos inesperados, y los genéricos permiten escribir código que funciona con diversos tipos de datos de forma segura.

3. Dominando el Análisis de Algoritmos: El Lenguaje de la Eficiencia

La herramienta principal de análisis que usaremos en este libro consiste en caracterizar los tiempos de ejecución de algoritmos y operaciones sobre estructuras de datos, siendo también relevante el uso de espacio.

Más allá de los experimentos. Aunque los estudios experimentales ofrecen perspectivas prácticas sobre el rendimiento de algoritmos, están limitados por hardware, software y entradas específicas. Un enfoque más sólido es el análisis teórico de algoritmos, que cuenta operaciones primitivas en función del tamaño de entrada n. Este método proporciona una forma independiente de máquina para comparar algoritmos y predecir su comportamiento para todas las entradas posibles, enfocándose en los peores casos para garantías sólidas.

La notación Big-Oh. El análisis asintótico, especialmente la notación "Big-Oh" (O(g(n))), nos permite caracterizar la tasa de crecimiento de un algoritmo ignorando factores constantes y términos de menor orden. Esto simplifica comparaciones, centrándose en el término dominante que dicta el rendimiento para entradas grandes. Por ejemplo, 5n^2 + 3n log n + 2n + 5 es O(n^2).

Siete funciones clave. La mayoría de los algoritmos pueden caracterizarse por una de siete funciones fundamentales:

• O(1): Tiempo constante (p. ej., acceso a arreglo)
• O(log n): Tiempo logarítmico (p. ej., búsqueda binaria)
• O(n): Tiempo lineal (p. ej., recorrido de arreglo)
• O(n log n): Tiempo n-log-n (p. ej., ordenamiento eficiente)
• O(n^2): Tiempo cuadrático (p. ej., bucles anidados)
• O(n^3): Tiempo cúbico (p. ej., multiplicación de matrices)
• O(a^n): Tiempo exponencial (p. ej., búsqueda exhaustiva)
  Comprender estas tasas de crecimiento es crucial para elegir algoritmos eficientes, pues incluso un crecimiento asintótico ligeramente más rápido puede conducir a un rendimiento dramáticamente peor para entradas grandes.

4. Recursión: Soluciones Elegantes, Diseño Cuidadoso

La recursión es una técnica mediante la cual un método se llama a sí mismo una o más veces durante su ejecución, o mediante la cual una estructura de datos se basa en instancias más pequeñas del mismo tipo en su representación.

El poder de la autorreferencia. La recursión ofrece una alternativa elegante y poderosa a los bucles para tareas repetitivas. Consiste en que un método se llame a sí mismo, resolviendo en cada llamada una instancia más pequeña del mismo problema hasta alcanzar un caso base. Este enfoque simplifica lógicas complejas, como en ejemplos de cálculo de factoriales, dibujo de reglas inglesas o recorrido de sistemas de archivos.

Análisis de algoritmos recursivos. La eficiencia de algoritmos recursivos se analiza sumando el trabajo realizado en cada nivel de la recursión. Por ejemplo, la búsqueda binaria, a pesar de su nombre "binaria", es una recursión lineal (cada llamada hace a lo sumo una llamada recursiva) que se ejecuta en tiempo O(log n) porque el tamaño del problema se reduce a la mitad en cada paso. La profundidad de la recursión impacta directamente el uso de memoria, ya que cada llamada añade un marco a la pila de métodos de Java.

Peligros y optimizaciones. Aunque elegante, la recursión puede usarse incorrectamente. Definiciones recursivas ineficientes, como una implementación ingenua de Fibonacci, pueden llevar a complejidad exponencial por cálculos redundantes. La recursión infinita, donde no se alcanza un caso base, provoca un StackOverflowError. La recursión de cola, donde la llamada recursiva es la última operación, puede ser optimizada por compiladores en bucles iterativos, eliminando la sobrecarga de pila.

5. Estructuras de Datos Lineales: Pilas, Colas y Listas

Una pila es una colección de objetos que se insertan y eliminan según el principio último en entrar, primero en salir (LIFO).

TAD lineales fundamentales. Pilas, colas y colas dobles son estructuras de datos lineales fundamentales, cada una definida por reglas específicas para inserción y eliminación de elementos.

• Pila (LIFO): push(e) añade al tope, pop() elimina del tope. Usada en mecanismos de deshacer, historial de navegadores y evaluación de expresiones.
• Cola (FIFO): enqueue(e) añade al final, dequeue() elimina del frente. Usada en planificación de tareas, colas de impresión y atención al cliente.
• Cola doble (Deque): Permite inserciones y eliminaciones tanto al frente como al final. Más versátil, puede emular pilas y colas.

Opciones de implementación. Estos TAD pueden implementarse eficientemente usando arreglos o listas enlazadas.

• Basadas en arreglos: Simples y O(1) para la mayoría de operaciones, pero suelen requerir capacidad fija. Los arreglos dinámicos (como ArrayList) superan esto redimensionando, con costo O(N) para redimensionar pero tiempo amortizado O(1) para inserciones.
• Basadas en listas enlazadas: Capacidad flexible, O(1) para la mayoría de operaciones (especialmente en extremos), pero usan más memoria por elemento debido a punteros. Las listas doblemente enlazadas son ideales para colas dobles, permitiendo operaciones O(1) en ambos extremos.

Compensaciones y aplicaciones. La elección de implementación depende de las necesidades de la aplicación. Arreglos de capacidad fija son rápidos si el tamaño es conocido. Arreglos dinámicos ofrecen flexibilidad. Las listas enlazadas son mejores cuando hay inserciones/eliminaciones frecuentes en posiciones arbitrarias o cuando el tamaño es muy impredecible. Las aplicaciones van desde invertir arreglos hasta emparejar paréntesis y etiquetas HTML, e incluso resolver el problema de José con colas circulares.

6. Árboles: Organizando Datos Jerárquicamente

Un árbol es un tipo abstracto de datos que almacena elementos de forma jerárquica.

Relaciones jerárquicas. Los árboles son estructuras de datos no lineales poderosas que representan relaciones jerárquicas, como árboles genealógicos, sistemas de archivos o organigramas. Consisten en nodos, con un nodo raíz especial, y relaciones padre-hijo. Terminología clave incluye:

• Raíz: El nodo superior sin padre.
• Nodo interno: Nodo con uno o más hijos.
• Nodo externo (hoja): Nodo sin hijos.
• Profundidad: Distancia desde la raíz.
• Altura: Profundidad máxima de cualquier nodo.

Árboles generales vs. binarios.

• Árboles generales: Los nodos pueden tener un número arbitrario de hijos.
• Árboles binarios: Cada nodo tiene a lo sumo dos hijos (izquierdo y derecho). Se usan a menudo para árboles de decisión o expresiones aritméticas. Un árbol binario propio tiene cada nodo interno con exactamente dos hijos.

Recorridos de árboles. Formas sistemáticas de visitar todos los nodos:

• Preorden: Visitar raíz, luego recorrer recursivamente hijos (p. ej., índice de contenidos).
• Postorden: Recorrer recursivamente hijos, luego visitar raíz (p. ej., cálculo de espacio en disco).
• Inorden (solo árboles binarios): Recorrer hijo izquierdo, visitar raíz, recorrer hijo derecho (p. ej., ordenar elementos en árbol binario de búsqueda).
• Búsqueda en anchura (BFS): Visitar nodos nivel por nivel (p. ej., árboles de juego).
  Estos recorridos típicamente se ejecutan en tiempo O(N), donde N es el número de nodos.

7. Colas de Prioridad: Gestionando Elementos por Importancia

Una cola de prioridad es una colección de elementos priorizados que permite inserción arbitraria y la eliminación del elemento con la máxima prioridad.

Más allá de FIFO. A diferencia de las colas estándar, las colas de prioridad gestionan elementos según una "clave" asociada que define su prioridad. La operación removeMin() extrae siempre el elemento con la clave más pequeña. Esto es crucial en aplicaciones donde el orden de procesamiento no es estrictamente cronológico, como:

• Control de tráfico aéreo (priorizando aterrizajes)
• Planificación de tareas en sistemas operativos
• Gestión de eventos en simulaciones

Entradas clave-valor y comparadores. Los elementos se almacenan como pares (clave, valor), llamados entradas. Las claves deben definir un orden total, que puede lograrse mediante la interfaz Comparable de Java (orden natural) o un objeto Comparator personalizado. Esta flexibilidad permite definir diversas nociones de "prioridad".

Implementación basada en montículos. La implementación más eficiente usa un montículo binario, un árbol binario completo que satisface la propiedad de orden de montículo (clave del padre ≤ claves de los hijos).

• insert(k, v): Añade en la siguiente posición disponible, luego "burbujea hacia arriba" para restaurar el orden. Tiempo O(log n).
• removeMin(): Reemplaza la raíz con el último elemento, luego "burbujea hacia abajo" para restaurar el orden. Tiempo O(log n).
• min(): Simplemente devuelve la raíz. Tiempo O(1).
  Los montículos garantizan rendimiento O(log n) para inserciones y eliminaciones, una mejora significativa sobre O(n) en colas de prioridad basadas en listas. La construcción de montículo de abajo hacia arriba puede incluso construir un montículo en tiempo O(n) a partir de un conjunto inicial de elementos.

8. Mapas y Tablas Hash: Búsquedas Rápidas Clave-Valor

El concepto novedoso de una tabla hash es el uso de una función hash para mapear claves generales a índices correspondientes en una tabla.

Arreglos asociativos. Los mapas almacenan entradas (clave, valor), donde las claves son identificadores únicos para recuperar valores. También se conocen como arreglos asociativos porque las claves actúan como índices, pero pueden no ser numéricas. Las aplicaciones van desde búsquedas DNS hasta autenticación de usuarios.

Tablas hash para velocidad. Las tablas hash son implementaciones de mapas altamente eficientes. Usan una función hash para convertir una clave en un índice entero (valor hash) para un arreglo de cubetas. Este proceso implica:

• Código hash: Mapea la clave a un entero (p. ej., código hash polinomial para cadenas).
• Función de compresión: Mapea el código hash a un índice dentro de la capacidad del arreglo (p. ej., método de división i mod N, o método MAD [(ai + b) mod p] mod N).

Manejo de colisiones. Cuando diferentes claves mapean al mismo índice (colisión), se requieren estrategias:

• Encadenamiento separado: Cada cubeta almacena una estructura secundaria (p. ej., un ArrayList o UnsortedTableMap) que contiene todas las entradas colisionantes.
• Dirección abierta: Las entradas se almacenan directamente en el arreglo, buscando la siguiente ranura disponible (p. ej., sondeo lineal, cuadrático, doble hashing).
  Con una buena función hash y manejo adecuado del factor de carga (redimensionando la tabla cuando se llena demasiado), las tablas hash ofrecen tiempo esperado O(1) para operaciones get, put y remove.

9. Árboles de Búsqueda Balanceados: Garantizando Rendimiento Logarítmico

La eficiencia de un árbol binario de búsqueda T es, por tanto, una implementación eficiente de un mapa con n entradas solo si su altura es pequeña.

El dilema del árbol de búsqueda. Los árboles binarios de búsqueda (BST) organizan entradas del mapa por clave, permitiendo búsquedas, inserciones y eliminaciones en tiempo O(h), donde h es la altura del árbol. Sin embargo, en el peor caso (p. ej., insertar claves ordenadas), h puede ser O(n), degradando el rendimiento a O(n). Los árboles balanceados superan esto manteniendo h = O(log n), garantizando rendimiento O(log n) en el peor caso.

Rebalanceo con rotaciones. La operación central de rebalanceo es una rotación, que remodela localmente el árbol en tiempo O(1) mientras preserva la propiedad BST. El rebalanceo complejo suele involucrar una reestructuración de trino, que combina una o dos rotaciones para corregir desequilibrios que involucran un nodo, su padre y su abuelo.

Tipos clave de árboles balanceados:

• Árboles AVL: Mantienen una propiedad de balance de altura (las alturas de los hijos difieren a lo sumo en 1). Inserciones y eliminaciones pueden desencadenar rotaciones O(log n) para restaurar el balance.
• Árboles Splay: No almacenan información explícita de balance. Tras cada acceso, inserción o eliminación, el nodo accedido se "splayea" (mueve a la raíz) usando secuencias de rotaciones zig-zig, zig-zag o zig. Esto proporciona rendimiento amortizado O(log n).
• Árboles (2,4): Árboles de búsqueda multiway donde los nodos internos tienen 2, 3 o 4 hijos. Todas las hojas están a la misma profundidad. Inserciones y eliminaciones implican "divisiones" o "fusiones" que se propagan hacia arriba, manteniendo el balance.
• Árboles Rojo-Negro: Árboles binarios de búsqueda con nodos coloreados rojo o negro, que satisfacen propiedades específicas (p. ej., no hay dos nodos rojos adyacentes, todos los caminos de raíz a hoja tienen igual número de nodos negros). Estas propiedades aseguran altura O(log n) y cambios estructurales O(1) (rotaciones) por actualización, con recoloreos O(log n).

10. Ordenamiento: La Tarea Fundamental de Organizar Datos

El tiempo de ejecución de cualquier algoritmo basado en comparaciones para ordenar una secuencia de n elementos es Ω(n log n) en el peor caso.

El imperativo del ordenamiento. Ordenar es una tarea fundamental, que