Relaciones y funciones discretas - 41. Aplicaciones en estructuras de datos

41.1 Introducción

Cada estructura de datos organiza información según una relación particular entre sus elementos. Una lista enlazada es una relación de precedencia lineal. Un árbol es una relación jerárquica donde cada nodo tiene un padre. Un grafo es una relación arbitraria entre nodos.

Al identificar qué relación discretas modelan nuestro problema, elegimos automáticamente la estructura más adecuada. Una mala elección causa ineficiencia; una buena elección hace que el código sea claro y rápido.

41.2 Listas Enlazadas como Relaciones

Una lista enlazada implementa una relación de precedencia lineal: cada elemento (nodo) apunta al siguiente. La relación es una función siguiente : Elemento → Elemento ∪ {null}.

Relación modelada: Para cada elemento x (excepto el último), hay exactamente un elemento siguiente. Es una función parcial porque el último elemento mapea a null.

// Nodo de la lista enlazada
class Nodo {
  constructor(valor) {
    this.valor = valor;
    this.siguiente = null; // Relación: este nodo → próximo nodo
  }
}

// Lista enlazada
class ListaEnlazada {
  constructor() {
    this.cabeza = null;
  }

  // Agregar elemento al final
  agregar(valor) {
    const nuevoNodo = new Nodo(valor);
    if (!this.cabeza) {
      this.cabeza = nuevoNodo;
      return;
    }
    let actual = this.cabeza;
    while (actual.siguiente) {
      actual = actual.siguiente;
    }
    actual.siguiente = nuevoNodo;
  }

  // Recorrer la relación
  recorrer() {
    const resultado = [];
    let actual = this.cabeza;
    while (actual) {
      resultado.push(actual.valor);
      actual = actual.siguiente; // Seguir la relación
    }
    return resultado;
  }

  // Buscar un elemento
  buscar(valor) {
    let actual = this.cabeza;
    while (actual) {
      if (actual.valor === valor) return true;
      actual = actual.siguiente;
    }
    return false;
  }

  // Eliminar un elemento
  eliminar(valor) {
    if (!this.cabeza) return false;
    if (this.cabeza.valor === valor) {
      this.cabeza = this.cabeza.siguiente;
      return true;
    }
    let actual = this.cabeza;
    while (actual.siguiente) {
      if (actual.siguiente.valor === valor) {
        actual.siguiente = actual.siguiente.siguiente;
        return true;
      }
      actual = actual.siguiente;
    }
    return false;
  }
}

const lista = new ListaEnlazada();
lista.agregar(10);
lista.agregar(20);
lista.agregar(30);
console.log(lista.recorrer()); // [10, 20, 30]
console.log(lista.buscar(20)); // true
lista.eliminar(20);
console.log(lista.recorrer()); // [10, 30]

41.3 Árboles como Relaciones Jerárquicas

Un árbol implementa una relación hijo-padre donde cada nodo tiene cero o más hijos, pero exactamente un padre (excepto la raíz). La relación es: padre : Nodo → Conjunto(Nodo).

Relación modelada: En un árbol genealógico, cada persona tiene exactamente un padre (excepto los ancestros) y cero o más hijos. Esta es una relación jerárquica donde se puede recorrer de arriba hacia abajo (ancestro a descendiente) o de abajo hacia arriba.

// Nodo del árbol binario
class NodoArbol {
  constructor(valor) {
    this.valor = valor;
    this.izquierda = null; // Relación: hijo izquierdo
    this.derecha = null;   // Relación: hijo derecho
  }
}

// Árbol binario de búsqueda
class ArbolBinarioBusqueda {
  constructor() {
    this.raiz = null;
  }

  insertar(valor) {
    if (this.raiz === null) {
      this.raiz = new NodoArbol(valor);
    } else {
      this._insertarRecursivo(this.raiz, valor);
    }
  }

  _insertarRecursivo(nodo, valor) {
    if (valor < nodo.valor) {
      if (nodo.izquierda === null) {
        nodo.izquierda = new NodoArbol(valor);
      } else {
        this._insertarRecursivo(nodo.izquierda, valor);
      }
    } else {
      if (nodo.derecha === null) {
        nodo.derecha = new NodoArbol(valor);
      } else {
        this._insertarRecursivo(nodo.derecha, valor);
      }
    }
  }

  // Recorrido en orden (izquierda, nodo, derecha)
  recorridoEnOrden(nodo = this.raiz) {
    if (!nodo) return [];
    return [
      ...this.recorridoEnOrden(nodo.izquierda),
      nodo.valor,
      ...this.recorridoEnOrden(nodo.derecha)
    ];
  }

