Computación I

Miércoles 27 de Octubre

Arboles de Búsqueda Binaria - 2da. parte

Temas:

Versión iterativa de la inserción en ABBs.
Versión recursiva de la inserción en ABBs.
Eliminación de nodos en ABBs.

Versión iterativa de la inserción en ABBs

Cuando se invoca la operación put, se presentan dos casos:

La llave existía previamente, y por lo tanto ya existe en el árbol un nodo para esa llave en donde colocar el nuevo valor asociado. Por lo tanto en este caso no es necesario crear un nuevo nodo.
La llave no existía previamente, y por lo tanto se hace necesario crear un nuevo nodo e insertarlo en el árbol de modo que éste continúe siendo un ABB. En este caso, lo intuitivo es colocar el nodo como una hoja del árbol.

A continuación se presenta la implementación iterativa (es decir no recursiva) de put. Ésta resulta más simple conceptualmente que la implementación recursiva. Pero veremos que a la larga, la versión recursiva es un poco más breve que la iterativa.

    void put(int llave, Object valObj) {
      Nodo nodo= raiz;
      while (nodo!=null) {
        if (nodo.llave==llave) {
          nodo.valObj= valObj;
          return;
        }
        if (nodo.llave<llave)
          if (nodo.izq!=null)
            nodo= nodo.izq;
          else {
            nodo.izq= new Nodo(llave, valObj, null, null);
            return;
          }
        else
          if (nodo.izq!=null)
            nodo= nodo.der;
          else {
            nodo.der= new Nodo(llave, valObj, null, null);
            return;
          }
      }
    }

Esta solución no es elegante porque hay que diferenciar el caso en que el eslabón se agrega al lado izquierdo o al lado derecho.

Versión recursiva de la inserción en ABBs

Al igual que en el caso de la búsqueda de un nodo, se requiere introducir un nuevo método que será recursivo. Este método recibe como argumento la llave que se desea modificar, el nuevo valor asociado y la raíz del ABB en el que se debe realizar la modificación.

La clave para simplificar la implementación está en hacer que el método recursivo retorne una referencia del árbol modificado. En forma pictórica los distintos casos de modificación se explican en la siguiente figura:

Inserción en un ABB

El código para implementar esta operación en Java es:

    void put(int llave, Object valObj) {
      this.raiz= modificar(llave, valObj, raiz);
    }

    private Nodo modificar(int llave, Object valObj, Nodo nodo) {
      if (nodo==null)
        return new Nodo(llave, valObj, null, null);

      if (llave==nodo.llave)
        nodo.valObj= valObj;
      else if (llave<nodo.llave)
        nodo.izq= modificar(llave, valObj, nodo.izq);
      else
        nodo.der= modificar(llave, valObj, nodo.der);
      return nodo;
    }

Como podemos apreciar, la versión es un poco más breve que la versión iterativa. Sin embargo, ambas son igualmente eficientes.

Eliminación de nodos en ABBs

Para implementar el método remove se necesita usar el patrón de eliminación de nodos en ABBs. La siguiente figura explica en forma pictórica la lógica de este patrón:

Eliminación en un ABB

Para implementar esta operación se agrega el método recursivo eliminar. Este método recibe un ABB como parámetro y lo transforma de modo que ya no contenga la llave especificada. El método retorna el ABB modificado:

    void remove(int llave) {
      this.raiz= eliminar(llave, raiz);
    }

    private Nodo eliminar(int llave, Nodo nodo) {
      if (nodo==null)
        return null;
      if (nodo.llave==llave)
        return unir(nodo.izq, nodo.der);

      if (llave<nodo.llave)
        nodo.izq= eliminar(llave, nodo.izq);
      else
        nodo.der= eliminar(llave, nodo.der);
      return nodo;
    }

El caso defícil se presenta cuando hay que eliminar un nodo, pero ese nodo tiene subárboles izquierdo y derecho al mismo tiempo. En este caso por lo tanto fabricamos un nuevo método que une dos ABBs (unir). El trabajo realizado por este método queda representado en la siguiente figura:

Unión de ABBs

El código de unir es:

    private Nodo unir(Nodo izq, Nodo der) {
      if (izq==null)
        return der;
      if (der==null)
        return izq);
      Nodo centro= unir(izq.der, der.izq);
      izq.der= der;
      der.izq= centro;
      return izq;
    }

Análisis

Sea n el número de asociaciones que posee un arreglo asociativo. La siguiente tabla muestra el tiempo de ejecución en función de n para las operaciones típicas de un arreglo asociativo:

Operación	Tiempo	Tiempo
	caso peor	caso promedio
get	O(n)	O(log(n))
isMapped	O(n)	O(log(n))
put	O(n)	O(log(n))

Como vemos, el caso promedio es muy eficiente en comparación con la implementación que usa listas enlazadas.

Ejercicio 1: Implementación del método size

Implemente la operación size que calcula el número de asociaciones de un arreglo asociativo implementado mediante ABBs. Por ejemplo:

    Map m= new Map();
    println(m.size()); // 0
    m.put(3, "hola");
    m.put(5, "que");
    m.put(-1, "tal");
    println(m.size()); // 3

Ejercicio 2: Implementación del método findKey

Se desea desea agregar el método findKey a la clase Map. Este método recibe como parámetro un objeto y debe entregar alguna llave a la cual se asocia ese objeto. El siguiente ejemplo muestra el uso de findKey:

    Map m= new Map();
    Object s= "hola";
    m.put(10, s);
    m.put(5, "que");
    println(m.findKey(s)); // 10

Formalmente, findKey debe cumplir con la siguiente propiedad:

       Sea o un objeto cualquiera,
       si m.findKey(o)==ll entonces m.get(ll)==o

Observe que pueden existir varias llaves que se asocian con el mismo objeto o. En tal caso, m.findKey(o) entrega cualquiera de esas llaves. Si no existe ninguna llave, findKey termina la ejecución con un mensaje de error (invoca fatalError).

Implemente el método findKey para un arreglo asociativo implementado mediante ABBs.

Observación: Ud. debe buscar el objeto en todo el árbol. En este caso, el orden en que se encuentran las llaves en el ABB no sirve de nada. Por lo tanto su implementación tomará tiempo O(n).

Ejercicio 3: Implementación de arreglos con llaves de tipo string

Implemente la clase StringMap usando ABBs. Implemente las siguientes operaciones:

Ejemplo	Significado	Declaración
StringMap m= new StringMap();	Construye un arreglo asociativo con llaves de tipo string, inicialmente vacío	StringMap()
m.put("juan", "26 de Junio");	Asocia el string "juan" string "26 de junio"	void put(String ll, Object v)
String s= (String)m.get("juan");	entrega el objeto asociado a la llave "juan". Si la llave no posee valor asociado se produce un error.	Object get(String ll)

Ejercicio 4: Inserción en la raiz de ABBs

En la implementación hecha para put, el eslabón que contiene la llave queda en su posición original (cuando la llave existía) o en una hoja del árbol (cuando la llave no existía). Implemente una versión de put en donde la llave que se reasocia con un nuevo objeto siempre quede en la raíz del ABB.

Indicaciones: Suponga que el método recursivo que inserta la llave en la raíz del ABB se llama insertar. El caso simple es cuando la llave ya se encuentra en la raíz o el ABB está vacío. Analícelo. Cuando no se cumple ninguna de estas condiciones, sin pérdida de generalidad podemos suponer que la llave que se reasocia con un nuevo valor es menor que la llave almacenada en la raíz del ABB. La siguiente figura muestra cómo debe calcular el nuevo árbol en el caso en que la llave que se desea agregar es menor que la llave que se encuentra almacenada en la raíz del ABB (ll<ll'):

Inserción en la raíz de un ABB
(caso ll<ll')

El resultado del método insertar será entonces el árbol A. Haga las figuras para los casos en que ll==ll' y ll>ll'. Finalmente programe los métodos put e insertar.