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.
Implementación de un arreglo asociativo con un árbol de búsqueda binaria.
Búsqueda en un ABB.

Definición de árboles de búsqueda binaria

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

El árbol vacío es un árbol.
Un nodo del cual cuelgan uno más árboles es un árbol.

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:

El árbol vacío es un ABB.
El árbol de la figura es un ABB cuando:
- los árboles izquierdo y derecho son ABBs, y
- la llave k es mayor que todas las llaves almacenadas en el ABB izquierdo.
- la llave k es menor que todas las llaves almacenadas en el ABB derecho.

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.