  // Recorrido por niveles (BFS)
  recorridoPorNiveles() {
    if (!this.raiz) return [];
    const resultado = [];
    const cola = [this.raiz];
    while (cola.length > 0) {
      const nodo = cola.shift();
      resultado.push(nodo.valor);
      if (nodo.izquierda) cola.push(nodo.izquierda);
      if (nodo.derecha) cola.push(nodo.derecha);
    }
    return resultado;
  }

  // Buscar en árbol binario de búsqueda
  buscar(valor, nodo = this.raiz) {
    if (!nodo) return false;
    if (nodo.valor === valor) return true;
    if (valor < nodo.valor) return this.buscar(valor, nodo.izquierda);
    return this.buscar(valor, nodo.derecha);
  }

  // Altura del árbol
  altura(nodo = this.raiz) {
    if (!nodo) return 0;
    return 1 + Math.max(
      this.altura(nodo.izquierda),
      this.altura(nodo.derecha)
    );
  }
}

const arbol = new ArbolBinarioBusqueda();
[50, 30, 70, 20, 40, 60, 80].forEach(v => arbol.insertar(v));
console.log(arbol.recorridoEnOrden());   // [20, 30, 40, 50, 60, 70, 80]
console.log(arbol.recorridoPorNiveles()); // [50, 30, 70, 20, 40, 60, 80]
console.log(arbol.buscar(40));           // true
console.log(arbol.altura());             // 3

41.4 Pilas y Colas como Relaciones Ordenadas

Una pila (stack) y una cola (queue) implementan relaciones lineales con reglas específicas de acceso:

Pila: Relación LIFO (Last In, First Out). El último en entrar es el primero en salir.
Cola: Relación FIFO (First In, First Out). El primero en entrar es el primero en salir.

Ejemplos reales: Una pila modela un historial de deshacer (undo), una cola modela la espera en un consultorio o un procesador de tareas en background.

// Pila (Stack)
class Pila {
  constructor() {
    this.elementos = [];
  }

  push(elemento) {
    this.elementos.push(elemento);
  }

  pop() {
    return this.elementos.pop();
  }

  esVacia() {
    return this.elementos.length === 0;
  }

  tamaño() {
    return this.elementos.length;
  }
}

// Cola (Queue)
class Cola {
  constructor() {
    this.elementos = [];
  }

  enqueue(elemento) {
    this.elementos.push(elemento);
  }

  dequeue() {
    return this.elementos.shift();
  }

  esVacia() {
    return this.elementos.length === 0;
  }

  tamaño() {
    return this.elementos.length;
  }
}

// Aplicación: Validar paréntesis balanceados (pila)
function paréntesesBalanceados(expresión) {
  const pila = new Pila();
  const pares = { ')': '(', ']': '[', '}': '{' };
  
  for (const char of expresión) {
    if (char === '(' || char === '[' || char === '{') {
      pila.push(char);
    } else if (char === ')' || char === ']' || char === '}') {
      if (pila.esVacia() || pila.pop() !== pares[char]) {
        return false;
      }
    }
  }
  return pila.esVacia();
}

console.log(paréntesesBalanceados("(a + [b * (c - d)])"));  // true
console.log(paréntesesBalanceados("(a + [b * c - d)]"));     // false

// Aplicación: Procesador de tareas con cola
class ProcesadorTareas {
  constructor() {
    this.cola = new Cola();
    this.tarea_id = 0;
  }

  agregarTarea(descripción) {
    this.tarea_id++;
    this.cola.enqueue({
      id: this.tarea_id,
      descripción,
      timestamp: new Date()
    });
  }

  procesarSiguiente() {
    if (this.cola.esVacia()) {
      return null;
    }
    return this.cola.dequeue();
  }

  tareasEnEspera() {
    return this.cola.tamaño();
  }
}

const procesador = new ProcesadorTareas();
procesador.agregarTarea("Enviar email");
procesador.agregarTarea("Generar reporte");
procesador.agregarTarea("Actualizar base de datos");

console.log(procesador.tareasEnEspera()); // 3
console.log(procesador.procesarSiguiente());
// { id: 1, descripción: "Enviar email", timestamp: ... }
console.log(procesador.tareasEnEspera()); // 2

41.5 Conjuntos y Relaciones de Pertenencia

Un conjunto (set) implementa la relación de pertenencia. Un elemento pertenece o no al conjunto. Las operaciones típicas son unión, intersección y diferencia, que derivan de operaciones lógicas sobre la relación de pertenencia.

Relación modelada: La relación binaria "x pertenece al conjunto S" define completamente el conjunto. Los conjuntos son útiles para modelar categorías, etiquetas y membresías.

// Conjunto como relación de pertenencia
class Conjunto {
  constructor(elementos = []) {
    this.elementos = new Set(elementos);
  }

  agregar(elemento) {
    this.elementos.add(elemento);
  }

  pertenece(elemento) {
    return this.elementos.has(elemento);
  }

