Lunes 11 de Octubre

Estructuras de Datos

Objetivos: Definir el concepto de estructura de datos y mostrar cómo se puede implementar una pila por medio de una lista enlazada..

Temas:

Implementación de tipos de datos abstractos

Los tipos de datos son los enteros, reales, valores booleanos y todos los objetos. Un tipo de datos es abstracto cuando los programadores pueden trabajar con él conociendo sólo sus operaciones. Uno puede abstraerse de su implementación y utilizarlos exitosamente. Por ejemplo, en este curso hemos usado las pilas, colas y arreglos asociativos sin conocer su implementación, y por lo tanto son tipos de datos abstractos.

La abstracción es importante para poder disminuir la complejidad de los problemas que se enfrentan. Sin embargo, también es útil conocer aspectos de la implementación de los tipos de datos con los que se trabaja y por ello estudiamos como se representaban los números reales. Esto nos permite entender mejor sus limitaciones, como el número finito de decimales que puede almacenar.

En este capítulo estudiaremos las técnicas que se usan para implementar los tipos de datos abstractos como las pilas, colas, arreglos asociativos y otros. Es decir definiremos (implementaremos) estas clases.

Estructuras de datos

Cuando se implementa una clase es necesario preocuparse de:

Veremos que existen patrones de organización para las variables de instancia. Estos patrones se denominan estructuras de datos.

La estructura de datos de uso más frecuente es el arreglo. Las pilas, colas y arreglos asociativos se implementan fácilmente por medio de arreglos nativos. Sin embargo, el resultado presenta serias deficiencias que resolveremos por medio de dos nuevas estructuras de datos: las listas enlazadas y los árboles.

Ejemplo: Implementación de una pila de enteros

El problema reside en donde almacenar los elementos de la pila. Lo más fácil es almacenarlos en un arreglo:

    class Queue extends Program {
      int a[];
      int tope;
      int tamanno;
      Queue() {
        max= 100;
        a= new int[max];
        tope= 0;
      }
      void push(int x) {
        if (tope>max) {
          println("desborde de pila");
          exit(); // termina el programa
        }
        a[tope]= x;
        tope= tope+1;
      }
      int popInt(int x) {
        if (tope==0) {
          println("pila vacia");
          exit();
        }
        tope= tope-1;
        return a[tope];
      }
      boolean isEmpty() {
        return tope==0;
      }
    }
En donde a es el arreglo y tope es el lugar en donde se almacenará el próximo entero que se coloque en la pila.

El problema de esta implementación es que si se llena el arreglo, hay que terminar el programa con un mensaje de error. Es decir la pila queda limitada a 100 elementos o el tamaño que se elija.

Una mejor implementación de una pila debería hacer crecer automáticamente el arreglo cuando se excede su tamaño. Por ejemplo se podría hacer crecer el tamaño en un factor 2. Ahora el problema es que si en algún momento se agrega un millón de elementos en la pila, la pila ocupará para siempre un millón enteros de la memoria del computador, incluso si sólo contiene unos cuantos enteros.

Listas enlazadas

Una lista enlazada es una estructura de datos que se visualiza como una cadena de eslabones que termina con una referencia nula. Cada eslabón se representa por medio de las siguientes variables de instancia:

    class Eslabon {
      ...
      Eslabon prox;
    }
Lo que caracteriza al eslabón como una estructura de datos recursiva es que entre las variables de instancia se encuentra una referencia a un objeto del mismo tipo.

Junto con poseer una referencia del próximo eslabón en la cadena, se colocan variables de instancia para almacenar datos concerniente al problema que se pretende resolver. Por ejemplo, para implementar la pila se puede colocar un entero en cada eslabón de la cadena: 

    class Eslabon {
      int x;
      Eslabon prox;
      Eslabon(int x, Eslabon prox) {
        this.x= x;
        this.prox= prox;
      }
    }
Típicamente los eslabones no tienen métodos asociados. Por conveniencia tienen un constructor.

Implementación de una pila usando listas enlazadas

La idea es formar una lista enlazada de eslabones que contienen los elementos de la pila. En la clase pila se almacena la referencia al eslabón que contiene el tope de la pila:

    class Pila extends Program {
      Eslabon primero= null;
      void push(int x) {
        primero= new Eslabon(x, primero);
      }
      void popInt() {
        int tope= primero.x;
        primero= primero.prox;
        return tope;
      }
    }

Computación I Miércoles 13 de Octubre

Listas Enlazadas

Objetivos: Mostrar cómo se efectúan algunas operaciones básicas en una lista enlazada.

Temas:

Implementación de una cola

La clase Queue que ha sido usada en el curso puede encolar enteros, reales, valores booleanos, strings o incluso cualquier objeto. Ahora veremos una versión simplicada que sólo permite almacenar strings:

Ejemplo Significado Declaración
StringQueue q= new StringQueue(); Construye una cola de strings vacía StringQueue()
q.put("hola"); Agrega el string "hola" al final void put(String s)
String s= q.getString() extrae y entrega el primer elemento de la cola String getString()
int l= q.size() entrega la cantidad de elementos de la cola int size()

Se puede usar un arreglo para almacenar los elementos de la cola, pero se presentan las mismas deficiencias de la pila implementada con arreglos.

La estructura de datos más conveniente para implementar una cola es la lista enlazada, al igual que la pila. La siguiente figura muestra la estructura de una cola en la que se han encolado los strings "hola", "que" y "tal":

La estructura de los eslabones queda representada por medio de la siguiente clase:

    class EslabonCola {
      String s;
      EslabonCola prox;
      Eslabon(String s, EslabonCola prox) {
        this.s= s;
        this.prox= prox;
      }
    }
Y la estructura de una cola consiste en una referencia del primer eslabón de la cola:

    class StringQueue extends Program {
      EslabonCola primero;
      ... // Los métodos getString, put y size
    }
La variable de instancia primero referencia el eslabón que contiene el primer string de la cola.

Extracción del primer eslabón de una lista enlazada

Para implementar la operación getString es necesario obtener el string contenido en el primer eslabón y luego extraer de la lista enlazada ese eslabón:

    String getString() {
      String s= primero.s;
      primero= primero.prox;
      return s;
    }
La siguiente figura muestra la modificación que se hace en los enlaces para sacar el primer eslabón de la cadena:

Observe que si la cola tenía exactamente un eslabón, después de extraerlo de la cola, la lista enlazada queda sin eslabones.

Recorrer los eslabones de una lista enlazada

El tamaño de la cola está dado por la cantidad de eslabones de la cola. Por lo tanto hay que contar los eslabones:

    int size() {
      int cont= 0;
      EslabonCola e= primero;
      while (primero!=null) {
        e= e.prox;
        cont= cont+1;
      }
      return cont;
    }

Agregar un eslabón al final de una lista enlazada

Para implementar la operación put es necesario agregar un nuevo eslabón al final de la lista enlazada. En este eslabón se coloca el string que se agrega a la cola. Esto no es trivial porque la estructura de la cola no contiene ningún puntero hacia el final de la cola. Por lo tanto hay que recorrer la pila hasta encontrar el último eslabón:

    void put(String s) {
      if (primero==null)
        primero= new EslabonCola(s, null);
      else {
        EslabonCola e= primero;
        while (e.prox!=null)
          e= e.prox;
        e.prox= new EslabonCola(s, null);
      }
    }
Observe que el caso en que la cola está vacía es un caso de borde, porque en ese caso el eslabón debe ser referenciado por la variable de instancia primero. La figura muestra las modificaciones realizadas en las referencias:

Análisis del tiempo de ejecución de cada operación:

En la próxima clase se verán mejoras a la eficiencia de esta implementación.

Computación I Lunes 18 de Octubre

Listas Enlazadas (continuación)

