Árboles

Tabla de contenidos

1. Trabajo en el laboratorio

1.1. Árbol binario de búsqueda

2. Actividades para casa

2.1. Cola con Prioridad utilizando un montículo

1. Trabajo en el laboratorio

TOTAL: 90 min

1.1. Árbol binario de búsqueda

90 min

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"
		       + "--------------";
	}

	
}

2. Actividades para casa

220 min

2.1. Cola con Prioridad utilizando un montículo

150 min

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 ColaConPrioridad {

    static int PRIORIDAD_MAXIMA = 1;

    /**
     * Insertar el objeto indicado en la posición adecuada de la cola 
     * según su prioridad.
     * La prioridad se indica mediante un número natural (> 0).
     * Cuanto mayor es dicho número, menor es la prioridad del elemento 
     * asociado. El valor 1 corresponde a los elementos con prioridad máxima.
     */
    void insertar(int prioridad, Object info);

    /**
     * Extrae el objeto con mayor prioridad de la cola 
     * (es decir, aquél cuya prioridad tenga valor mínimo)
     * En el caso de que varios elementos tengan la misma prioridad, 
     * se devuelve el primero que se introdujo (FIFO).
     * Si la cola está vacía, devuelve null.
     */
    Object extraer();

    /**
     * Devuelve el número de elementos de la cola
     */
    int tamaño();

    /**
     * Indica si la cola está vacía.
     */
    boolean isVacio();

}

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  GestorColaImpresion {

    ColaConPrioridad cola;

    /**
     * Inicializa el gestor, vacío.
     */
    public GestorColaImpresion() {
        // completar
    }

    /**
     * Agrega un nuevo trabajo de impresión, con la prioridad indicada.
     */
    public void imprimir(int prioridad, String fichero) {
        // completar
    }

    /**
     * Procesa (saca por impresora) el primer trabajo de la cola, con prioridad máxima, 
     * reorganizando adecuadamente la estructura de datos. 
     */
    public void procesar() {
        // completar
    }

    // NOTA: en versiones previas de este enunciado se incluía un
    // método llamado eliminarTrabajo(). Se trataba de un error en el
    // enunciado, dado que no tenía sentido su implementación.

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

Universidad Carlos III de Madrid

Ingeniería de Telecomunicación

Enero-Mayo 2010 / January-May 2010

Árboles

1. Trabajo en el laboratorio

1.1. Árbol binario de búsqueda

Objetivo

Ejercicio

Solución

2. Actividades para casa

2.1. Cola con Prioridad utilizando un montículo

Objetivo

Ejercicio

Solución