  eliminar(elemento) {
    return this.elementos.delete(elemento);
  }

  // Unión: todos los elementos en A o en B
  union(otro) {
    return new Conjunto([...this.elementos, ...otro.elementos]);
  }

  // Intersección: elementos que están en A y en B
  intersección(otro) {
    const resultado = new Conjunto();
    for (const elem of this.elementos) {
      if (otro.pertenece(elem)) {
        resultado.agregar(elem);
      }
    }
    return resultado;
  }

  // Diferencia: elementos en A que no están en B
  diferencia(otro) {
    const resultado = new Conjunto();
    for (const elem of this.elementos) {
      if (!otro.pertenece(elem)) {
        resultado.agregar(elem);
      }
    }
    return resultado;
  }

  // Subconjunto: ¿todos los elementos de este están en otro?
  esSubconjunto(otro) {
    for (const elem of this.elementos) {
      if (!otro.pertenece(elem)) return false;
    }
    return true;
  }

  tamaño() {
    return this.elementos.size;
  }

  aArray() {
    return Array.from(this.elementos);
  }
}

// Aplicación: Gestión de permisos
const permisosAna = new Conjunto(["leer", "escribir", "ejecutar"]);
const permisosLuis = new Conjunto(["leer", "ejecutar"]);

console.log(permisosAna.pertenece("escribir"));  // true
console.log(permisosLuis.pertenece("escribir")); // false

// Permisos que ambos tienen
console.log(permisosAna.intersección(permisosLuis).aArray());
// ["leer", "ejecutar"]

// Permisos que tiene Ana pero no Luis
console.log(permisosAna.diferencia(permisosLuis).aArray());
// ["escribir"]

// ¿Luis tiene un subconjunto de permisos de Ana?
console.log(permisosLuis.esSubconjunto(permisosAna)); // true

41.6 Tablas Hash y Funciones de Mapeo

Una tabla hash implementa una función discreta eficiente: función : Clave → Valor. La tabla usa una función de hash para mapear claves a posiciones en un array, logrando acceso promedio O(1).

Relación modelada: Cada clave está asociada a exactamente un valor. La tabla hash es una implementación eficiente de la función discreta.

// Tabla hash simple (sin manejo de colisiones avanzado)
class TablaHash {
  constructor(tamaño = 10) {
    this.tamaño = tamaño;
    this.tabla = Array(tamaño).fill(null).map(() => []);
  }

  _funcionHash(clave) {
    let hash = 0;
    for (let i = 0; i < clave.length; i++) {
      hash += clave.charCodeAt(i);
    }
    return hash % this.tamaño;
  }

  // Insertar: mapear clave a valor
  insertar(clave, valor) {
    const indice = this._funcionHash(clave);
    const bucket = this.tabla[indice];
    
    // Buscar si la clave ya existe
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === clave) {
        bucket[i][1] = valor; // Actualizar
        return;
      }
    }
    bucket.push([clave, valor]); // Agregar nuevo
  }

  // Obtener: recuperar valor dado la clave
  obtener(clave) {
    const indice = this._funcionHash(clave);
    const bucket = this.tabla[indice];
    
    for (const [k, v] of bucket) {
      if (k === clave) return v;
    }
    return undefined;
  }

  // Existe: verificar si una clave está mapeada
  existe(clave) {
    return this.obtener(clave) !== undefined;
  }

  // Eliminar: remover mapeo
  eliminar(clave) {
    const indice = this._funcionHash(clave);
    const bucket = this.tabla[indice];
    
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === clave) {
        bucket.splice(i, 1);
        return true;
      }
    }
    return false;
  }
}

// Aplicación: Caché de consultas
class Caché {
  constructor() {
    this.tabla = new TablaHash(50);
  }

  almacenar(query, resultado) {
    this.tabla.insertar(query, resultado);
  }

  buscar(query) {
    return this.tabla.obtener(query);
  }

  limpiar(query) {
    this.tabla.eliminar(query);
  }
}

const cache = new Caché();
cache.almacenar("SELECT * FROM usuarios", [{ id: 1, nombre: "Ana" }]);
cache.almacenar("SELECT * FROM productos", [{ id: 10, nombre: "Laptop" }]);

console.log(cache.buscar("SELECT * FROM usuarios"));
// [{ id: 1, nombre: "Ana" }]

console.log(cache.buscar("SELECT * FROM pedidos"));
// undefined

41.7 Grafos Generales y Relaciones Arbitrarias

Un grafo (dirigido o no dirigido) es la estructura más general para modelar relaciones discretas. Permite cualquier relación binaria entre sus nodos, sin restricciones de linealidad ni jerarquía.

