Universidad Carlos III de Madrid

Ingeniería de Telecomunicación

Enero-Mayo 2010 / January-May 2010

Árboles

Tabla de contenidos

1. Sesión 4 (laboratorio): Árboles (II)
1.1. Árbol binario de búsqueda
2. Actividades para casa
2.1. Árbol N-ario
2.2. Cola con Prioridad utilizando un montículo

Lab Section1. Sesión 4 (laboratorio): Árboles (II)

Exercise Section1.1. Árbol binario de búsqueda

Objetivo

Instruir al alumno en la utilización de árboles binarios de búsqueda.

Ejercicio

Un árbol binario de búsqueda es un árbol binario ordenado de modo que para cada nodo n, todas las claves de los nodos del subárbol izquierdo son menores que la clave de n y todas las del subárbol derecho son mayores (supondremos que no existen repeticiones).

En esta práctica implementaremos un árbol binario de búsqueda mediante las clases BSTree (que representa el árbol) y la clase auxiliar BSNode, de modo que:

  • Un árbol BSTree contiene la referencia a su nodo raíz.

  • Un nodo BSNode contiene la clave de comparación, la información a almacenar y las referencias a los nodos que forman los subárboles izquierdo y derecho.

Tal como se representa en la figura siguiente:

Observa que con esta estructura, un árbol vacío es aquél que tiene su nodo raíz a null (sin embargo, el objeto árbol en sí no es null). A continuación, implementa:

  • Define los atributos de las clases BSTree y BSNode, de acuerdo a la estructura representada en la figura anterior.

  • Proporciona un constructor, sin parámetros, para la clase BSTree que inicialice un árbol vacío (es decir, con la raíz igual a null).Proporciona un constructor para la clase auxiliar BSNode. Este constructor debe recibir como parámetros la clave de búsqueda asociada ese nodo y la información a almacenar. Los subárboles hijos, izquierdo y derecho, del nodo se inicializarán a null. Para cada clase, proporciona los métodos get y set necesarios para acceder a sus atributos.

  • Programa el método boolean isEmpty() que comprueba si el árbol está vacío.

  • Programa el método public Object search(Comparable key) que devuelve el objeto almacenado en el nodo cuya clave asociada coincide con la que se pasa como parámetro.

  • Programa el método public void insert(Comparable key, Object info) que introduce un nuevo dato en el árbol. Para ello, debe crear un nuevo nodo en el lugar apropiado, que contenga la clave y el objeto que se pasan como parámetros. Si el árbol ya contiene un nodo con la clave indicada, se sobreescribe la información almacenada en el objeto.

  • Programa el método void printPreOrden() que presenta por salida estándar todas las entradas del árbol, siguiendo el recorrido pre-orden.

Ahora que ya tienes experiencia en el manejo de árboles vamos a implementar una agenda de direcciones utilizando un árbol binario de búsqueda para facilitar las búsquedas:

  • Programa la clase DirectoryEntry que almacena los datos asociados a cada entrada de la agenda: Nombre, Apellidos, Dirección, Teléfono, Móvil and Correo electrónico.

  • Programa la clase Directory, que utiliza un árbol binario de búsqueda para almacenar los datos de una agenda electrónica. La clave de búsqueda por la que se ordenan los datos de la agenda es el nombre completo, según el formato: Apellidos, Nombre

  • Agrega a la clase Directory el método void insert(DirectoryEntry data) que introduce los datos que se pasan como parámetros en la agenda. Recuerda que debes concatenar los apellidos y el nombre para generar la clave de búsqueda asociada. Agrega a la clase Directory el método void insert() que introduce una nueva entrada en la agenda con los datos que se introduzcan por teclado.

  • Agrega a la clase Directory el método DirectoryEntry search(String fullName) que permite recuperar los datos de una determinada entrada a partir del nombre completo (apellidos y nombre).

  • Programa el método void printInOrder() que presenta el contenido de la agenda por salida estándar, en orden alfabético (recorrido in-orden).

Solución

Esta es la solución: 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

/**
 * Directory using a Binary Search tree
 * 
 * @author jfgalvan
 * 
 */
public class Directory {

  private BSTree directory;

  public Directory() {
    directory = new BSTree();
  }

  /**
   * Introduce the data passed as a parameter
   * 
   * @param data
   *          of the new entry
   */
  public void insert(DirectoryEntry data) {

    // Search key
    String key = data.getSurname() + ", " + data.getName();
    System.out.println("** Inserting: " + key);
    directory.insert(key, data);

  }