Objetivos: Mostrar algunas técnicas que se pueden usar con las listas enlazadas para hacerlas más simples y más eficientes .

Temas:

Implementación eficiente de una cola con listas enlazadas

La eficiencia se logra colocando en la estructura de la cola una referencia del último eslabón de la lista enlazada:

    class StringQueue extends Program {
      EslabonCola primero;
      EslabonCola ultimo;
      ... // Los métodos getString, put y size
    }
Con esta referencia es posible llegar directamente al último eslabón sin tener que visitar todos los eslabones de la lista enlazada:

    void put(String s) {
      EslabonCola e= new EslabonCola(s, null);
      if (primero==null)
        primero= ultimo= e;
      else {
        ultimo.prox= e;
        ultimo= e;
      }
    }
Análisis del tiempo de ejecución de cada operación:

Con esta implementación encolar un string en la cola es igual de eficiente que extraer el primer elemento.

Eliminación del caso de borde en que la lista esta vacía

El truco consiste en hacer que la lista nunca esté vacía. Para ello se crea un primer eslabón falso. Este eslabón no contiene nigún string de la cola. Sólo esta ahí para evitar que la lista enlazada quede sin eslabones:

    class StringQueue extends Program {
      EslabonCola primero;
      EslabonCola ultimo;
      StringQueue() {
        primero= ultimo= new EslabonCola(null, null); // eslabón falso
      }
      String getString() {
        if (primero.prox==null) {
          println("Cola vacia");
          exit();
        }
        String s= primero.prox.s;
        primero.prox= primero.prox.prox;
        return s;
      }
      int size() {
        int cont= 0;
        EslabonCola e= primero.e;
        while (e!=null) {
          e= e.prox;
          cont= cont+1;
        }
        return cont;
      }
      void put(String s) {
        ultimo.prox= new EslabonCola(s, null);
        ultimo= ultimo.prox;
      }
    }
Observe que esto no significa que la cola no pueda estar vacía. La cola está vacía cuando la lista enlazada contiene exactamente un eslabón (el eslabón falso).

Colas de objetos

Basta cambiar los datos contenidos en los eslabones. En vez de colocar una referencia de un String, se coloca una referencia de un objeto:

    class EslabonCola {
      Object o;
      EslabonCola prox;
      Eslabon(Objecto o, EslabonCola prox) {
        this.o= o;
        this.prox= prox;
      }
    }
La implementación es la misma sólo que cambia el tipo del dato que se manipula:

    class Queue extends Program {
      EslabonCola primero;
      EslabonCola ultimo;
      ...
      Object get() {
        Object o= primero.prox.o;
        primero.prox= primero.prox.prox;
        return o;
      }
      void put(Object o) {
        ultimo.prox= new EslabonCola(o, null);
        ultimo= ultimo.prox;
      }
    }

Colas con objetos y strings

En la cola anterior se pueden colocar string porque en Java los strings son objetos. El problema es que al sacarlos de la cola se obtienen como objetos y no como strings:

    Queue q= new Queue();
    q.put("hola"); // Proyección
    q.put("que");
    String s= q.get(); // Error durante la compilación
El error se produce porque get entrega un objeto, y un objeto es más general que un string y por lo tanto no se puede almacenar en una variable de tipo String. Observe que put recibe un objeto como parámetro y se le pasa un string como argumento. Esto sí se puede hacer porque un string es una forma más restringida de objeto, pero es un objeto finalmente.

La última instrucción se puede escribir de la siguiente forma para que no de error:

    Object s= q.get(); // Correcto en compilación y ejecución
    ... substring(s, 1, 2) ... // Error en tiempo de compilación
Ahora no es posible operar con el objeto como un string. Para poder almacenarlo en una variable de tipo String y así poder aplicarle las operaciones que acepta un string se debe usar un cast:

    String s= (String)q.get(); // Correcto en compilación y ejecución
    ... substring(s, 1, 2) ... // Correcto

Colas con objetos y tipos primitivos