Relación modelada: En una red de carreteras, hay una relación entre ciudades. En una red social, hay una relación de amistad. En un compilador, hay una relación de dependencias entre módulos. Todos son grafos.

// Grafo no dirigido
class Grafo {
  constructor() {
    this.adyacencia = {};
  }

  agregarNodo(nodo) {
    if (!this.adyacencia[nodo]) {
      this.adyacencia[nodo] = [];
    }
  }

  // Agregar arista (relación entre dos nodos)
  agregarArista(nodo1, nodo2) {
    this.agregarNodo(nodo1);
    this.agregarNodo(nodo2);
    if (!this.adyacencia[nodo1].includes(nodo2)) {
      this.adyacencia[nodo1].push(nodo2);
    }
    if (!this.adyacencia[nodo2].includes(nodo1)) {
      this.adyacencia[nodo2].push(nodo1);
    }
  }

  // Recorrido en profundidad (DFS)
  dfs(inicio, visitados = new Set()) {
    visitados.add(inicio);
    const resultado = [inicio];
    for (const vecino of this.adyacencia[inicio] || []) {
      if (!visitados.has(vecino)) {
        resultado.push(...this.dfs(vecino, visitados));
      }
    }
    return resultado;
  }

  // Recorrido en amplitud (BFS)
  bfs(inicio) {
    const visitados = new Set([inicio]);
    const resultado = [];
    const cola = [inicio];
    
    while (cola.length > 0) {
      const nodo = cola.shift();
      resultado.push(nodo);
      for (const vecino of this.adyacencia[nodo] || []) {
        if (!visitados.has(vecino)) {
          visitados.add(vecino);
          cola.push(vecino);
        }
      }
    }
    return resultado;
  }

  // Encontrar el camino más corto (BFS)
  caminoMásCorto(origen, destino) {
    if (origen === destino) return [origen];
    
    const visitados = new Set([origen]);
    const cola = [[origen]];
    
    while (cola.length > 0) {
      const camino = cola.shift();
      const ultimo = camino[camino.length - 1];
      
      for (const vecino of this.adyacencia[ultimo] || []) {
        if (vecino === destino) {
          return [...camino, destino];
        }
        if (!visitados.has(vecino)) {
          visitados.add(vecino);
          cola.push([...camino, vecino]);
        }
      }
    }
    return null; // No hay camino
  }
}

// Aplicación: Red de ciudades
const red = new Grafo();
red.agregarArista("Madrid", "Barcelona");
red.agregarArista("Madrid", "Sevilla");
red.agregarArista("Barcelona", "Bilbao");
red.agregarArista("Bilbao", "Sevilla");

console.log(red.dfs("Madrid"));
// ["Madrid", "Barcelona", "Bilbao", "Sevilla"] o similar

console.log(red.bfs("Madrid"));
// ["Madrid", "Barcelona", "Sevilla", "Bilbao"]

console.log(red.caminoMásCorto("Madrid", "Bilbao"));
// ["Madrid", "Barcelona", "Bilbao"]

41.8 Errores Comunes

Elegir la estructura equivocada: Usar un array donde se necesita un árbol, o un árbol donde es suficiente una lista enlazada, causa ineficiencia.
Olvidar liberar memoria: Al eliminar nodos de una lista o árbol, asegurate de actualizar los punteros. Las referencias dangling (referencias a memoria no asignada) causan fugas de memoria.
No considerar complejidad: Una búsqueda lineal en una lista es O(n), pero en un árbol binario de búsqueda es O(log n). La elección importa.
Ciclos infinitos en grafos: Al recorrer un grafo con ciclos sin llevar cuenta de nodos visitados, el algoritmo entra en un bucle infinito.
Asumir que toda relación es simétrica: En un grafo dirigido, la arista (A → B) no implica la existencia de (B → A). Tratar el grafo como no dirigido es un error común.

41.9 Qué debes recordar de este tema

Cada estructura de datos implementa una relación discreta específica.
Las listas enlazadas modelan relaciones lineales de precedencia.
Los árboles modelan relaciones jerárquicas padre-hijo.
Las pilas y colas modelan relaciones ordenadas con reglas LIFO/FIFO.
Los conjuntos modelan la relación de pertenencia.
Las tablas hash implementan funciones discretas eficientemente.
Los grafos modelan relaciones arbitrarias binarias entre nodos.
Elegir la estructura correcta es crucial para eficiencia y claridad del código.

41.10 Conclusión

Las estructuras de datos no son solo formas de almacenar información. Son implementaciones concretas de relaciones matemáticas discretas. Reconocer la estructura relacional subyacente permite elegir la herramienta adecuada para cada problema.

En el próximo tema exploraremos cómo las relaciones discretas se aplican específicamente en bases de datos, donde las tablas, claves foráneas e índices son todos reflejos de relaciones y funciones discretas.

Volver al índice