  /**
   * Introduce a new entry with the data passed through the standard input
   * agenda con los datos que se introduzcan por teclado
   */
  public void insert() throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    DirectoryEntry data = new DirectoryEntry(br);
    br.close();

    insert(data);

  }

  /**
   * Gets the data of a certain entry given a full name (surname and name) *
   * 
   * @param fullName
   *          (Surname, Name)
   * @return searched entry
   */
  public DirectoryEntry search(String fullName) {
    return (DirectoryEntry) directory.search(fullName);
  }

  /**
   * Prints the agenda content in alphabetic order to the standard output
   */
  public void printInOrder() {
    directory.printInOrder();
  }

  public static void main(String[] args) {

    Directory dir = new Directory();

    DirectoryEntry dirEntry = new DirectoryEntry("John", "Smith",
        "Sesame Street", "99999999", "9999999999", "john.smith@test.com");
    dir.insert(dirEntry);

    dirEntry = new DirectoryEntry("Jimmy", "Johnson", "Waterloo Street",
        "435858098", "4999124909", "jimmy.johnson@test.com");
    dir.insert(dirEntry);

    dirEntry = new DirectoryEntry("Larry", "Paxson", "Bristol Street",
        "7848892823", "995454549", "larry.paxson@test.com");
    dir.insert(dirEntry);

    dirEntry = new DirectoryEntry("Michael", "Brown", "Generic Street",
        "9984309999", "9991343539", "michael.brown@test.com");
    dir.insert(dirEntry);

    System.out.println("===== Sorted query =====");

    dir.printInOrder();

    System.out
        .println("\n\n===== Now we search for an existing member =====\n");
    dirEntry = dir.search("Paxson, Larry");
    if (dirEntry != null)
      System.out.println(dirEntry.toString());
    else
      System.out.println("Not found!");

    System.out
        .println("\n\n===== Now we search for a non-existing member =====\n");
    dirEntry = dir.search("Paxson, Jimmy");
    if (dirEntry != null)
      System.out.println(dirEntry.toString());
    else
      System.out.println("Not found!");

  }

}

	  
/**
 * Binary Search Tree
 * 
 * @author jfgalvan
 */

public class BSTree {

  /* ********************************************** *
   * CLASS BSNode * **********************************************
   */

  static class BSNode {

    private Comparable key;
    private Object info;
    private BSNode left;
    private BSNode right;

    BSNode(Comparable key, Object info) {
      this(key, info, null, null);
    }

    BSNode(Comparable key, Object info, BSNode l, BSNode r) {
      this.key = key;
      this.info = info;
      left = l;
      right = r;

    }

    Comparable getKey() {
      return key;
    }

    Object getInfo() {
      return info;
    }

    BSNode getLeft() {
      return left;
    }

    BSNode getRight() {
      return right;
    }

    void setInfo(Comparable info) {
      this.info = info;
    }

    void setLeft(BSNode left) {
      this.left = left;
    }

    void setRight(BSNode right) {
      this.right = right;
    }

    public void insert(BSNode tree) throws BTreeException {

      if (tree.getKey().compareTo(this.getKey()) < 0) {
        // lower key -> insert in the left subtree
        if (left != null)
          left.insert(tree);
        else
          left = tree;

      } else if (tree.getKey().compareTo(this.getKey()) > 0) {
        // greater key -> right subtree
        if (right != null)
          right.insert(tree);
        else
          right = tree;

      } else
        throw new BTreeException("Elment already in tree");

    }

    /**
     * Returns the object stored in the node whose key is the same as the one of
     * the key param.
     * 
     * @param key
     *          string to search
     * @return object stored in the searched node
     */
    public Object search(BSNode tree) {

      Object result = null;

      if (tree.getKey().compareTo(this.getKey()) == 0)
        result = this.getInfo();

      else if (tree.getKey().compareTo(this.getKey()) < 0) {
        // If the key to search is lower than the one
        // of the root, search down through the left subtree
        if (left != null)
          result = left.search(tree);

      }

      else {
        // greater key -> right subtree
        if (right != null)
          result = right.search(tree);

      }

      return result;
    }

    void preOrder() {
      System.out.println(info);
      if (left != null)
        left.preOrder();
      if (right != null)
        right.preOrder();
    }

