Universidad Carlos III de Madrid

Si recuerdas, un árbol binario de búsqueda es un árbol binario (tiene dos subárboles, izquierdo y derecho) ordenado. Esto significa que los nodos que conforman el árbol siguen cierto orden. Si queremos ordenar los nodos del árbol, vamos a necesitar una clave que nos sirva para saber qué nodo va antes y cuál después.

La ordenación de un árbol binario de búsqueda es tal que, para cada nodo, las claves de los nodos de su subárbol izquierdo son menores (o iguales), mientras que las claves de los nodos de su subárbol derecho son mayores (o iguales).

Con estos conceptos en mente, y apoyándote en los conceptos que aprendiste en la práctica de árboles binarios, vamos a implementar un árbol binario de búsqueda.

Más concretamente, vamos a hacer una implementación de la interfaz BSTree<E> (Binary Search Tree) que se muestra a continuación, usando nodos enlazados como en la práctica anterior. Por tanto, nuestro árbol binario de búsqueda estará representado por la clase LBSTree<E>.

public interface BSTree<E> {

    boolean isEmpty();

    E getInfo();
    Comparable getKey();
    BSTree<E> getLeft();
    BSTree<E> getRight();

    String toStringPreOrder();
    String toStringInOrder();
    String toStringPostOrder();
    String toString(); // pre-order

    void insert(Comparable key, E info);

    BSTree<E> search(Comparable key);
}

Antes de empezar a implementar la clase LBSTree<E>, necesitas definir la clase que representará a los nodos que componen el árbol. Completa el siguiente esqueleto para la clase LBSNode<E> que representará dichos nodos.

public class LBSNode<E> {

    private E info;
    private Comparable key;
    private BSTree<E> right;
    private BSTree<E> left;

    public LBSNode(Comparable key, E info, BSTree<E> left, BSTree<E> right;) {
        /* your code here */
    }

    /** Get and set methods */

    public String toString() {
        if(info != null) {
            return info.toString();
        } else {
            return "";
        }
    }
}

Presta especial atención al atributo key. Si te fijas, el tipo de este atributo es Comparable. Consulta la API de esta interfaz. ¿Qué método tendrá que implementar cualquier key de forma que implemente correctamente dicha interfaz? Consulta la API de las clases String e Integer. ¿Implementan la interfaz Comparable? ¿Se podrán usar como key?

A continuación, vamos a implementar el árbol binario de búsqueda en sí. Observa la interfaz BSTree<E>, y contesta a las preguntas:

Comienza a implementar la clase LBSTree<E>:

Hasta ahora tenemos el esqueleto de nuestra nueva clase LBSTree<E>. En este apartado vamos a completarla, codificando los dos métodos principales: insert y search.

Finalmente, prueba tu implementación con la clase LBSTreeTest.

Ahora que ya tenemos implementado nuestro árbol binario de búsqueda, vamos a ver un ejemplo de uso. En este caso, vamos a implementar una agenda telefónica.

La clave con la que vamos a ordenar la agenda es por apellidos y nombre, de forma que se ordenará primero por primer apellido, si son iguales, por segundo, y si son iguales, por nombre. Para realizar esta ordenación necesitamos una clase que llamaremos Name y que va a implementar la interfaz Comparable. Recuerda la API de la interfaz Comparable. ¿Qué método tendrá que implementar la clase Name para implementar correctamente dicha interfaz?

Completa el siguiente esqueleto de código de forma que si el objeto que se compara (this) es alfabéticamente anterior al argumento que recibe el método de comparación, se devuelva -1, si son iguales, 0, y si es posterior, 1. Recuerda que un nombre es anterior a otro si su primer apellido va antes en orden alfabético, si son iguales se compara el segundo apellido, y si son iguales, se compara el nombre.

class Name implements Comparable {

    private String name;
    private String firstSurname;
    private String secondSurname;

    public Name(String name, String firstSurname, String secondSurname) {
        this.name = name;
        this.firstSurname = firstSurname;
        this.secondSurname = secondSurname;
    }

    public String getName() {
        return this.name;
    }

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

    public String getFirstSurname() {
        return this.firstSurname;
    }

    public void setFirstsurame(String firstSurname) {
        this.firstSurname = firstSurname;
    }

    public String getSecondSurname() {
        return this.secondSurname;
    }

    public void setSecondSurname(String secondSurname) {
        this.secondSurname = secondSurname;
    }

    public String toString() {
        return this.firstSurname+" "+this.secondSurname+", "+this.name;
    }

    public int compareTo(Object anotherName){
        /** Your code here */
    }
}

Ya tenemos la clave de ordenación que vamos a utilizar. Ahora necesitamos almacenar todos los datos de cada persona que va a aparecer en nuestra agenda de teléfonos, para lo que usaremos la clase Contact. Completa el siguiente esqueleto con el código necesario en el constructor, y los los métodos de acceso y modificación para todos y cada uno de los atributos.

class Contact {

    private Name name;
    private int phoneNumber;
    private String postalAddress;

    public Contact(String name, String firstSurname, String secondSurname,
                        int phoneNumber, String postalAdress) {
        /** Your code here */
    }

    /** Get and set methods for every attribute */

    public String toString() {
        String contactStr = this.name.toString();
        contactStr = contactStr+"\nPhone: "+this.phoneNumber;
        contactStr = contactStr+"\nAddress: "+this.postalAddress;
        return contactStr;
    }
}

Finalmente, implementaremos nuestra agenda telefónica, PhoneAgenda haciendo uso de un árbol binario de búsqueda para que las búsquedas sean rápidas y eficientes. Implementa dicha clase siguiendo estas directrices: