Estructuras de Datos en Java: Árboles, Tablas Hash y Algoritmos Recursivos Resueltos
Estructuras de Datos en Java: Árboles y Tablas Hash
1. Inversión de un árbol general
public Tree<T> invierteArbol1(Tree<T> entrada) {
Tree<T> salida;
if (entrada.isEmpty()) {
// el árbol es vacío: se devuelve un árbol vacío
salida = CollectionsFactory.createTreeFactory().createTree();
} else {
// el árbol no es vacío. Al menos tiene la raíz
T raiz = entrada.getInfo();
// se crea un nuevo árbol con esa raíz
salida = CollectionsFactory.createTreeFactory().createTree(raiz);
List<Tree<T>> subarboles = entrada.getSubTrees();
// Se van añadiendo, en orden, en la posición 0
for (Tree<T> subarbol : subarboles) {
salida.add(0, invierteArbol1(subarbol));
}
}
return salida;
}
2. Inversión de un árbol general (versión con ListIterator)
private static <T> Tree<T> invierteArbol2(Tree<T> entrada) {
Tree<T> salida;
if (entrada.isEmpty()) {
salida = CollectionsFactory.createTreeFactory().createTree();
} else {
// el árbol no es vacío. Al menos tiene la raíz
T raiz = entrada.getInfo();
// se crea un nuevo árbol con esa raíz
salida = CollectionsFactory.createTreeFactory().createTree(raiz);
List<Tree<T>> subarboles = entrada.getSubTrees();
// Se crea un ListIterator, comenzando por la última posición
ListIterator<Tree<T>> lit = subarboles.listIterator(subarboles.size());
// Se van añadiendo, desde el final al principio, siempre al
// final de la lista de subárboles
while (lit.hasPrevious()) {
Tree<T> subarbol = lit.previous();
salida.add(invierteArbol2(subarbol));
}
}
return salida;
}
3. Redistribución de una tabla hash
private void redistribuye(int nuevoTamano) {
ArrayList<List<Entry<K,V>>> entradasAntigua = entradas;
tamanoEntradas = nuevoTamano;
entradas = new ArrayList<List<Entry<K,V>>>(nuevoTamano);
for (int i=0; i<nuevoTamano; i++) {
entradas.add(new LinkedList<Entry<K, V>>());
}
int nuevoHash = 0;
for (List<Entry<K, V>> l : entradasAntigua) {
for (Entry<K,V> e : l) {
nuevoHash = h(e.getKey());
entradas.get(nuevoHash).add(e);
}
}
}
4. Constructores de la clase FuncionEje09
public FuncionEje09() {
this(CAPACIDAD_INICIAL_DEFECTO);
}
public FuncionEje09(int capacidadInicial) {
if (capacidadInicial < 0)
throw new IllegalArgumentException("Argumento inválido capacidadInicial: " + capacidadInicial);
tamanoEntradas = capacidadInicial;
tamano = 0;
// Daría igual ponerlo o no, pues al principio la lista está vacía
factorCarga = UMBRAL_MINIMO;
// Hasta llegar a UMBRAL_MINIMO no se considera redispersión
minimoAlcanzado = false;
// Se instancia entradas
entradas = new ArrayList<SearchTree<Entry<K,V>>>(capacidadInicial);
for (int i=0; i<capacidadInicial; i++) {
entradas.add(new ArbolDeBusqueda<Entry<K, V>>());
}
}
5. Operaciones putAll y remove
public void putAll(Map<? extends K, ? extends V> map) {
if (map == null)
throw new NullPointerException("Argumento NULL");
// Se recorren los pares del map de entrada y se añaden a this()
for (Entry<? extends K, ? extends V> e : map.entrySet()) {
this.put(e.getKey(), e.getValue());
}
}
public V remove(Object key) {
if (key == null)
throw new NullPointerException("Argumento NULL");
// a través de la función de dispersión obtenemos la posición de la lista donde puede estar el par buscado
int i = h(key);
// buscamos sobre esa lista solamente
V valor = null;
SearchTree<Entry<K,V>> l = entradas.get(i);
for (Entry<K,V> e : l) {
if (e.getKey().equals(key)) { // y cuando la encontramos
valor = e.getValue(); // guardamos el valor que habrá que devolver
tamano--;
l.remove(e); // se elimina el par, y se invalida el iterador, pero ya no lo necesitamos más
equilibraCarga(); // vemos si hay que redispersar y redispersamos en su caso
break; // y terminamos
}
}
return valor;
}
6. Reconstrucción de un árbol binario a partir de preorden e inorden
public class Ejercicio1 {
public BinaryTree<Character> dibujarArbol(List<Character> preorden, List<Character> inorden) {
BinaryTree<Character> salida = CollectionsFactory.createTreeFactory().createBinaryTree();
int i;
if (!preorden.isEmpty()) {
/* Se toma el primer elemento de la lista en preorden, se busca en inorden y se llama recursivamente con las dos ramas */
Character raiz = preorden.get(0);
/* se crea un nuevo árbol con esa raíz y con los hijos izquierdos y derechos recursivos */
i = inorden.indexOf(raiz);
List<Character> preordenIzq = preorden.subList(1, i+1);
List<Character> preordenDer = preorden.subList(i+1, preorden.size());
List<Character> inordenIzq = inorden.subList(0, i);
List<Character> inordenDer = inorden.subList(i+1, inorden.size());
salida.setInfo(raiz);
salida.set(0, dibujarArbol(preordenIzq, inordenIzq));
salida.set(1, dibujarArbol(preordenDer, inordenDer));
}
return salida;
}
}
7. Comparación de dos árboles
public class Ej02 {
public static <E> void ej02(Tree<E> t1, Tree<E> t2) {
if (equalsEj02(t1, t2))
System.out.println("Son iguales");
else
System.out.println("Son diferentes");
}
public static <E> boolean equalsEj02(Tree<E> t1, Tree<E> t2) {
boolean b = true;
if (!(t1.isEmpty() && t2.isEmpty())) {
if (!t1.isEmpty() && !t2.isEmpty()) {
b = t1.getInfo().equals(t2.getInfo());
Iterator<Tree<E>> it1 = t1.getSubTrees().iterator();
Iterator<Tree<E>> it2 = t2.getSubTrees().iterator();
while (b && it1.hasNext() && it2.hasNext()) {
b = equalsEj02(it1.next(), it2.next());
}
if (it1.hasNext() || it2.hasNext()) {
b = false;
}
} else {
b = false;
}
}
return b;
}
}
8. Operaciones put y equals de un mapa
public V put(K key, V value) {
if (key == null || value == null)
throw new NullPointerException("Argumento NULL");
// a través de la función de dispersión obtenemos la posición de la lista donde puede estar el par buscado
int i = h(key);
// buscamos sobre esa lista solamente
V valor = null;
boolean sustitucion = false;
SearchTree<Entry<K,V>> l = entradas.get(i);
for (Entry<K,V> e : l) {
if (e.getKey().equals(key)) {
// si existe un par con igual clave
valor = e.getValue();
sustitucion = true;
// hay que sustituir su valor por el parámetro
e.setValue(value);
break; // terminamos
}
}
// si no existía un par con la misma clave que en el parámetro
if (!sustitucion) {
Entry<K,V> e = new ParSimple<K,V>(key, value);
entradas.get(i).add(e);
tamano++;
equilibraCarga(); // vemos si hay que redispersar y redispersamos en su caso
}
return valor;
}
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Map))
return false;
Map<K,V> m = (Map<K,V>) o;
if (m.size() != size())
return false;
try {
Iterator<Entry<K,V>> i = entrySet().iterator();
while (i.hasNext()) {
Entry<K,V> e = i.next();
K key = e.getKey();
V value = e.getValue();
if (value == null) {
if (!(m.get(key) == null && m.containsKey(key)))
return false;
} else {
if (!value.equals(m.get(key)))
return false;
}
}
} catch (ClassCastException unused) {
return false;
} catch (NullPointerException unused) {
return false;
}
return true;
}