Estructuras de Datos en Java: Polinomios, Grafos, Árboles, Tablas Hash y Colecciones

equals->

{
if(this==o) return true;
if(!(o instanceof Set<E>)) return false;
Set<E> c=(Set<E>)o;
if(c.size()!=size()) return false;
Iterator<E> it1=iterator();
Iterator<E> it2=c.iterator();
while(it1.hasNext() && it2.hasNext())
    if(!it1.next().equals(it2.next())) return false;
final return true;
}

Polinomios

2,2,0
0,0,5
2,-2,0
0,-0,2

p1 -> TreeMap de pares de la forma (exp, coef) ordenados por exp, que es la clave, de menor a mayor según el orden natural.
p1: ((0,0.5) (2,2.0) (5,5.0))
p2: ((0,-0.2) (1,1.2) (2,-2.0) (5,5.5) (7,7.0))

opera -> es la suma de polinomios: p1 = p1 + p2

d -> Coste temporal: O(n·log n). Se puede mejorar siguiendo el algoritmo de mezcla, consiguiendo O(n).

e -> suma de p1 + p2 anteriores
p1: 0,0.3 1,1.2 5,10.5 7,7.0

Poly2d

Área de datos: class Point2D -> String nombre, double x, double y; y private List<Point2D> points;

Por defecto: points = new ArrayList<>();

Copia: points = new ArrayList<>(); for (Point2D p : other.points) points.add(new Point2D(p.nombre, p.x, p.y));

Método numPoints: return points.size();

Método getCoordLastPoint:

double[] getCoordLastPoint() {
    if (points.isEmpty()) return null;
    Point2D p = points.get(points.size() - 1);
    return new double[]{p.x, p.y};
}

TurismoAstur

private TreeMap<String, TreeSet<String>> data;

data = new TreeMap...; luego copia: this(); data.putAll(other.data);

Método numSites:

int num = 0;
Collection<TreeSet<String>> coll = data.values();
for (TreeSet<String> s : coll)
    num += s.size();
return num;

Coste: O(n). Habría que añadir un contador de sitios para poder ser O(1).

Por último: private TreeMap<String, TreeMap<String, String>> data;

ClaseX

size = 0
data = entry[9]: es una tabla hash con direccionamiento abierto. Dibujarla:

Índice: 0   1   2   3   4   5   6   7   8
Datos: (17,P) · (2,Manuel) · · (5,María) (14,Leo) · (8,Elena)

c) HashMap<K,V>

op1 es un put y op2 es un get, porque op1 inserta una pareja y op2 devuelve el valor asociado a esa clave.
op2(5) → María
op2(3) → null

f)

Porque usa Entry<K,V>, direccionamiento abierto, sondeo lineal, no usa listas enlazadas y no hay marcas de borrado (entry).
Posición: (i+1)·size
Búsqueda secuencial hasta volver al índice inicial.
Uso directo del array.

peek

Lego<E> actual = raíz;
E resultado = null;
while (actual != null) {
    resultado = actual.dato;
    actual = actual.uno;
}
return resultado;

Multi de Lego: Lego<Par<K,V>> primero; int elementos. Par k,v; ordeno en el dibujo por abecedario.

sig: Lego<E> tabla; int elementos;

sig -> 0, 1 -> puerta, 3, 4 -> hola -> <-

ebanistas con 3 elementos: buen factor de carga. Con 4 elementos: redimensionar.
4 -> hola, 6 -> puerta -> <- última
7 -> raspad, 9 -> ebanistas, 10

Tabla

LinkedList y ArrayList<E> data:
get: O(1); resto: O(n)

HashSet<Par<E,Integer>> data: O(1) de media, excepto addAll (O(n) de media).
Lo mismo para HashMap<E,Integer> data; y TreeMap<E,Integer>: O(log n) y n log n.

retainAll

boolean m = false;
Iterator<E> itr = c.iterator();
while (itr.hasNext()) {
    E elem = itr.next();
    if (this.contains(elem)) {
        this.removeAll(elem);
        m = true;
    }
}
return m;

Tabla hash: área de datos

E[] tabla; int[] status; int[] index; double loadFactorLimit; int elements; int deleted; int tamTablaSize;
double currentLoadFactor = (elements + deleted) / tamTablaSize;

TaskManager

private PriorityQueue<Task> data = new PriorityQueue<>();

boolean add(Task t) { return data.add(t); }
Task peek() { return data.peek(); }
int size() { return data.size(); }
boolean isEmpty() { return data.size() == 0; }
Task poll() { return data.poll(); }

sumaPolinomios

Map<Integer, Double> sumaPolinomios(Map<Integer, Double> p1, Map<Integer, Double> p2) {
    Map<Integer, Double> res = new HashMap<>();
    for (Map.Entry<Integer, Double> e : p1.entrySet())
        res.put(e.getKey(), e.getValue());
    for (Map.Entry<Integer, Double> e : p2.entrySet()) {
        int exp = e.getKey();
        double coef = e.getValue();
        res.put(exp, res.getOrDefault(exp, 0.0) + coef);
        if (res.get(exp) == 0.0)
            res.remove(exp);
    }
    return res;
}

