Cuando trabajamos con estructuras de datos en Java, una de las implementaciones más interesantes y útiles es la de un árbol binario de búsqueda (BST). En lugar de limitarnos a tipos simples como enteros, podemos aprovechar la potencia de los objetos complejos para organizar datos más ricos, como empleados, libros o cualquier entidad que necesite ser almacenada y buscada eficientemente.
Para que un árbol binario de búsqueda funcione correctamente con objetos, es fundamental que estos puedan compararse entre sí. En el caso de empleados, por ejemplo, no podemos simplemente decir que un empleado es menor o mayor que otro sin definir un criterio claro. Aquí es donde entra en juego la interfaz Comparable de Java, que nos permite definir un método compareTo para establecer un orden entre objetos.
El método compareTo debe devolver un número negativo si el objeto actual es menor que el que se pasa como parámetro, un número positivo si es mayor, y cero si son iguales. Para empleados, podemos usar un identificador único, como un código o DNI, como clave para esta comparación. Así, si dos empleados tienen el mismo código, serán considerados iguales, y si uno tiene un código menor, será menor en el árbol.
Implementar esta interfaz nos facilita mucho la vida, porque luego podemos usar compareTo directamente para decidir dónde insertar un nuevo nodo en el árbol, sin preocuparnos por comparar manualmente cada atributo.
Al diseñar nuestro BST, podemos aprovechar la programación genérica para que el árbol sea flexible y pueda manejar cualquier tipo de objeto que implemente Comparable. Esto nos permite reutilizar la estructura para diferentes tipos de datos sin cambiar la lógica interna.
En cuanto a la estructura interna del árbol, cada nodo debe contener un valor (en nuestro caso, un empleado) y referencias a sus subárboles izquierdo y derecho. Inicialmente, estos pueden ser null, indicando que no hay nodos hijos. Para determinar si un árbol está vacío, simplemente comprobamos si el valor es null. Para saber si un nodo es hoja, verificamos que tenga un valor y que ambos subárboles sean null.
La inserción en el árbol se realiza de forma recursiva. Si el árbol está vacío, insertamos el nuevo empleado directamente en el nodo actual. Si no, comparamos el empleado a insertar con el valor del nodo actual usando compareTo. Si es menor, intentamos insertarlo en el subárbol izquierdo; si es mayor, en el derecho. Antes de hacer la llamada recursiva, debemos asegurarnos de que el subárbol correspondiente no sea null. Si lo es, creamos un nuevo nodo para continuar la inserción.
En caso de que el empleado a insertar tenga un identificador igual al de un nodo ya existente, podemos decidir no hacer nada para evitar duplicados, lanzar una excepción o manejarlo según convenga. En nuestro ejemplo, optamos por no hacer nada silenciosamente.
Aquí podemos ver cómo quedaría el método de inserción en Java, usando genéricos y la interfaz Comparable:
public class BST<T extends Comparable<T>> {
private T valor;
private BST<T> izquierdo;
private BST<T> derecho;
public BST() {
this.valor = null;
this.izquierdo = null;
this.derecho = null;
}
public boolean esVacio() {
return valor == null;
}
public boolean esHoja() {
return valor != null && izquierdo == null && derecho == null;
}
public void insertar(T empleado) {
if (esVacio()) {
valor = empleado;
} else {
int comparacion = empleado.compareTo(valor);
if (comparacion < 0) {
if (izquierdo == null) {
izquierdo = new BST<>();
}
izquierdo.insertar(empleado);
} else if (comparacion > 0) {
if (derecho == null) {
derecho = new BST<>();
}
derecho.insertar(empleado);
} else {
// Duplicado: no hacemos nada o manejamos el caso según convenga
}
}
}
}
Con esta base, podemos seguir implementando otras operaciones esenciales para el árbol, como buscar un empleado por su identificador, recorrer el árbol en diferentes órdenes (preorden, inorden, posorden), y eliminar nodos. La clave está en que, gracias a la interfaz Comparable y a la programación genérica, nuestro árbol es flexible y puede manejar cualquier tipo de objeto que tenga un criterio de comparación definido.
Así, al organizar empleados en un BST, conseguimos una estructura eficiente para búsquedas rápidas, que es especialmente útil en aplicaciones como bases de datos, donde la velocidad de acceso a la información es crucial.