B2-T3: ESTRUCTURAS DE DATOS, ALGORITMOS Y FICHEROS
Tema fundamental y muy preguntado. Las complejidades de los algoritmos de ordenación son casi fijas en el examen TAI. Los árboles binarios de búsqueda (BST), los AVL y los B/B+ son recurrentes. También preguntan sobre recorridos de grafos (DFS/BFS) y organización de ficheros (secuencial, indexado, hash). Memoriza las tablas comparativas de complejidad.
COMPLEJIDAD ALGORÍTMICA
Notación asintótica
La notación Big O describe el comportamiento asintótico del tiempo (o espacio) de ejecución de un algoritmo en función del tamaño de la entrada n. Se usa para analizar el peor caso.
| Notación | Significado | Uso |
|---|
| O(f(n)) — Big O | Cota superior asintótica (peor caso) | La más usada. "A lo sumo" crece como f(n) |
| Ω(f(n)) — Omega | Cota inferior asintótica (mejor caso) | "Al menos" crece como f(n) |
| Θ(f(n)) — Theta | Cota ajustada (mejor y peor coinciden) | Complejidad exacta asintótica |
| o(f(n)) — Little-o | Estrictamente menor que f(n) | Crece más lento que f(n) |
Órdenes de complejidad (de mejor a peor)
| Complejidad | Nombre | Ejemplo para n=1.000 | Ejemplo de algoritmo |
|---|
| O(1) | Constante | 1 | Acceso a array por índice, hash table lookup |
| O(log n) | Logarítmica | ~10 | Búsqueda binaria, operaciones en árboles balanceados |
| O(n) | Lineal | 1.000 | Búsqueda secuencial, recorrido de lista |
| O(n log n) | Lineal-logarítmica | ~10.000 | Mergesort, Heapsort, Quicksort (promedio) |
| O(n²) | Cuadrática | 1.000.000 | Bubble sort, Insertion sort (peor caso) |
| O(n³) | Cúbica | 10⁹ | Multiplicación de matrices naive, Floyd-Warshall |
| O(2ⁿ) | Exponencial | ~10³⁰¹ | Subconjuntos, fuerza bruta combinatoria |
| O(n!) | Factorial | Astronómica | Permutaciones, TSP por fuerza bruta |
Regla clave: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!). Un algoritmo O(n log n) es generalmente óptimo para ordenación por comparación (demostrado como cota inferior teórica).
ESTRUCTURAS DE DATOS LINEALES
Arrays (vectores y matrices)
| Característica | Descripción |
|---|
| Definición | Colección de elementos del mismo tipo almacenados en posiciones contiguas de memoria |
| Acceso | O(1) — acceso directo por índice (base + desplazamiento) |
| Búsqueda | O(n) secuencial; O(log n) si está ordenado (búsqueda binaria) |
| Inserción/eliminación | O(n) — requiere desplazar elementos |
| Tamaño | Fijo en tiempo de compilación (estático) o dinámico (con reasignación) |
| Ventaja | Acceso rápido, buen uso de caché (localidad espacial) |
| Desventaja | Tamaño fijo, inserción/eliminación costosas |
Listas enlazadas
| Tipo | Estructura | Navegación | Uso típico |
|---|
| Simple (singly linked) | Nodo → [dato | siguiente] | Solo hacia adelante | Pilas, colas simples |
| Doble (doubly linked) | ← [anterior | dato | siguiente] → | Bidireccional | Navegación adelante/atrás, editores de texto |
| Circular | El último nodo apunta al primero | Cíclica | Buffers circulares, round-robin |
| Operación | Lista enlazada | Array |
|---|
| Acceso por índice | O(n) | O(1) |
| Inserción al inicio | O(1) | O(n) |
| Inserción al final | O(n) / O(1) con puntero al final | O(1) amortizado |
| Eliminación | O(1) si tenemos referencia al nodo | O(n) (desplazar) |
| Búsqueda | O(n) | O(n) / O(log n) ordenado |
| Uso de memoria | Overhead por punteros | Compacto, buena localidad de caché |
Pilas (stacks)
| Propiedad | Descripción |
|---|
| Disciplina | LIFO (Last In, First Out) — el último en entrar es el primero en salir |
| Operaciones | push (apilar), pop (desapilar), peek/top (ver tope sin extraer) |
| Complejidad | push, pop y peek: O(1) |
| Implementación | Array (puntero al tope) o lista enlazada simple |
| Aplicaciones | Pila de llamadas a funciones (call stack), evaluación de expresiones postfijas, undo/redo, parsers, verificación de paréntesis balanceados, backtracking, DFS iterativo |
Colas (queues)
| Tipo | Disciplina | Operaciones | Aplicación |
|---|
| Cola simple | FIFO (First In, First Out) | enqueue (encolar), dequeue (desencolar) | Buffers de impresión, planificación de procesos |
| Cola de prioridad | Sale primero el de mayor (o menor) prioridad | insert, extractMin/Max | Dijkstra, planificación de tareas, heaps |
| Cola doble (deque) | Inserción/extracción por ambos extremos | pushFront, pushBack, popFront, popBack | Sliding window, palíndromos |
| Cola circular | FIFO con buffer circular (array) | Índices front/rear con módulo | Buffers de E/S, colas de tamaño fijo |
Examen: Pila = LIFO. Cola = FIFO. Las colas de prioridad se implementan típicamente con un heap binario (insert y extract en O(log n)). No confundir cola de prioridad con cola ordenada — la cola de prioridad no mantiene todos los elementos ordenados, solo garantiza el máximo/mínimo.
ESTRUCTURAS DE DATOS NO LINEALES
Árboles: conceptos fundamentales
| Término | Definición |
|---|
| Raíz | Nodo sin padre (parte superior del árbol) |
| Hoja | Nodo sin hijos (nodo terminal) |
| Nodo interno | Nodo con al menos un hijo |
| Profundidad de un nodo | Número de aristas desde la raíz hasta ese nodo |
| Altura del árbol | Máxima profundidad entre todas las hojas |
| Grado de un nodo | Número de hijos directos |
| Grado del árbol | Máximo grado entre todos los nodos |
| Subárbol | Árbol formado por un nodo y todos sus descendientes |
| Bosque | Conjunto de árboles disjuntos |
Tipos de árboles
| Tipo | Descripción | Altura | Uso |
|---|
| Árbol binario | Cada nodo tiene máximo 2 hijos (izquierdo/derecho) | Variable | Base para BST, heaps, expresiones |
| BST (Binary Search Tree) | Izq < raíz < der para todo nodo | O(n) peor, O(log n) promedio | Diccionarios, conjuntos |
| AVL | BST autobalanceado: |h(izq) - h(der)| ≤ 1 | O(log n) garantizado | Búsqueda frecuente |
| Rojo-Negro | BST autobalanceado con nodos rojo/negro y reglas de color | O(log n) (menos estricto que AVL) | Librerías estándar (TreeMap, std::map) |
| Heap binario | Árbol binario completo; padre ≥ hijos (max-heap) o ≤ (min-heap) | O(log n) | Colas de prioridad, Heapsort |
| Árbol B | Generalización balanceada: nodo con m claves y m+1 hijos | O(log n) con base alta | Índices de BBDD, sistemas de ficheros |
| Árbol B+ | Datos SOLO en hojas (nodos internos = solo claves). Hojas enlazadas para búsquedas de rango. Clave: Árbol B tiene datos en todos los nodos; Árbol B+ solo en hojas | O(log n) | Índices en BBDD (MySQL InnoDB, PostgreSQL) |
| Trie (prefix tree) | Cada arista representa un carácter; nodos compartidos por prefijo | O(longitud de la clave) | Autocompletado, diccionarios, routing IP |
Examen: En un AVL, si la diferencia de alturas supera 1, se rebalancean con rotaciones (simple o doble, izquierda o derecha). En un B-tree de orden m, cada nodo interno tiene entre ⌈m/2⌉ y m hijos. El B+ es el preferido en BBDD porque las hojas enlazadas permiten recorridos secuenciales eficientes (range scans).
Rotaciones AVL
| Caso de desbalanceo | Rotación | Descripción |
|---|
| Izquierda-Izquierda (LL) | Rotación simple a la derecha | El subárbol izquierdo del hijo izquierdo causó el desbalanceo |
| Derecha-Derecha (RR) | Rotación simple a la izquierda | El subárbol derecho del hijo derecho causó el desbalanceo |
| Izquierda-Derecha (LR) | Rotación doble: izquierda + derecha | Primero rota el hijo izquierdo a la izquierda, luego la raíz a la derecha |
| Derecha-Izquierda (RL) | Rotación doble: derecha + izquierda | Primero rota el hijo derecho a la derecha, luego la raíz a la izquierda |
Recorridos de árboles binarios
| Recorrido | Orden de visita | Aplicación |
|---|
| Preorden (NID) | Nodo → Izquierdo → Derecho | Copiar/serializar el árbol, expresiones prefijas |
| Inorden (IND) | Izquierdo → Nodo → Derecho | Obtener elementos ordenados en un BST |
| Postorden (IDN) | Izquierdo → Derecho → Nodo | Liberar memoria, evaluación de expresiones postfijas |
| Por niveles (BFS) | Nivel 0, nivel 1, nivel 2… | Impresión por niveles, búsqueda en anchura |
Examen: El recorrido inorden de un BST produce los elementos en orden ascendente. Es la forma más directa de verificar si un árbol binario es un BST válido.
Grafos
Un grafo G = (V, E) consta de un conjunto de vértices (V) y un conjunto de aristas (E) que conectan pares de vértices.
| Tipo | Descripción |
|---|
| Dirigido (digrafo) | Las aristas tienen dirección (A → B ≠ B → A) |
| No dirigido | Las aristas no tienen dirección (A — B = B — A) |
| Ponderado | Las aristas tienen un peso/coste asociado |
| Conexo | Existe camino entre cualquier par de vértices |
| Acíclico | No contiene ciclos |
| DAG | Directed Acyclic Graph — dirigido sin ciclos |
| Completo | Cada vértice está conectado con todos los demás (n(n-1)/2 aristas) |
| Bipartito | Vértices divisibles en dos grupos sin aristas internas |
| Árbol | Grafo conexo acíclico (n vértices, n-1 aristas) |
Representación de grafos
| Representación | Espacio | Comprobar arista | Listar vecinos | Mejor para |
|---|
| Matriz de adyacencia | O(V²) | O(1) | O(V) | Grafos densos (muchas aristas) |
| Lista de adyacencia | O(V + E) | O(grado) | O(grado) | Grafos dispersos (pocas aristas) |
| Matriz de incidencia | O(V × E) | O(E) | O(E) | Análisis matemático de grafos |
Algoritmos fundamentales de grafos
| Algoritmo | Tipo | Complejidad | Descripción |
|---|
| BFS (Breadth-First Search) | Recorrido en anchura | O(V + E) | Usa cola (FIFO). Encuentra camino más corto en grafos no ponderados |
| DFS (Depth-First Search) | Recorrido en profundidad | O(V + E) | Usa pila (LIFO) o recursión. Detecta ciclos, ordenación topológica |
| Dijkstra | Camino más corto (origen único) | O((V + E) log V) con heap | Pesos no negativos. Usa cola de prioridad (min-heap) |
| Bellman-Ford | Camino más corto (origen único) | O(V × E) | Acepta pesos negativos. Detecta ciclos negativos |
| Floyd-Warshall | Camino más corto (todos los pares) | O(V³) | Programación dinámica. Acepta pesos negativos |
| Kruskal | Árbol de expansión mínima (MST) | O(E log E) | Ordena aristas por peso, usa Union-Find. Grafo disperso |
| Prim | Árbol de expansión mínima (MST) | O((V + E) log V) con heap | Crece el árbol desde un vértice. Grafo denso |
| Ordenación topológica | Orden lineal de DAG | O(V + E) | Basado en DFS o algoritmo de Kahn. Scheduling de tareas |
Examen: BFS usa cola, DFS usa pila — pregunta clásica. Dijkstra NO funciona con pesos negativos (usar Bellman-Ford). Floyd-Warshall es para TODOS los pares de caminos más cortos. MST: Kruskal ordena aristas (bueno para dispersos), Prim crece desde un vértice (bueno para densos).
TABLAS HASH
Concepto y operaciones
Una tabla hash (hash table / hash map) es una estructura que asocia claves a valores usando una función hash que mapea la clave a una posición del array subyacente.
| Operación | Caso promedio | Peor caso |
|---|
| Búsqueda | O(1) | O(n) (todas las claves colisionan) |
| Inserción | O(1) | O(n) |
| Eliminación | O(1) | O(n) |
Resolución de colisiones
| Método | Descripción | Ventaja | Desventaja |
|---|
| Encadenamiento (chaining) | Cada posición del array es una lista enlazada con todos los elementos que colisionan | Simple, funciona bien con alto factor de carga | Uso de memoria extra para punteros |
| Direccionamiento abierto — Sondeo lineal | Si la posición h(k) está ocupada, probar h(k)+1, h(k)+2, … | Buena localidad de caché | Clustering primario (agrupamiento) |
| Direccionamiento abierto — Sondeo cuadrático | Probar h(k)+1², h(k)+2², h(k)+3², … | Reduce clustering primario | Clustering secundario, no garantiza cobertura total |
| Doble hashing | Usar segunda función hash: h(k) + i × h₂(k) | Distribuye mejor las colisiones | Requiere dos funciones hash buenas |
El factor de carga (α) = nº elementos / tamaño tabla. Con encadenamiento, rendimiento se degrada gradualmente. Con direccionamiento abierto, se recomienda α < 0.7. Cuando se supera el umbral, se hace rehashing: se crea una tabla más grande (típicamente 2×) y se reinsertan todos los elementos.
Funciones hash comunes
| Función | Descripción | Uso |
|---|
| Módulo | h(k) = k mod m (m primo ideal) | Hash de enteros, base de muchas implementaciones |
| Multiplicación | h(k) = ⌊m × (k × A mod 1)⌋ (0 < A < 1) | Distribución más uniforme que módulo |
| Hash de cadenas | Polinómica: h = Σ(s[i] × p^i) mod m | Strings, claves alfanuméricas |
ALGORITMOS DE ORDENACIÓN
Comparativa de algoritmos de ordenación
| Algoritmo | Mejor caso | Caso medio | Peor caso | Espacio | Estable | Método |
|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Sí | Intercambio |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | Selección |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Sí | Inserción |
| Shell Sort | O(n log n) | Depende de gaps | O(n²) – O(n^1.5) | O(1) | No | Inserción con gaps |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Sí | Divide y vencerás |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Divide y vencerás (partición) |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Selección con heap |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Sí | No comparativo (conteo) |
| Radix Sort | O(d × (n + k)) | O(d × (n + k)) | O(d × (n + k)) | O(n + k) | Sí | No comparativo (dígito a dígito) |
| Bucket Sort | O(n + k) | O(n + k) | O(n²) | O(n + k) | Sí | No comparativo (distribución) |
Detalles de los principales algoritmos
| Algoritmo | Cómo funciona | Cuándo usarlo |
|---|
| Bubble Sort | Compara pares adyacentes y los intercambia si están desordenados. Repite pasadas hasta que no haya intercambios | Solo educativo — ineficiente para cualquier uso real |
| Insertion Sort | Inserta cada elemento en su posición correcta dentro de la porción ya ordenada | Arrays pequeños (<20 elementos) o casi ordenados |
| Merge Sort | Divide el array en mitades recursivamente, ordena cada mitad y fusiona (merge) las mitades ordenadas | Cuando se necesita estabilidad y rendimiento garantizado O(n log n) |
| Quick Sort | Elige un pivote, particiona el array en menores/mayores que el pivote, y ordena recursivamente | Uso general — el más rápido en práctica (buena localidad de caché) |
| Heap Sort | Construye un max-heap y extrae sucesivamente el máximo | Cuando se necesita O(n log n) garantizado sin memoria extra |
| Counting Sort | Cuenta ocurrencias de cada valor y reconstruye el array ordenado | Enteros en un rango pequeño [0, k] con k = O(n) |
| Radix Sort | Ordena dígito a dígito (LSD o MSD) usando un sort estable (counting) como subrutina | Enteros/strings de longitud fija, d dígitos |
Examen: Los algoritmos no comparativos (counting, radix, bucket) pueden romper la barrera O(n log n) pero solo funcionan con datos de tipo específico. Quick Sort es el más usado en la práctica (stdlib de C usa una variante). Merge Sort es el preferido para listas enlazadas (no necesita acceso aleatorio). Un algoritmo es estable si mantiene el orden relativo de elementos con claves iguales.
ALGORITMOS DE BÚSQUEDA
| Algoritmo | Requisito | Complejidad | Descripción |
|---|
| Búsqueda secuencial | Ninguno | O(n) | Recorre uno a uno hasta encontrar o llegar al final |
| Búsqueda binaria | Array ordenado | O(log n) | Divide el espacio de búsqueda a la mitad en cada paso |
| Búsqueda por interpolación | Array ordenado, distribución uniforme | O(log log n) promedio | Estima la posición proporcional al valor buscado |
| Búsqueda hash | Tabla hash construida | O(1) promedio | Aplica función hash a la clave |
| Búsqueda en árbol (BST) | BST construido | O(log n) promedio, O(n) peor | Compara con raíz y desciende izquierda/derecha |
| Búsqueda en árbol balanceado | AVL / Red-Black | O(log n) garantizado | Igual que BST pero con altura garantizada |
RECURSIVIDAD Y TÉCNICAS ALGORÍTMICAS
Recursividad
| Concepto | Descripción |
|---|
| Definición | Función que se llama a sí misma con un subproblema más pequeño |
| Caso base | Condición de parada que evita recursión infinita |
| Caso recursivo | Llamada a sí misma con entrada reducida |
| Pila de llamadas | Cada llamada recursiva añade un frame al call stack (riesgo de stack overflow) |
| Tail recursion | La llamada recursiva es la última operación — el compilador puede optimizarla a un bucle |
Paradigmas algorítmicos
| Paradigma | Descripción | Ejemplo clásico |
|---|
| Fuerza bruta | Probar todas las soluciones posibles | Búsqueda secuencial, TSP exhaustivo |
| Divide y vencerás | Dividir el problema en subproblemas, resolver recursivamente, combinar resultados | Merge sort, Quick sort, búsqueda binaria |
| Programación dinámica | Resolver subproblemas solapados una sola vez, almacenando resultados (memoización/tabulación) | Fibonacci, mochila (knapsack), Floyd-Warshall, LCS |
| Algoritmos voraces (greedy) | Elegir siempre la opción localmente óptima, sin retroceder | Dijkstra, Kruskal, Prim, Huffman |
| Backtracking | Exploración sistemática con retroceso cuando se detecta camino sin salida | N-reinas, sudoku, laberintos |
| Branch and Bound | Backtracking con poda basada en cotas (bound) del coste | TSP, problema de asignación |
Examen: Divide y vencerás → subproblemas independientes. Programación dinámica → subproblemas solapados (se repiten). La clave de la PD es que almacena resultados intermedios para no recalcularlos. Greedy no garantiza óptimo global en general, pero sí en casos específicos (Dijkstra, Huffman).
ORGANIZACIÓN DE FICHEROS
Tipos de organización
| Organización | Acceso | Descripción | Ventaja | Desventaja |
|---|
| Secuencial | Secuencial | Registros almacenados uno tras otro en el orden de inserción | Simple, eficiente para procesamiento por lotes | Búsqueda lenta O(n), inserción al final |
| Secuencial indexado (ISAM) | Secuencial + directo | Fichero ordenado por clave + índice con punteros a bloques | Búsqueda O(log n) por índice, recorrido secuencial eficiente | Degradación con inserciones (overflow) |
| Indexado | Directo por índice | Índice completo (una entrada por registro) o disperso | Búsqueda rápida, múltiples índices posibles | Overhead de mantener índices |
| Directo / Hash | Directo | Posición calculada mediante función hash sobre la clave | Acceso O(1) promedio | Colisiones, no soporta recorrido ordenado |
| Relativo (direccionamiento relativo) | Directo | Acceso por número de registro relativo (RRN) | Acceso directo O(1) sin función hash | Requiere conocer el RRN |
Índices en bases de datos
| Tipo de índice | Estructura | Descripción |
|---|
| Índice primario | Árbol B+ | Sobre la clave primaria; el fichero está ordenado físicamente por esa clave (índice clustered) |
| Índice secundario | Árbol B+ | Sobre un atributo no clave; el fichero NO está ordenado por ese atributo (non-clustered) |
| Índice denso | Variable | Una entrada de índice por cada registro del fichero |
| Índice disperso | Variable | Una entrada por cada bloque (o grupo de registros) del fichero |
| Índice hash | Tabla hash | Acceso directo por igualdad (no soporta rangos) |
| Índice bitmap | Mapa de bits | Un bit por registro para cada valor del atributo. Ideal para atributos con pocos valores distintos (género, estado) |
Examen: Índice clustered = 1 por tabla (el fichero está ordenado físicamente por esa clave). Non-clustered = múltiples por tabla. Los SGBD modernos (MySQL InnoDB, PostgreSQL) usan árboles B+ como estructura de índice por defecto. El índice hash solo sirve para búsquedas por igualdad exacta, no para rangos (WHERE x BETWEEN a AND b).
FUENTES PÚBLICAS
Este resumen ha sido elaborado íntegramente a partir de fuentes de dominio público. No se ha utilizado material con copyright de terceros ni material de preparadores.
| Fuente | Tipo | Referencia |
|---|
| Conceptos algorítmicos — CLRS, Knuth | Conocimiento académico | Dominio público |
| Dijkstra — Algoritmos y semáforos | Publicación académica | Dominio público |
| Teoría de grafos y complejidad | Conocimiento académico | Dominio público |