    void inOrder() {
      if (left != null)
        left.inOrder();
      System.out.println(info);
      if (right != null)
        right.inOrder();
    }

    void postOrder() {
      if (left != null)
        left.postOrder();
      if (right != null)
        right.postOrder();
      System.out.println(info);
    }
  }

  /* ********************************************** */

  public static final int LEFT_SIDE = 0;
  public static final int RIGHT_SIDE = 1;

  protected BSNode root;

  BSTree() {
    root = null;
  }

  BSTree(Comparable key, Object info) {
    root = new BSNode(key, info);
  }

  public BSNode getRoot() {
    return root;
  }

  public void setRoot(BSNode root) {
    this.root = root;
  }

  void insert(Comparable key, Object info) {

    BSNode node = new BSNode(key, info);

    if (root == null)
      setRoot(node);
    else {
      try {
        root.insert(node);
      } catch (BTreeException e) {
        System.out.println(e);
      }

    }

  }

  public Object search(String info) {

    BSNode node = new BSNode(info, info);

    return root.search(node);

  }

  /**
   * Check if the tree is empty (no nodes)
   * 
   * @return true if tree is empty; false otherwise
   */
  boolean isEmpty() {
    return (root == null);

  }

  public void printPreOrder() {
    if (root != null)
      root.preOrder();
  }

  public void printInOrder() {
    if (root != null)
      root.inOrder();
  }

  public void printPostOrder() {
    if (root != null)
      root.postOrder();
  }

}
	  
import java.io.BufferedReader;
import java.io.IOException;

/**
 * @author jfgalvan
 * 
 */
public class DirectoryEntry {

  private String name;
  private String surname;
  private String address;
  private String phone;
  private String mobile;
  private String email;

  public DirectoryEntry(String name, String surname, String address,
      String phone, String mobile, String email) {
    this.name = name;
    this.surname = surname;
    this.address = address;
    this.phone = phone;
    this.mobile = mobile;
    this.email = email;
  }

  /**
   * Initialize a new object from the standard input
   */
  public DirectoryEntry(BufferedReader br) throws IOException {

    System.out.print("Introduce the name: ");
    name = br.readLine();

    System.out.print("Introduce the surname: ");
    surname = br.readLine();

    System.out.print("Introduce the address: ");
    address = br.readLine();

    System.out.print("Introduce the phone: ");
    phone = br.readLine();

    System.out.print("Introduce the mobile phone: ");
    mobile = br.readLine();

    System.out.print("Introduce the email address: ");
    email = br.readLine();

  }

  public String getSurname() {
    return surname;
  }

  public String getAddress() {
    return address;
  }

  public String getEmail() {
    return email;
  }

  public String getMobile() {
    return mobile;
  }

  public String getName() {
    return name;
  }

  public String getPhone() {
    return phone;
  }

  public void setSurname(String surname) {
    this.surname = surname;
  }

  public void setAddress(String address) {
    this.address = address;
  }

  public void setEmail(String email) {
    this.email = email;
  }

  public void setMobile(String mobile) {
    this.mobile = mobile;
  }

  public void setName(String name) {
    this.name = name;
  }

  public void setPhone(String phone) {
    this.phone = phone;
  }

  public String toString() {
    return "Data: \n" + surname + ", " + name + "\n" + address + " " + phone
        + " " + mobile + " " + email + "\n" + "--------------";
  }

}

Homework Section2. Actividades para casa

Exercise Section2.1. Árbol N-ario

Objetivo

Instruir al alumno en la implementación y utilización de árboles con un número variable de hijos.

Ejercicio

En este ejercicio se utilizará la definición recursiva de árbol para diseñar una clase Java que implemente un árbol N-ario.

Recuerda que se necesitan dos clases, NTree y NNode, para poder modelar adecuadamente el árbol vacío.

  • Crea la clase NTree basándote en la definición recursiva anterior. Programa un constructor sin parámetros que inicialice un árbol vacío. Programa un constructor adicional que reciba como parámetro el elemento (de la clase Object) a almacenar en el nodo raíz.

  • Crea la clase NNode basándote en la definición recursiva anterior, que encapsule la información a almacenar en el nodo y un Vector con las referencias a los hijos. Programa un constructor que reciba como parámetro el elemento (de la clase Object) a almacenar en el nodo. Programa también los correspondientes métodos accesores (get y set).

  • Programa el método size que devuelve el tamaño (número de nodos) del árbol.

  • Programa el método preorder que imprime los elementos del árbol siguiendo un recorrido preorden.

  • Necesitarás métodos auxiliares para construir y recorrer el árbol, como int getNumberOfChildren(), void addChild(NNode child), void addChildAt(int index, NNode child), NNode getChildAt(int index), y otros.

