Identificás el problema que modela el capítulo y el TAD/estructura más adecuada.
Justificás decisiones de diseño con costo temporal/espacial y contrato de operaciones.
Aplicás el contenido en Java sin romper invariantes ni contrato público.
Este capitulo completa el catalogo algebraico de la parte con cuatro familias que aparecen todo el tiempo en la practica: sets, diccionarios, arboles y grafos. La idea no es fijar una unica implementacion, sino mostrar como se expresa el contrato de cada estructura, que variantes son habituales y cual es la version simplificada que conviene usar cuando queres enseñar la idea sin cargar demasiada maquinaria.
En todos los casos, la tecnica es la misma: definir sorts, operaciones, axiomas e invariantes. Lo que cambia es el vocabulario de cada familia.
Un set representa una coleccion finita de elementos sin repetidos y sin orden observable. La igualdad no depende de la forma de construccion, sino del contenido.
Permite add y remove sobre el mismo estado abstracto
La especificacion debe dejar claro si remove sobre un elemento ausente es identidad.
Set ordenado
Expone un orden observable sobre los elementos
Aparecen observadores como min, max, predecessor y successor.
Set acotado
Trabaja sobre un universo finito y conocido
contains puede razonarse como un vector booleano finito.
Set persistente
Cada operacion devuelve un set nuevo sin mutar el anterior
Las ecuaciones deben expresar comparticion semantica, no mutacion.
Estas variantes cambian la manera de leer el contrato, pero no el principio central: dos sets son iguales si contienen los mismos elementos. Cuando el set deja de ser “solo pertenencia” y empieza a exponer orden o finitud, la signatura gana observadores nuevos.
La version simplificada mas util es el set sobre universo finito. En vez de modelar cualquier elemento, se toma un universo fijo U={0,…,n−1} y el set se especifica solo con una interfaz minima:
En esa version, basta con dejar explícitos cuatro hechos:
empty no contiene nada.
add vuelve verdadera la pertenencia del elemento agregado.
remove vuelve falsa la pertenencia del elemento removido.
add es idempotente.
Eso reduce el esfuerzo de axiomatizacion porque contains se comporta como acceso a una posicion booleana. Si queres formalizar un set un poco mas rico sin perder simplicidad, esta es la variante de partida.
put reemplaza el valor anterior y lookup devuelve a lo sumo un resultado.
Diccionario ordenado
Las claves tienen orden observable
Aparecen consultas por rango y extremos.
Multidiccionario
Una clave puede tener varios valores
lookup devuelve una coleccion y remove puede eliminar una ocurrencia o todas.
Diccionario hash
La ubicacion depende de una funcion de dispersion
La especificacion suele ocultar el almacenamiento y solo exigir acceso promedio eficiente.
En el diccionario simple, la propiedad clave es que la igualdad de mapas depende de pares clave -> valor, no de la historia de inserciones. Cuando agregas orden, el contrato deja de ser solo asociativo y pasa a incluir recorridos. Cuando agregas multiplicidad, lookup ya no puede seguir siendo un unico valor.
La version simplificada mas didactica es el diccionario parcial sobre claves acotadas. Se fija un universo de claves finito y se evita modelar iteradores, vistas o estructura interna. El contrato minimo queda asi:
remove elimina la clave y hace que containsKey vuelva a falso.
Con eso alcanza para enseñar el contrato semantico sin sumar complejidad accidental. Es la version mas util cuando queres conectar algebra de TDAs con estructuras de mapas concretas.
Un arbol representa una estructura jerarquica con una raiz y subarboles. La especificacion cambia segun si el arbol es general, binario o binario de busqueda.
La estructura de nodo queda fijada por raiz, izquierdo y derecho.
Arbol binario de busqueda
El orden de las claves queda restringido por la raiz
El contrato agrega la propiedad de orden total entre subarboles.
Arbol balanceado
Mantiene una cota sobre la altura
Aparecen axiomas sobre rotaciones y altura acotada.
Trie
La forma del arbol sigue prefijos de claves
La ruta desde la raiz representa una clave compuesta.
En arboles, la variante elegida cambia mucho mas que el nombre: cambia la forma en que se interpreta la jerarquia. Un arbol general sirve para modelar pertenencia estructural; un BST agrega orden; un balanceado agrega restriccion sobre la forma; un trie agrega prefijos.
La version simplificada mas clara es el arbol binario puro, donde solo importan la raiz y los dos hijos. Se omiten el orden de busqueda, el balanceo y cualquier politica de rebalanceo. El contrato minimo queda reducido a:
adjacent es una relacion booleana entre vertices distintos.
Grafo dirigido
La relacion depende del sentido
Hay que distinguir outNeighbors de inNeighbors.
Grafo ponderado
Cada arista tiene un peso
El contrato agrega weight y restricciones sobre la existencia de peso.
Multigrafo
Puede repetir aristas entre vertices
edgeCount y multiplicidad pasan a ser observables.
Grafo con lazos
Permite aristas de un vertice hacia si mismo
adjacent(g, v, v) deja de ser un caso prohibido.
La variante simple es la base pedagogica mas estable. Las otras se usan cuando el problema real exige direccion, costo o multiplicidad. En todos los casos, la pregunta algebraica sigue siendo la misma: que significa que dos grafos sean iguales, y que operaciones cambian realmente el estado.
El contrato minimo deberia dejar claros estos puntos:
addVertex hace visible al vertice.
addEdge solo agrega incidencia entre vertices existentes.
removeEdge elimina una incidencia concreta.
neighbors devuelve exactamente los vertices adyacentes.
adjacent es simetrica porque el grafo es no dirigido.
Eso alcanza para enseñar conectividad, recorrido y razonamiento sobre incidencia sin mezclar pesos ni orientacion. Si despues queres agregar direccion o ponderacion, la simplificacion sirve como punto de partida limpio.
Los cuatro TDAs comparten la misma forma de especificacion, pero cambian los axiomas que definen identidad, ausencia, reemplazo y relacion entre observadores.
En un set, la igualdad depende del contenido.
En un diccionario, la clave es unica y lookup preserva la semantica de reemplazo.
En un arbol, la estructura jerarquica domina y las medidas como size y height expresan su forma.
En un grafo, la incidencia entre vertices y aristas es el centro de la especificacion.
La version simplificada de cada uno sirve para introducir la idea sin arrastrar variantes de implementacion o detalles de uso que distraen del contrato algebraico.