Problema 1: Árbol Posicional

Defina un TDA arbol posicional (AP), que almacene números enteros y permita realizar las siguientes operaciones:

• Crear un AP vacío, en tiempo O(1).
• Insertar un elemento, en tiempo O(log n) en promedio.
• Eliminar un elemento, en tiempo O(log n) en promedio.
• Buscar el k-ésimo elemento del árbol, para cualquier k dado (ej. el mínimo (k = 1), el máximo (k = n), la mediana (k = n=2), etc.), en tiempo O(log n) en promedio.

Solución Inicial:

En principio basta con una árbol binario:

1. AP vacio en tiempo O(1): El binario se crea en tiempo constante
2. Inserta en O(log n): El binario inserta en tiempo log n
3. Elimina en O(log n): El binario elimina en orden log n
4. Buscar el k-esimo elemento en O(log n): NO :(, para sacar el k-esimo elemento, hay que sacar en orden del elemento 1 al elemento k, costo: k*log n, y si k es n, costo n*log n, para esto mejor ordenar y sacamos cualquier elemento en orden

 Para calcular fácilmente la posición, necesito conservar la cantidad de nodos que tengo por la izquierda y derecha.

  - Al crear numNodosIzq = numNodosDer = 0
  - Al insertar si es a la derecha un nodo se incrementa en uno el num nodos derecha, si es a la izquierda se incrementa en uno el num nodos
izquierda
  - Idem al eliminar pero esta vez actualizando los contadores de nodos.

  Busqueda
  - si el de la izquierda mas lo acumulado es 1 menor que la posicion, estamos en el elemento k-esimo
  - si el de la izquierda mas lo acumulado es menor que la posicion entonces derecha, se debe recordar cuantos elementos se tienen a la
    izquierda ahora.
  - si el de la izquierda es mayor que la posicion entonces izquierda, y se debe guardar cuantos elementos hay a la izquierda.

class AP {
  int valor;
  int numNodosIzq;
  AP izq, der;

  AP() {
    valor = null;
    numNodosDer = numNodosIzq = 0;
    izq = null;
    der = null;
  }

  AP(int item) {
    valor = item;
    numNodosDer = numNodosIzq = 0;
    izq = null;
    der = null;
  }

  void insertar(int item) {
    AP aux = this; // parto por la raiz
    boolean insertado = false;
    AP nuevo = AP(item);
    while (!insertado){
      if (item < aux.valor) { // inserto uno menor
        aux.numNodosIzq++;
        if (aux.izq != null) aux= aux.izq; // deciendo
        else { //llegue a la hoja
          aux.izq = nuevo;
          insertado = true;
        }
      }
      else { // inserto uno mayor
        aux.numNodosIzq++;
        if (aux.der != null) aux= aux.der; // deciendo
        else { //llegue a la hoja
          aux.der = nuevo;
          insertado = true;
        }
      }
    }
  };

  boolean esta(int item){
    AP aux = this;
    while (1) {
      if (aux = null) return false;
      if (aux.valor < item) aux = aux.izq;
      else (aux.valor > item) aux = aux.der;
      else return true; //aux.valor es igual a item !!
    }
  }

  boolean eliminar(int item) {
    if (!esta(item)) return false;
    AP aux = this;
    while (1) {
      if (aux.valor < item){
        aux.numNodosIzq--;
        if (aux.izq.valor != item)
          aux = aux.izq;
        else { // lo voy a eliminar
          AP aux2 = aux.izq;
          aux.izq = aux2.der;
          colgar aux2.izq a la izquierda de aux.izq y a medida que deciendo agrego a la izquierda los nodos de aux2.izq;
          return true;
        }
      }
      else (aux.valor > item){
        aux.numNodosDer--;
        if (aux.der.valor != item)
          aux = aux.der;
        else { // lo voy a eliminar
          AP aux2 = aux.der;
          aux.der = aux2.izq;
          colgar aux2.der a la derecha de aux.der y a medida que deciendo agrego a la derecha los nodos de aux2.der;
          return true;
        }
      }
    }
  };

  int buscar(int pos) {
    if ( (this.numNodosIzq + this.numNodosDer + 1) < pos )
      return POSICION_INVALIDA;
    AP aux = this;
    while (1){
      if (pos > aux.numNodosIzq + 1) {
        pos = pos - aux.numNodosIzq - 1;
        aux = aux.der;
      }
      else (pos = aux.numNodosIzq + 1) return aux.valor;
      else aux = aux.izq;
    }
  };

}

Problema 2: Evaluacion de expresion matematicas en notacion polaca usando una pila

Supuestos:

• Operaciones binarias
• Clase Base: Elem, heredan Numero y Operador

Ejemplo: (pila de izquierda a derecha)
2 4 / 2 1 3 - * +

Luego las llamadas son

      + (resultado = 6)
     /                 \
    * (res = 4)        / (res = 2)
   /            \     / \
  - (res = 2)    2   4   2
 / \
3   1

Problema 3: Implementacion de lista con estrategia Move-To-Front (MTF)

MTF es: si accesas un elemento de la lista, dicho elemento pasa a ser el primero de la lista (recuerda que se hace busqueda secuencial).

clase:

public class ListaMTF {
  public ListaMTF sig;
  public Item item;

  public ListaMTF() {
    this.sig = null;
    this.item= null;
  };

  public ListaMTF(Item item) {
    this.sig = null;
    this.item= item;
  };

  void insert(Item item) {
    // Se inserta al comienzo
    ListaMTF elem = new ListaMTF(item);
    elem.sig = this.sig;
    this.sig = elem;
  };

  boolean esta(Item item) {
    ListaMTF aux = this;
    while (aux->sig != null) { //termina cuando llega al final de la lista
      if (Equal.(aux->sig->item, item)){
        // descuelgo el elemento encontrado
        aux->sig = aux->sig->sig;
        // lo coloco en primer lugar (despues del header)
        aux->sig = this->sig;
        this->sig = aux;
        return true;
      }
    }
    return false;
  };

  Item get (Item item){
    if (esta(item))
      return this.sig.item;
    else return null;
  };

  boolean remove (Item item) {
    if (esta(item) {
      // si no hay recolector hay que hacer: aux = this.sig;
      this.sig = this.sig.sig;
      // si no hay recolector hay que hacer: delete aux;
      return true;
      // el recolector hace el resto del trabajo
    }
    else return false;
  }
}