5 Árboles¶

Introducción¶

Los árboles se caracterizan por almacenar sus nodos en forma jerárquica y no en forma lineal como las listas

Un árbol es una estructura en la que los datos se organizan en nodos. Los árboles binarios son aquellos en los que un nodo solamente puede tener dos hijos como máximo. Se utilizan para ordenar datos, de tal manera que a la izquierda se colocan los valores menores y a la derecha los valores mayores. Un árbol binario se puede recorrer de varias formas, siendo el recorrido inorden el que muestra los datos ordenados: subárbol izquierdo, raíz, subárbol derecho. Veamos un ejemplo.

Nos posicionamos en el 9. Mientras tenga subárbol izquierdo vamos avanzando hasta llegar al 1. Como es una hoja, la mostramos: el 1. Luego mostramos la raíz: el 3. Después, continuamos con el subárbol derecho. Nos encontramos con el 6, pero tiene subárbol izquierdo, así avanzamos hasta el 4. Como es una hoja, los mostramos: el 4. Luego, continuamos con la raíz: el 6. Después, continuamos con el subárbol derecho, avanzando hasta el 7. Como es hoja, lo mostramos: el 7. Ya hemos tratado todo el subárbol izquierdo del 8, que es la raíz. Ahora mostramos la raíz: el 8 y a continuación comenzamos con el subárbol derecho del 8. Y así sucesivamente. El resultado final es: 1,3,4,6,7,8,10,13 y 14, es decir, los elementos ordenador de menor a mayor.

Si queremos introducir un nuevo nodo en el árbol, hay que tener en cuidado de no romper la estructura ni el orden del árbol. Hay que tener en cuenta que cada nodo nunca se podrá insertar como su hijo. Con esta restricción nos aseguramos de mantener la estructura del árbol, pero aún nos falta mantener el orden. Para localizar el lugar adecuado del árbol donde insertar el nuevo nodo se realizan comparaciones entre los nodos del árbol y el elemento a insertar. El primer nodo que se compara es el nodo raíz, si el nuevo nodo es menor que el raíz, la búsqueda prosigue por el lado izquierdo de éste. Si el nuevo nodo fuese mayor, la búsqueda seguiría por el hijo derecho. Y así, sucesivamente hasta llegar a un nodo que no tenga hijo en la rama por la que la búsqueda debería seguir. En este caso, el nuevo nodo se inserta en ese hueco, como su nuevo hijo.

Por ejemplo, queremos insertar el elemento 9. Lo primero es comparar el nuevo elemento con el nodo raíz. Como 9 > 8, entonces la búsqueda prosigue por el lado derecho. Ahora el nuevo nodo se compara con el elemento 10. En este caso 9 < 10, por lo que hay que continuar la búsqueda por la rama izquierda. Como la rama izquierda de 10 no tiene ningún nodo, se inserta en ese lugar el nuevo nodo.