En la cola anterior no se pueden colocar tipos de datos primitivos como los enteros, reales y valores de verdad. Estos tipos de datos no son objetos y por lo tanto al colocarlos como argumentos de la operación se produce un error de tipos durante la compilación:

    q.put(1); // Error de tipos en tiempo de compilación
Esto significa que los enteros no pueden ser considerados como una subclase de Object. Para solucionar este problema Java ofrece la clase Integer que sí es una subclase de Object. La operaciones que acepta esta clase son las siguientes:

Ejemplo Significado Declaración
Integer objent= new Integer(1); Construye un objeto Integer que almacena el 1 Integer(int i)
int i= objent.intValue() Entrega el valor entero almacenado en objent int intValue()

El objeto objent es un objeto y por lo tanto puede ser colocado en una cola:

    q.put(objent); // Error de tipos en tiempo de compilación
Sin embargo, al ser un objeto pierde sus operaciones como entero y no se puede operar como tal:

    objent= objent+1; // Error de tipos en tiempo de compilación
Con la clase Integer ahora es posible almacenar cualquier entero en una cola. Supongamos que necesitamos agregar el entero e en una cola y posteriormente extraerlo. Entonces el siguiente código es una receta para lograr esto:

    q.put(new Integer(e));  // Coloca el entero e en la cola
    ...
    int f= ((Integer)q.get()).intValue(); // Recupera el valor e de la cola
Java también ofrece las clases estándares Double y Boolean para trabajar con los reales y los valores de verdad como objetos. Observe que se diferencian únicamente de los tipos de datos primitivos double y boolean porque Double y Boolean comienzan con una letra mayúscula y porque Double y Boolean son subclases de Object.

Implementación de la clase Integer

    class Integer {
      private int e; // No es accesible desde fuera de la clase
      Integer(int e) {
        this.e= e;
      }
      int intValue() {
        return e;
      }
    }

Computación I Miércoles 20 de Octubre

Implementación de Arreglos Asociativos

Objetivos: Mostrar como se implementa un arreglo asociativo usando listas enlazadas.

Temas:

El tipo de datos abstracto arreglo asociativo con llaves enteras

En esta clase implementaremos un subconjunto del tipo de datos Map que utilizamos durante el primer semestre. Este tipo de datos asocia enteros con un objeto cualquiera. Sus operaciones son:

Ejemplo Significado Declaración
Map m= new Map(); Construye un arreglo asociativo con llaves enteras, inicialmente vacío Map()
m.put(2, "hola"); Asocia el entero 2 con el string "hola" void put(int ll, Object v)
String s= (String)m.get(2); entrega el objeto asociado a la llave 2 ("hola"). Si la llave no posee valor asociado se produce un error. Object get(int ll)
if (m.isMapped(2)) ... entrega verdadero si la llave 2 tiene un valor asociado. boolean isMapped(int ll)
m.remove(2) elimina la asociación (2,...) del arreglo asociativo. void remove(int ll)

Por simplicidad, esta versión restringida de Map no acepta establecer asociaciones entre enteros y otros enteros o números reales, como:

    m.put(1, 3);    // no implementada
    m.put(1, 3.14); // no implementada

Representación de un arreglo asociativo usando listas enlazadas

Se usa un eslabón por cada par (llave, valor asociado) presente en el arreglo asociativo. En cada eslabón se almacena la llave, el valor asociado y la referencia del próximo eslabón en la lista enlazada.

En la figura se observa la estructura de una arreglo asociativo que posee las asociaciones (2, "hola"), (5, "que") y (3, "tal").

En el objeto que representa el arreglo asociativo se coloca una referencia del primer eslabón de la lista enlazada. Por conveniencia, se incluye un eslabón falso para que la lista nunca esté vacía. En este caso no es útil tener una referencia del último eslabón, porque ninguna operación requiere agregar algún eslabón al final de la lista enlazada.