Grafos

int numVertex; int numEdges; SortedMap<Vertex, SortedMap<Vertex, Double>> adjList;
Se usa TreeMap, SortedMap: adjList = ...

gradoEntrada

int gradoEntrada(Graph g, Vertex v) {
    if (!g.hasVertex(v)) throw new Exception();
    int cont = 0;
    Collection<Vertex> c = g.getAllVertex();
    for (Vertex w : c)
        if (g.hasEdge(w, v)) cont++;
    return cont;
}

gradoSalidaMax

int max = 0;
for (Vertex v : g.vertices()) {
    int grado = g.outEdges(v).size();
    if (grado > max) max = grado;
}
return max;

addEdge

if (adj[i] == null) adj[i] = new ArrayList<>();
adj[i].add(new Edge(j, label));

maxOutdegree

int max = -1, vert = -1;
for (int i = 0; i < numVertices; i++) {
    int grado = (adj[i] == null) ? 0 : adj[i].size();
    if (grado > max) {
        max = grado;
        vert = i;
    }
}
return vert;

Modificar el algoritmo

El bosque de extensión se almacena mediante una relación padre–hijo, guardando para cada vértice el vértice desde el que fue descubierto en la búsqueda en profundidad.

void BEP(Graph g, Vertex v, Collection<Vertex> marked, Map<Vertex, Vertex> parent) {
    for (Vertex w : g.adjacent(v))
        if (!marked.contains(w)) {
            parent.put(w, v);
            BEP(g, w, marked, parent);
        }
}

Map<Vertex, Vertex> parent = new HashMap<>();
if (!marcados.contains(v)) {
    parent.put(v, null);
    BEP(g, v, marcados, parent);
}
return parent;

Matrices y vectores dispersos

SparseVector

Vector disperso con muchos valores cero. Diccionario donde la clave es el índice y el valor es el elemento distinto de cero, almacenando solo la información relevante. Ejemplo: {2=5.0, 5=3.0}
Map<Integer, Double>

SparseMatrix

Matriz en la que la mayoría de sus elementos son cero. Ejemplo: [0 0 0; 0 5 0; 3 0 0]
Diccionario cuya clave es el par (fila, columna) y cuyo valor es el elemento no nulo. Ejemplo: {(1,1)=5.0, (2,0)=3.0}
Map<Pair<Integer, Integer>, Double>

Polynomial

Suma de términos de la forma coef·x^exp. Ejemplo: 3x⁴ + 2x² − 5
Diccionario que asocia cada exponente con su coeficiente. Ejemplo: {4=3.0, 2=2.0, 0=-5.0}
Map<Integer, Double>

CrossReferences

Asocian elementos con los lugares donde aparecen. Ejemplo: "java" → {1, 3, 7}
Diccionario donde la clave es la palabra y el valor es el conjunto de posiciones asociadas.
Map<String, Set<Integer>>

Árboles

ABB

Colección de elementos jerarquizada que tienen un orden. Etiqueta e, dibujo.

Node<E> theTree;

private class Node {
    E label;
    Node<E> left;
    Node<E> right;
    boolean rightThread;
}

Árboles enhebrados

Son árboles binarios en los que los nodos que no tienen hijo izquierdo o derecho están enlazados, mediante hilos, al nodo predecesor y sucesor en inorden.

Parent

Para obtener el padre de un nodo en un árbol binario enhebrado por la derecha, se recorre el árbol desde la raíz siguiendo únicamente los enlaces a hijos reales, ignorando los hilos. El primer nodo cuyo hijo izquierdo o derecho real coincide con el nodo dado es su padre. Si el nodo es la raíz, no tiene padre.

public Tree<E> parent() {
    if (theRoot.right == null) {
        throw new NoSuchElementException();
    }
    Node<E> current = theRoot;
    while (!current.isRightThread)
        current = current.right;
    return current.right;
}

Hilos

Son enlaces que sustituyen a los punteros nulos, normalmente apuntando al sucesor o predecesor en inorden. Su objetivo es permitir recorridos eficientes del árbol sin necesidad de usar pila, recursión ni memoria auxiliar.

Implementación, primero:

this.label = e;
this.left = left;
this.right = right;
this.isThread = false;

Y el otro:

if (bt.isEmpty()) {
    this.isThread = false;
} else {
    this.label = bt.getRoot();
    this.left = new ThreadedBT<>(bt.getLeft());
    this.right = new ThreadedBT<>(bt.getRight());
    this.isThread = false;
}

Rojo-Negro

Un árbol Rojo-Negro es un árbol binario de búsqueda balanceado donde cada nodo es rojo o negro. La raíz y los nodos nulos son negros.

public int blackHeight() {
    if (theRoot == null) return 1;
    int h = blackHeight(theRoot.left);
    return theRoot.color == BLACK ? h + 1 : h;
}

RB_Tree<Integer> t = new RB_Tree<>();