La interfaz SortedSet<E> es la encargada de definir esta estructura. Esta interfaz es hija de Set<E>, que a su vez es hija de Collection<E>, que a su vez es hija de `Iterable. Por lo tanto, tiene los métodos de todas y además añade sus propios métodos.

E first(): devuelve el elemento más pequeño.
E last(): devuelve el elemento más grande.
SortedSet<E> headSet(E toElement): devuelve un SortedSet que contendrá todos los elementos menores que toElement.
SortedSet<E> tailSet(E fromElement): devuelve un SortedSet que contendrá todos los elementos mayores que fromElement.
SortedSet<E> subSet(E fromElement, E toElement): devuelve un SortedSet que contendrá los elementos que van desde fromElement incluido haste toElement excluido.

Pero, ¿cómo ordenamos los elementos por ejemplo vehículos? Para ello, Java nos proporciona dos interfaces: Comparable<T> y Comparator<T>. La diferencia entre ambas es que Comparable se implementa desde la propia clase que se quiere ordenar y Comparator^ no.

Interfaz Comparable¶

La interfaz Comparable contiene un único método, el método compareTo, que recibe un objeto de la misma clase y que debe realizar una comparación entre ambos objetos, retornando un valor entero negativo, cero o positivo, dependiendo de si el objeto sobre el que se ejecuta es respectivamente, menor, igual o mayor que el objeto recibido.

La definición de la interfaz es la siguiente:

public interface Comparable<T>{
    int compareTo(T o);
}

Por ejemplo, si quisiéramos crear un árbol para ordenar los vehículos lo primero que tendríamos que hacer es que la clase Vehicle implemente la interfaz Comparable y que el método compareTo ordene por el atributo que deseemos. Por ejemplo, vamos a ordenar vehículos alfabéticamente por el color. Como el color es de tipo String, debemos utilizar el compareTo de la clase String:

VehicleMain

public class Vehicle implements Comparable<Vehicle> {
    private String registration;
    private int wheelCount;
    private double speed;
    private String colour;

    public Vehicle(String registration, int wheelCount, String colour) {
        this.registration = registration;
        this.wheelCount = wheelCount;
        this.colour = colour;
        speed = 0;
    }

    public int getWheelCount() {
        return wheelCount;
    }

    public double getSpeed() {
        return speed;
    }

    public String getColour() {
        return colour;
    }

    public void setColour(String colour) {
        this.colour = colour;
    }

    public String getRegistration() {
        return registration;
    }

    public void accelerate(double amount) {
        speed += amount;
    }

    public void brake(double amount) {
        speed -= amount;
    }

    @Override
    public String toString() {
        return "Vehicle [registration=" + registration + ", wheelCount=" +  wheelCount + ", speed=" + speed + ", colour="
                + colour + "]";
    }

    @Override
    public int compareTo(Vehicle o) {
        return colour.compareTo(o.colour);
    }
}

public class Compare{
    public void show(){
        Vehicle v1 = new Vehicle("9685KMX", 4, "azul");
        Vehicle v2 = new Vehicle("1235GTR", 2, "rojo");
        Vehicle v3 = new Vehicle("7314QWE", 4, "rojo");

        System.out.println(v1.compareTo(v2)); // positivo -> v1 > v2
        System.out.println(v2.compareTo(v1)); // negativo -> v2 < v1
        System.out.println(v1.compareTo(v3)); // 0 -> v1 == v3
    }

    public static void main(String[] args){
        new Compare().show();
    }
}

Interfaz Comparator¶

La interfaz Comparator<T> es una interfaz que define el método compareal que se le pasan los dos objetos a comparar y cuyo resultado es como el del compareTo (0 si son iguales, positivo si el primero es mayor y negativo si el segundo es mayor). Para definir un comparador de este forma, hay que crear una clase que implemente esta interfaz y definir el método compare, después crear un objeto de ese tipo y usarlo.

VehicleComparatorMain

public class VehicleComparator implements Comparator<Vehicle>{
    @Override
    public int compare(Vehicle o1, Vehicle o2){
        return o1.getColour().compareTo(o2.getColour());
    }
}

public class Comparator{
    public void show(){
        Vehicle v1 = new Vehicle("9685KMX", 4, "azul");
        Vehicle v2 = new Vehicle("1235GTR", 2, "rojo");
        Vehicle v3 = new Vehicle("7314QWE", 4, "rojo");
        VehicleComparator comparator = new VehicleComparator();

        System.out.println(comparator.compare(v1, v2)); // positivo -> v1 > v2
        System.out.println(comparator.compare(v2, v1)); // negativo -> v2 < v1
        System.out.println(comparator.compare(v1, v3)); // 0 -> v1 == v3
    }

    public static void main(String[] args){
        new Comparator().show();
    }
}

Si dicha clase, solo va a ser utilizada una única vez, se recomienda usar una clase anónima en línea:

public class ComparatorAnonymous{
    public void show(){
        Vehicle v1 = new Vehicle("9685KMX", 4, "azul");
        Vehicle v2 = new Vehicle("1235GTR", 2, "rojo");
        Vehicle v3 = new Vehicle("7314QWE", 4, "rojo");
        Comparator comparator = new Comparator<Vehicle>(){
                @Override
                public int compare(Vehicle o1, Vehicle o2){
                    return o1.getColour().compareTo(o2.getColour());
                }
            };

        System.out.println(comparator.compare(v1, v2)); // positivo -> v1 > v2
        System.out.println(comparator.compare(v2, v1)); // negativo -> v2 < v1
        System.out.println(comparator.compare(v1, v3)); // 0 -> v1 == v3
    }

    public static void main(String[] args){
        new ComparatorAnonymous().show();
    }
}

Para ordenar descendientemente se cambiaría el orden de o1 por el de o2.

Usos de comparable y comparator¶

Cuando creemos clases que representen valores que posean un determinado orden natural, como por ejemplo un orden alfabético, numérico o cronológico, deberemos hacer que dicha clase implemente la interfaz Comparable, permitiendo así que los objetos de dicha clase puedan trabajar con mucho algoritmos genéricos e implementaciones de colecciones que dependen de dicha interfaz.

La mayoría de las clases estándar que representan valores y de las clases enums incorporadas a Java, implementan la interfaz Comparable, como por ejemplo la clase String. Las clases que definamos nosotros que representen valores también deberían implementarla.

A la hora de realizar la implementación debemos respetar una serie de reglas:

x.compareTo(y) == -y.compareTo(x) para todo valor de x e y .
La relación es transitiva, es decir, que si (x. compareTo(y) > 0 && y.compareTo(z) >0) entonces x.compareTo(z) > 0.
Si x.compareTo(y) == 0 entonces x.compareTo(z) == y.compareTo(z) para cualquier valor de z.
Aunque no es obligatorio se recomienda que (x.compareTo(y) == 0) == (x.equals(y)).

Si para comparar los objetos debemos comparar un atributo de un tipo primitivo, se recomienda usar los métodos estáticos de comparación compare de las clases boxed correspondientes, como Long.compare(), Float.compare(), etc., disponibles a partir de Java 7, en vez de usar los operadores < o >, ya que son menos verbosos y propensos al error:

Clase TreeSet¶

La clase TreeSet<E> es la que se utiliza prioritariamente para trabajar con árboles ordenados ya que implementa la interfaz SortedSet<E>.

Los objetos a incluir en un TreeSet deben implementar Comparable o bien crear el árbol con un constructor que reciba un Comparator

Ejemplo:

VehicleMainConsola

public class Vehicle implements Comparable<Vehicle> {
    private String registration;
    private int wheelCount;
    private double speed;
    private String colour;

    public Vehicle(String registration, int wheelCount, String colour) {
        this.registration = registration;
        this.wheelCount = wheelCount;
        this.colour = colour;
        speed = 0;
    }

    public int getWheelCount() {
        return wheelCount;
    }

    public double getSpeed() {
        return speed;
    }

    public String getColour() {
        return colour;
    }

    public void setColour(String colour) {
        this.colour = colour;
    }

    public String getRegistration() {
        return registration;
    }

    public void accelerate(double amount) {
        speed += amount;
    }

    public void brake(double amount) {
        speed -= amount;
    }

    @Override
    public String toString() {
        return "Vehicle [registration=" + registration + ", wheelCount=" +  wheelCount + ", speed=" + speed + ", colour="
                + colour + "]";
    }

    @Override
    public int compareTo(Vehicle o) {
        return colour.compareTo(o.colour);
    }
}

public class TreeSet1{
    public void show(){
        SortedSet<Vehicle> tree = new TreeSet<>();
        tree.add(new Vehicle("9685KMX", 4, "azul"));
        tree.add(new Vehicle("1235GTR", 2, "rojo"));
        tree.add(new Vehicle("7314QWE", 4, "verde"));
        tree.add(new Vehicle("5930POI", 2, "negro"));
        tree.add(new Vehicle("1705UBG", 4, "blanco"));
        tree.add(new Vehicle("3495JZA", 2, "naranja"));

        for(Vehicle v: tree){
            System.out.println(v);
        }
    }

    public static void main(String[] args){
        new TreeSet1().show();
    }
}

Vehicle [registration=9685KMX, wheelCount=4, speed=0.0, colour=azul]
Vehicle [registration=1705UBG, wheelCount=4, speed=0.0, colour=blanco]
Vehicle [registration=3495JZA, wheelCount=2, speed=0.0, colour=naranja]
Vehicle [registration=5930POI, wheelCount=2, speed=0.0, colour=negro]
Vehicle [registration=1235GTR, wheelCount=2, speed=0.0, colour=rojo]
Vehicle [registration=7314QWE, wheelCount=4, speed=0.0, colour=verde]

Pero, ¿qué ocurriría si tuviéramos colores repetidos?:

MainConsola

import java.util.SortedSet;
import java.util.TreeSet;

public class TreeSet2 {
    public void show() {
        SortedSet<Vehicle> tree = new TreeSet<>();

        tree.add(new Vehicle("9685KMX", 4, "azul"));
        tree.add(new Vehicle("1235GTR", 2, "rojo"));
        tree.add(new Vehicle("7314QWE", 4, "verde"));
        tree.add(new Vehicle("5930POI", 2, "azul"));
        tree.add(new Vehicle("1705UBG", 4, "rojo"));
        tree.add(new Vehicle("3495JZA", 2, "verde"));

        for (Vehicle v : tree) {
            System.out.println(v);
        }
    }

    public static void main(String[] args) {
        new TreeSet2().show();
    }
}

Vehicle [registration=9685KMX, wheelCount=4, speed=0.0, colour=azul]
Vehicle [registration=1235GTR, wheelCount=2, speed=0.0, colour=rojo]
Vehicle [registration=7314QWE, wheelCount=4, speed=0.0, colour=verde]

Los tres primero vehículos se introducen en el árbol. Cuando se va a introducir el cuarto que es de color azul, el árbol lo va comparando con compareTo con los vehículos que ya existen el árbol para encontrar la posición ordenada donde incluirlo. Pero cuando lo compara con el que es azul, el compareTo, devuelve 0, por lo que el árbol interpreta que ese objeto ya existe en el árbol, que es igual a otro, por lo tanto no lo incluye en el árbol. Lo mismo ocurre con el quinto y el sexto. Por lo tanto, lo que ocurriría es que los 3 últimos no se introducen en el árbol porque compareTo devuelve 0 entre vehículos del mismo color, por lo que el árbol considera que son iguales. En estos casos, lo que se hace es que se incluye un segundo criterio de comparación: vamos a ordenar por el color, y en aquellos casos donde los vehículos tengan el mismo color entonces vamos a ordenar por matrícula.

VehicleMainConsola

public class Vehicle implements Comparable<Vehicle>{
    //...

    @Override
    public int compareTo(Vehicle o){
        int result = colour.compareTo(o.colour);

        if(result == 0){
            result = registration.compareTo(o,registration);
        }

        return result;
    }
}

import java.util.SortedSet;
import java.util.TreeSet;
public class ShowTreeSet {
    public void show() {
        SortedSet<Vehicle> tree = new TreeSet<>();

        tree.add(new Vehicle("9685KMX", 4, "azul"));
        tree.add(new Vehicle("1235GTR", 2, "rojo"));
        tree.add(new Vehicle("7314QWE", 4, "verde"));
        tree.add(new Vehicle("5930POI", 2, "azul"));
        tree.add(new Vehicle("1705UBG", 4, "rojo"));
        tree.add(new Vehicle("3495JZA", 2, "verde"));

        for (Vehicle v : tree) {
            System.out.println(v);
        }
    }

    public static void main(String[] args) {
        new ShowTreeSet().show();
    }
}

Vehicle [registration=5930POI, wheelCount=2, speed=0.0, colour=azul]
Vehicle [registration=9685KMX, wheelCount=4, speed=0.0, colour=azul]
Vehicle [registration=1235GTR, wheelCount=2, speed=0.0, colour=rojo]
Vehicle [registration=1705UBG, wheelCount=4, speed=0.0, colour=rojo]
Vehicle [registration=3495JZA, wheelCount=2, speed=0.0, colour=verde]
Vehicle [registration=7314QWE, wheelCount=4, speed=0.0, colour=verde]

Pero, ¿qué ocurriría si la clase Vehicle no implementase la interfaz Comparable? Pues que no contendría el método compareTo, entonces el árbol no tendría la información de cómo ordenar los vehículos. En este caso, se lanzaría una excepción ClassCastException.

VehicleMainConsola

public class Vehicle{
    //...

    // No contiene el método compareTo
}

import java.util.SortedSet;
import java.util.TreeSet;

public class ShowException{

    public void show(){
        SortedSet<Vehicle> = new TreeSet<>();
        tree.add(new Vehicle("9685KMX", 4, "azul"));
        tree.add(new Vehicle("1235GTR", 2, "rojo"));
        tree.add(new Vehicle("7314QWE", 4, "verde"));
        tree.add(new Vehicle("5930POI", 2, "negro"));
        tree.add(new Vehicle("1705UBG", 4, "blanco"));
        tree.add(new Vehicle("3495JZA", 2, "naranja"));

        for(Vehicle v: tree){
            System.out.println(v);
        }
    }

    public static void main(String[] args){
        new ShowException().show();
    }
}

Exception in thread "main" java.lang.ClassCastException: class 
tema11_Colecciones.arboles3.Vehicle cannot be cast to class
java.lang.Comparable (tema11_Colecciones.arboles3.Vehicle is in unnamed module
of loader 'app'; java.lang.Comparable is in module java.base of loader
'bootstrap')
at java.base/java.util.TreeMap.compare(TreeMap.java:1291)
at java.base/java.util.TreeMap.put(TreeMap.java:536)
at java.base/java.util.TreeSet.add(TreeSet.java:255)
at tema11_Colecciones.arboles3.ShowException.show(ShowException.java:11)
at tema11_Colecciones.arboles3.ShowException.main(ShowException.java:25)

Otra posibilidad es utilizar un objeto Comparator<E>. Para ello, se crea la clase que implementa dicha interfaz y se usaría en la construcción del árbol mediante un constructor que recibe un Comparator: TreeSet(Comparator<? super E> comparator). En este caso, ésa será la forma prioritaria para ordenar la lista, por encima del método compareTo de la interfaz Comparable. Como ya dijimos anteriormente, la diferencia entre Comparable y Comparator es que Comparable se implementa desde la propia clase que se quiere ordenar y Comparator no, ya que Comparator se implementa desde otra clase distinta a la que se quiere ordenar:

VehicleComparatorMainConsola

import java.util.comparator;

public class VehicleComparator implements Comparator<Vehicle>{

    @Override
    public int compare(Vehicle o1, Vehicle o2){
        int result = o1.getColour().compareTo(o2.getColour());

        if(result == 0){
            result = o1.getRegistration().compareTo(o2.getRegistration());
        }

        return result;
    }
}

import java.util.SortedSet;
import java.util.TreeSet;

public class ShowComparator {
    public void show() {
        SortedSet<Vehicle> tree = new TreeSet<>(new VehicleComparator());

        tree.add(new Vehicle("9685KMX", 4, "azul"));
        tree.add(new Vehicle("1235GTR", 2, "rojo"));
        tree.add(new Vehicle("7314QWE", 4, "verde"));
        tree.add(new Vehicle("5930POI", 2, "azul"));
        tree.add(new Vehicle("1705UBG", 4, "rojo"));
        tree.add(new Vehicle("3495JZA", 2, "verde"));

        for (Vehicle v : tree) {
            System.out.println(v);
        }
    }

    public static void main(String[] args) {
        new ShowComparator().show();
    }
}

Vehicle [registration=5930POI, wheelCount=2, speed=0.0, colour=azul]
Vehicle [registration=9685KMX, wheelCount=4, speed=0.0, colour=azul]
Vehicle [registration=1235GTR, wheelCount=2, speed=0.0, colour=rojo]
Vehicle [registration=1705UBG, wheelCount=4, speed=0.0, colour=rojo]
Vehicle [registration=3495JZA, wheelCount=2, speed=0.0, colour=verde]
Vehicle [registration=7314QWE, wheelCount=4, speed=0.0, colour=verde]

Pero si esta comparación la vamos a utilizar solamente una vez, tenemos que crear una clase solamente para su uso. Y si necesitamos ordenar los vehículos de varias maneras, tenemos que tener una clase por cada criterio de ordenación. En estos casos, podemos utilizar una clase inline anónima:

MainConsola

import java.util.Comparator;
import java.util.SortedSet;
import java.util.TreeSet;

public class AnonymousComparator {
    public void show() {
        SortedSet<Vehicle> tree = new TreeSet<>(new Comparator<Vehicle>(){
            @Override
            public int compare(Vehicle o1, Vehicle o2){
                int result = o1.getColour().compareTo(o2.getColour());

                if(result == 0){
                    result = o1.getRegistration().compareTo(o2.getRegistration());
                }

                return result;
            }
        });

        tree.add(new Vehicle("9685KMX", 4, "azul"));
        tree.add(new Vehicle("1235GTR", 2, "rojo"));
        tree.add(new Vehicle("7314QWE", 4, "verde"));
        tree.add(new Vehicle("5930POI", 2, "azul"));
        tree.add(new Vehicle("1705UBG", 4, "rojo"));
        tree.add(new Vehicle("3495JZA", 2, "verde"));

        for (Vehicle v : tree) {
            System.out.println(v);
        }
    }

    public static void main(String[] args) {
        new AnonymousComparator().show();
    }
}

Vehicle [registration=5930POI, wheelCount=2, speed=0.0, colour=azul]
Vehicle [registration=9685KMX, wheelCount=4, speed=0.0, colour=azul]
Vehicle [registration=1235GTR, wheelCount=2, speed=0.0, colour=rojo]
Vehicle [registration=1705UBG, wheelCount=4, speed=0.0, colour=rojo]
Vehicle [registration=3495JZA, wheelCount=2, speed=0.0, colour=verde]
Vehicle [registration=7314QWE, wheelCount=4, speed=0.0, colour=verde]

Si quisiéramos ordenar de manera descendente, cambiamos el orden entre o1 y o2, es decir, hacemos que sea o2 el que ejecute el compareTo

MainConsola

import java.util.Comparator;
import java.util.SortedSet;
import java.util.TreeSet;

public class DescendingOrder {
    public void show() {
        SortedSet<Vehicle> tree = new TreeSet<>(new Comparator<Vehicle>(){
            /*
             * Si quisiéramos ordenar de manera descendente,
             * cambiamos el orden entre o1 y o2, es decir,
             * hacemos que sea o2 el que ejecute el compareTo
             */
            @Override
            public int compare(Vehicle o1, Vehicle o2){
                int result = o2.getColour().compareTo(o1.getColour());

                if(result == 0){
                    result = o2.getRegistration().compareTo(o1.getRegistration());
                }

                return result;
            }
        });

        tree.add(new Vehicle("9685KMX", 4, "azul"));
        tree.add(new Vehicle("1235GTR", 2, "rojo"));
        tree.add(new Vehicle("7314QWE", 4, "verde"));
        tree.add(new Vehicle("5930POI", 2, "azul"));
        tree.add(new Vehicle("1705UBG", 4, "rojo"));
        tree.add(new Vehicle("3495JZA", 2, "verde"));

        for (Vehicle v : tree) {
            System.out.println(v);
        }
    }

    public static void main(String[] args) {
        new DescendingOrder().show();
    }
}

Vehicle [registration=5930POI, wheelCount=2, speed=0.0, colour=azul]
Vehicle [registration=9685KMX, wheelCount=4, speed=0.0, colour=azul]
Vehicle [registration=1235GTR, wheelCount=2, speed=0.0, colour=rojo]
Vehicle [registration=1705UBG, wheelCount=4, speed=0.0, colour=rojo]
Vehicle [registration=3495JZA, wheelCount=2, speed=0.0, colour=verde]
Vehicle [registration=7314QWE, wheelCount=4, speed=0.0, colour=verde]

Los comparadores de tipo Comparator permiten ordenar de diferentes formas, por eso en la práctica se utilizan mucho. Por ejemplo, el método sort de la clase Arrays también admite indicar un comparador para saber de qué forma deseamos ordenar el array.

CompareBoxedClassesConsola

import java.util.Comparator;
import java.util.SortedSet;
import java.util.TreeSet;

public class CompareBoxedClasses {
    public void show() {
        SortedSet<Vehicle> tree = new TreeSet<>(new Comparator<Vehicle>() {

            @Override
            public int compare(Vehicle o1, Vehicle o2) {
                int result = Integer.compare(o1.getWheelCount(), o2.getWheelCount());
                if (result == 0) {
                    result = Double.compare(o1.getSpeed(), o2.getSpeed());
                }
                return result;
            }
        });

        Vehicle vehicles[] = new Vehicle[6];

        vehicles[0] = new Vehicle("9685KMX", 4, "azul");
        vehicles[0].accelerate(100);

        vehicles[1] = new Vehicle("1235GTR", 2, "rojo");
        vehicles[1].accelerate(150);

        vehicles[2] = new Vehicle("7314QWE", 4, "verde");
        vehicles[2].accelerate(200);

        vehicles[3] = new Vehicle("5930POI", 2, "negro");
        vehicles[3].accelerate(80);

        vehicles[4] = new Vehicle("1705UBG", 4, "blanco");
        vehicles[4].accelerate(75);

        vehicles[5] = new Vehicle("3495JZA", 2, "naranja");
        vehicles[5].accelerate(170);

        for (int i = 0; i < vehicles.length; i++) {
            tree.add(vehicles[i]);
        }

        for (Vehicle v : tree) {
            System.out.println(v);
        }
    }

    public static void main(String[] args) {
        new CompareBoxedClasses().show();
    }
}

Vehicle [registration=5930POI, wheelCount=2, speed=80.0, colour=negro]
Vehicle [registration=1235GTR, wheelCount=2, speed=150.0, colour=rojo]
Vehicle [registration=3495JZA, wheelCount=2, speed=170.0, colour=naranja]
Vehicle [registration=1705UBG, wheelCount=4, speed=75.0, colour=blanco]
Vehicle [registration=9685KMX, wheelCount=4, speed=100.0, colour=azul]
Vehicle [registration=7314QWE, wheelCount=4, speed=200.0, colour=verde]

Clase TreeMap¶

Esta implementación utiliza una estructura de árbol que permite que los elementos del mapa se ordenen en sentido ascendente según la clave, por lo tanto, la clase de las claves tiene que implementar la interfaz Comparable o bien indicar un objeto Comparator durante la creación del TreeMap.

TreeMap implementa la interfaz SortedMap que, a su vez, es heredera de Map , por lo que todo lo dicho sobre los mapas funciona con las colecciones de tipo TreeMap.

MainConsola

import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;

public class ShowTreeMap {
    public void show() {
        SortedMap<String, Vehicle> sortedMap = new TreeMap<>();

        Vehicle vehicles[] = new Vehicle[6];

        vehicles[0] = new Vehicle("9685KMX", 4, "azul");
        vehicles[1] = new Vehicle("1235GTR", 2, "rojo");
        vehicles[2] = new Vehicle("7314QWE", 4, "verde");
        vehicles[3] = new Vehicle("5930POI", 2, "negro");
        vehicles[4] = new Vehicle("1705UBG", 4, "blanco");
        vehicles[5] = new Vehicle("3495JZA", 2, "naranja");

        for (int i = 0; i < vehicles.length; i++) {
            sortedMap.put(vehicles[i].getRegistration(), vehicles[i]);
        }

        for (Map.Entry<String, Vehicle> entry : sortedMap.entrySet()) {
            System.out.printf("Matrícula -> %s Vehículo -> %s\n", entry.getKey(), entry.getValue());
        }
    }

    public static void main(String[] args) {
        new ShowTreeMap().show();
    }

Matrícula -> 1235GTR Vehículo -> Vehicle [registration=1235GTR, wheelCount=2, 
speed=0.0, colour=rojo]
Matrícula -> 1705UBG Vehículo -> Vehicle [registration=1705UBG, wheelCount=4,
speed=0.0, colour=blanco]
Matrícula -> 3495JZA Vehículo -> Vehicle [registration=3495JZA, wheelCount=2,
speed=0.0, colour=naranja]
Matrícula -> 5930POI Vehículo -> Vehicle [registration=5930POI, wheelCount=2,
speed=0.0, colour=negro]
Matrícula -> 7314QWE Vehículo -> Vehicle [registration=7314QWE, wheelCount=4,
speed=0.0, colour=verde]
Matrícula -> 9685KMX Vehículo -> Vehicle [registration=9685KMX, wheelCount=4,
speed=0.0, colour=azul]

Como podemos observar, está ordenado ascendentemente por la matrícula ya que la matrícula es de tipo String que implementa la interfaz Comparable. Si la clave fuera una clase hecha por nosotros, tendríamos que hacer que implementara Comparable o bien indicar un Comparator en la creación del TreeMap.