Observe que el orden en que se organiza la lista enlazada es irrelevante. El eslabón que contiene la llave 2 podría haber quedado perfectamente después del eslabón de la llave 5 sin alterar el contenido formal del arreglo asociativo. El orden en que quedarán almacenadas las llaves depende únicamente del orden en que se hagan las asociaciones.

Por lo tanto, la estructura de representación de la clase Map y la clase EslabónM es la siguiente:

    class Map extends Program {
      EslabonM primero= new EslabonM(0, null, null);
      ... la implementación de la operaciones de Map ...
    }
    class EslabonM {
      int llave;
      Object valObj;
      EslabonM proximo;
      EslabomM(int llave, Object valObj, EslabomM proximo) {
        this.llave= llave;
        this.valObj= valObj;
        this.proximo= proximo;
      }
    }

Búsqueda de una llave en la lista enlazada

Para implementar la operación get se usa el patrón de recorrido de la lista enlazada. Al hacer la búsqueda de la llave no se necesita visitar el eslabón falso por lo tanto el recorrido de los eslabones comienza por el segundo eslabón:

    Object get(int llave) {
      EslabonM e= primero.proximo;
      while (e!=null) {
        if (e.llave==llave)
          return e.valObj;
        e= e.proximo;
      }
      fatalError("No se encontro la llave "+i); // termina la ejecución!
      return null; // para que pase la compilacion
    }
La búsqueda termina cuando se encuentra la llave especifica o cuando se acaba la lista enlazada. En este último caso el programa termina con un mensaje de error.

También se necesita hacer este mismo recorrido con la operación put. Si la llave existe se modifica el valor en el mismo eslabón. Si la llave no existía previamente en la lista enlazada, se crea un nuevo eslabón para esa llave y se agrega por conveniencia justo después del eslabón falso:

    void put(int llave, Object valObj) {
      EslabonM e= primero.proximo;
      while (e!=null) {
        if (e.llave==llave) { // la llave existe
          e.valObj= valObj;   // cambiamos su valor
          return;             // y retornamos
        }
        e= e.proximo;
      }
      // la llave no existía previamente
      // Creamos un nuevo eslabon y lo agregamos entre el eslabon
      // falso y el segundo eslabon
      e= new EslabonM(llave, valObj, primero.proximo);
      primero.proximo= e;
    }
La siguiente figura muestra el caso en que la llave ya existía previamente en el arreglo asociativo:

Ejercicio: Verifique que las dos operaciones funcionan correctamente cuando el arreglo asociativo se encuentra vacío (cuando la lista enlazada sólo contiene el eslabón falso).

Eliminación de un eslabón en la lista enlazada

La operación remove elimina una asociación en el arreglo asociativo. Esto equivale a eliminar el eslabón que contiene la llave especificada.

El primer intento de implementación que viene a la mente consiste en usar el patrón de recorrido de los eslabones para buscar la llave que se desea eliminar. Sin embargo, este patrón no sirve porque cuando se encuentre la llave, la variable de instancia prox que hay que modificar se encuentra en el eslabón visitado en la iteración anterior. Pero este eslabón ya se visitó y no es posible volverlo a recorrer si comenzar por el primer eslabón.

Para resolver el problema, modificamos ligeramente el patrón de recorrido de modo de mantener en la variable anterior el eslabón visitado en la iteración anterior. La siguiente figura muestra cómo realizar la eliminación del eslabón utilizando la variable anterior:

El código para eliminar una llave del arreglo asociativo es entonces:

    void remove(int llave) {
      EslabonM anterior= primero;
      EslabonM proximo= primer.proximo;
      while (proximo!=null && proximo.llave!=llave) {
        anterior= proximo;
        proximo= proximo.proximo;
      }
      if (proximo==null) // la llave no existe en el arreglo asociativo
        return;
      // la llave si existe, por lo que se elimina el eslabon
      // referenciado por proximo
      anterior.proximo= proximo.proximo;
    }
La eliminación es una operación frecuente con las listas enlazadas, por lo que este trozo de código constituye un patrón de programación. Estúdielo cuidadosamente.

Análisis del tiempo de ejecución de las operaciones

Sea n el número de asociaciones que contiene un arreglo asociativo implementado usando listas enlazadas. El tiempo que toma cada una de las operaciones es el siguiente:

Estos tiempos son válidos tanto para el caso peor como para el caso promedio.

Observe que construir un arreglo asociativo de n llaves toma tiempo O(n*n), lo que sabemos es muy ineficiente de acuerdo a lo estudiado con los algoritmos de ordenamiento.

En la próxima clase veremos una implementación eficiente de un arreglo asociativo que permite construir un arreglo con n asociaciones en tiempo O(n*log n) en el caso promedio. Esta implementación estará basada en un nueva estructura de datos: el árbol de búsqueda binaria.

Resumen

Todas las operaciones que hemos realizado con listas enlazadas se pueden resumir en los siguientes patrones de programación:

Computación I Lunes 25 de Octubre

Arboles de Búsqueda Binaria

Objetivos: Mostrar como se implementa un arreglo asociativo usando árboles de búsqueda binaria.

Temas:

Definición de árboles de búsqueda binaria

Un árbol es una estructura de datos recursiva que se puede caracterizar en forma inductiva:


Un árbol binario es un árbol en el que de cada nodo cuelgan a los más dos árboles binarios.

Un árbol de búsqueda binaria (ABB) es un árbol binario que almacena en cada nodo una llave. El árbol de búsqueda binaria cumple las siguientes propiedades:


Implementación de un arreglo asociativo con un árbol de búsqueda binaria

Representamos el arreglo asociativo mediante un objeto que tiene una referencia de la raíz de un ABB:

    class Map extends Program {
      Nodo raiz= null;
      ... operaciones del arreglo asociativo ...
    }
Cuando el arreglo está vacío, la raíz es nula y representa entonces el árbol vacío. Cuando el arreglo tiene al menos una asociación, la raíz no es nula y referencia un objeto de la clase Nodo que se define como:

    class Nodo {
      int llave;
      Objecto valObj;
      Nodo izq;
      Nodo der;
      Nodo(int llave, Object valObj, Nodo izq, Nodo der) {
        this.llave= llave;
        this.valObj= valObj;
        this.izq= izq;
        this.der= der;
      }
    }
En donde izq referencia la raíz del ABB izquierdo, o nulo si el ABB vacío, y der referencia respectivamente el ABB derecho. Un nodo almacena una asociación (llave, valObj), al igual que en una lista enlazada un eslabón almacena un asociación del arreglo asociativo.

La siguiente figura dos posibles representaciones de un arreglo asociativo con asociaciones {3->"hola", 5->"que", 10->"tal}:


Búsqueda en un ABB

Para implementar la operación get se utiliza un patrón de programación denominado búsqueda en ABBs. Esta búsqueda hace uso de un método recursivo que llamaremos buscar:

    Object get(int llave) {
      return buscar(llave, raiz);
    }

    private Object buscar(int llave, Nodo nodo) {
      if (nodo==null) {
        fatalError("La llave no existe en el arreglo");
        return null;
      }
      else if (llave==nodo.llave)
        return nodo.valObj;
      else if (llave<nodo.llave)
        return buscar(llave, nodo.izq);
      else
        return buscar(llave, nodo.der);
    }
La siguiente figura muestra gráficamente el funcionamiento de este método:


Versión iterativa:

    Object get(int llave) {
      Nodo nodo= raiz;
      while (nodo!=null) {
        if (nodo.llave==llave)
          return nodo.valObj;
        if (nodo.llave<llave)
          nodo= nodo.izq;
        else
          nodo= nodo.der;
      }
      fatalError("La llave no existe en el arreglo");
      return null;
    }
Ejercicio: Implemente el método isMapped. Revise la clase anterior para obtener la especificación del comportamiento de este método.

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

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

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.