Solución

Esta es la solución: 

public class NTree {

  private NNode root;

  public NTree() {
    root = null;
  }

  public NTree(Object info) {
    root = new NNode(info);
  }

  public int size() {
    return root.size();
  }

  public void preorder() {
    root.preorder();
  }

  public NNode getRoot() {
    return root;
  }

  public void setRoot(NNode root) {
    this.root = root;
  }

}
    

import java.util.*;

public class NNode {

  public Object info;
  public Vector<NNode> children;

  /* ************************************************* *
   * Constructor * *************************************************
   */

  public NNode(Object info) {
    this.info = info;
    children = new Vector<NNode>();
  }

  /* ************************************************* *
   * Getters and Setters * *************************************************
   */

  public Object getInfo() {
    return this.info;
  }

  public void setInfo(Object info) {
    this.info = info;
  }

  public Vector<NNode> getChildren() {
    return this.children;
  }

  public void setChildren(Vector<NNode> children) {
    this.children = children;
  }

  /* ************************************************* */

  /**
   * Returns the number of elements in the tree formed by this node and its
   * descendants
   */
  public int size() {
    int size = 1;
    if (children != null)
      for (int i = 0; i < children.size(); i++)
        size += getChildAt(i).size();

    return size;
  }

  /**
   * Prints the tree formed by this node and its descendants following a
   * preorder traversal
   */
  public void preorder() {

    System.out.println("[" + info + "]");

    if (children != null)
      for (int i = 0; i < children.size(); i++)
        getChildAt(i).preorder();

  }

  /* ************************************************* *
   * Other auxiliary methods * *************************************************
   */

  public int getNumberOfChildren() {
    return children.size();
  }

  public boolean hasChildren() {
    return (getNumberOfChildren() > 0);
  }

  public void addChild(NNode child) {
    children.add(child);
  }

  public void addChildAt(int index, NNode child)
      throws IndexOutOfBoundsException {
    children.add(index, child);
  }

  public void removeChildren() {
    this.children = new Vector<NNode>();
  }

  public NNode getChildAt(int index) throws IndexOutOfBoundsException {
    return children.get(index);
  }

  public void removeChildAt(int index) throws IndexOutOfBoundsException {
    children.remove(index);
  }

  public String toString() {
    return getInfo().toString();
  }

  public boolean equals(NNode node) {
    return node.getInfo().equals(getInfo());
  }

}

Exercise Section2.2. Cola con Prioridad utilizando un montículo

Objetivo

Profundizar en el manejo de árboles mediante montículos binarios, implementando una cola de prioridad.

Ejercicio

Un montículo binario es un árbol binario completo ordenado de modo que el dato almacenado en un determinado nodo es menor que los datos almacenados en sus hijos. Esta característica hace que podamos implementarlo usando un vector, garantizando que su profundidad es logarítmica.

Al ser un árbol binario completo puede representarse fácilmente de forma lineal, almacenando su recorrido por niveles (por ejemplo en un Vector ). Dado un elemento situado en la posición i , su hijo izquierdo estará situado en la posición 2i+1 y su hijo derecho en la posición 2i+2 . De forma simétrica, su padre estará en la posición (i-1)/2 . Observa que necesitamos tener también el número de elementos del árbol para comprobar si un nodo existe antes de intentar acceder a su posición. Observe la siguiente figura:

Teniendo en cuenta la descripción anterior:

  • Programa la clase MonticuloBinario que representa un montículo binario, tal como se ha definido previamente, utilizando internamente un Vector para almacenar los datos. Define los atributos de la clase y proporciona un constructor que inicializa un montículo vacío (no recibe parámetros). Observa que cada elemento del montículo almacena dos datos: la prioridad del elemento y el objeto almacenado. Programa la clase auxiliar ElementoColaPrioridad que encapsula esta información

  • Agrega a la clase MonticuloBinario los siguientes métodos: int tamaño(); , que devuelve el número de elementos y boolean isVacio(); , que indica si está vacío el árbol

  • Agrega a la clase MonticuloBinario el método void insertar(int prioridad, Object info); que almacena un nuevo el elemento manteniendo las propiedades de estructura y orden del montículo.

    Para insertar un elemento X en el montículo, primero debemos añadir un nuevo nodo al árbol. Este nodo debe agregarse al final de la estructura para garantizar que continúa siendo completo. Una vez agregado el nuevo elemento en la última posición, hay que comprobar que se mantiene la propiedad de ordenación del montículo. Para ello, hay que comprobar si el nuevo hijo es mayor que su padre. En ese caso, el montículo está ordenado y termina el proceso. Si el nuevo dato es menor que el almacenado en el nodo padre, hay que intercambiarlos y repetir el proceso de comprobación hasta que el dato llegue a un nodo en que se cumpla la propiedad del montículo (padre menor o igual que hijo) o bien a la raíz.

  • Agrega a la clase MonticuloBinario el método Object extraer(); que devuelve el objeto almacenado en la raíz, es decir, con mayor prioridad, y reorganiza el montículo de modo que se mantengan sus propiedades de estructura y orden. Recuerda que las prioridades más altas se corresponden con los valores más pequeños, siendo 1 la prioridad máxima.

    Devolver el objeto buscado es trivial, puesto que las propiedades del montículo garantizan que se encuentra en la raíz.

    La dificultad de este método consiste en reorganizar posteriormente la estructura, puesto que el nodo raíz puede tener dos hijos. Para ello hay que realizar el proceso inverso al "reflotamiento" realizado al insertar, "hundiendo" el "hueco" generado hasta la posición adecuada.

    Para ocupar el lugar que ha quedado vacío, hay que seleccionar el menor de los dos hijos del nodo (si existen). El elemento hijo pasa a ocupar la posición del padre, de modo que el hueco baja un nivel. El proceso se repite sucesivamente hasta llegar a una hoja (un nodo que no tenga hijos).

    El árbol debe seguir siendo completo, de modo que el último elemento pasa a la posición en que ha quedado el hueco.

  • Agrega a la clase MonticuloBinario el método print() , que imprime por pantalla los elementos almacenados junto con su prioridad. Los elementos deben presentarse en orden según su posición en el montículo.

  • Un nodo NodoBB contiene la clave de comparación, la información a almacenar y las referencias a los subárboles izquierdo y derecho.

  • Modifica la definición de la clase MonticuloBinario de modo que implemente el interfaz ColaConPrioridad . 

    interface PriorityQueue {

  static int MAX_PRIORITY = 1;

  /**
   * Insert the indicated object in the correct position in the queue, depending
   * on its priority. Priority is declared with a natural number (> 0). The
   * bigger is this number, the lower is the element priority associated with
   * the number. The value 1 corresponds to elements with maximum priority.
   */
  void insert(int priority, Object info);

  /**
   * Extract the object with highest priority out of the queue (that is, the one
   * with the minimum priority) In case that several elements have the same high
   * priority, the first introduced (FIFO) will be returned. If queue is empty,
   * null is returned.
   */
  Object extract();

  /**
   * Returns the number of elements in the queue.
   */
  int size();

  /**
   * Indicates if the queue is empty.
   */
  boolean isEmpty();

}

  • Utilizando la clase MonticuloBinario desarrollada en los apartados anteriores, completa la clase GestorColaImpresion que gestiona los trabajos a imprimir mediante una cola con prioridad: 

    public class PrintQueueManager {

  PriorityQueue queue;

  /**
   * Initialize the manager, empty.
   */
  public PrintQueueManager() {
    // to be completed by the student
  }

  /**
   * Adds a new work to print, with the indicated priority. *
   */
  public void print(int priority, String file) {
    // to be completed by the student

  }

  /**
   * Processes (prints out of the printer) the first work of the queue, with the
   * highest priority, reorganizing the data structure.
   */
  public void process() {
    // to be completed by the student
  }
}

    Observa que el atributo que almacena la cola se declara de tipo interfaz ColaConPrioridad . La justificación es que el código sea lo más genérico posible. De este modo, si en algún momento se decide utilizar otra implementación de la cola en vez de un montículo, los cambios serán mínimos. Mantén esta filosofía en el código que desarrolles utilizando siempre que sea posible el tipo definido por el interfaz y evitando (en la medida de lo posible) las referencias a la clase que lo implementa.

Solución

Esta es la solución:

heaps.zip