Los árboles binarios de búsqueda son una estructura fundamental para organizar datos de forma ordenada y eficiente, facilitando operaciones como la búsqueda e inserción. Se trata de un tipo especial de árbol binario que cumple una propiedad clave: para cada nodo, todos los elementos del subárbol izquierdo son menores que el nodo, y todos los del subárbol derecho son mayores. Esta característica nos permite navegar por el árbol de manera rápida y ordenada.
Para entenderlo mejor, imaginemos un árbol con raíz 16. En su subárbol izquierdo encontraremos valores menores, como 8, y en el derecho valores mayores, como 24. A su vez, el subárbol izquierdo de 8 tendrá valores menores que 8, como 3, y mayores, como 13, y así sucesivamente. Esta estructura garantiza que, al buscar un elemento, podemos decidir en cada paso si debemos ir a la izquierda o a la derecha, reduciendo el espacio de búsqueda.
Es importante que los elementos que almacenamos sean comparables, es decir, que podamos establecer un orden entre ellos. Por ejemplo, números enteros, cadenas ordenadas lexicográficamente o cualquier objeto que tenga una clave ordenable, como un libro por su ISBN o una persona por su DNI. Esto es especialmente útil en bases de datos, donde se almacenan objetos completos pero se utilizan claves para identificarlos y ordenarlos.
Cuando trabajamos con árboles binarios de búsqueda, podemos aprovechar la recursividad para definir la estructura y las operaciones. Un árbol puede considerarse un nodo que a su vez tiene subárboles izquierdo y derecho, que pueden ser otros árboles o estar vacíos (null). Esta definición recursiva facilita la implementación de algoritmos para buscar o insertar elementos.
La búsqueda en un árbol binario de búsqueda se realiza comparando la clave que buscamos con la raíz del árbol. Si coinciden, hemos encontrado el elemento. Si la clave es menor, buscamos recursivamente en el subárbol izquierdo; si es mayor, en el derecho. Si llegamos a un árbol vacío, significa que el elemento no está presente. Este proceso se puede expresar en pseudocódigo así:
Elemento buscar(Árbol árbol, Clave x) {
si (árbol == null) {
return null;
}
si (x == árbol.raíz) {
return árbol.raíz;
}
si (x < árbol.raíz) {
return buscar(árbol.izquierdo, x);
} else {
return buscar(árbol.derecho, x);
}
}
Para saber si un elemento existe, basta con adaptar este algoritmo para devolver un valor booleano, retornando falso si el árbol está vacío y verdadero si encontramos la clave.
La inserción de elementos en el árbol sigue una lógica similar a la búsqueda, pero con la particularidad de que debemos mantener el orden para no romper la estructura. Si el árbol está vacío, insertamos el nuevo elemento como raíz. Si no, comparamos la clave con la raíz y decidimos si insertarla en el subárbol izquierdo o derecho. Además, debemos decidir si permitimos duplicados o no; en muchos casos, como con identificadores únicos, no se permiten.
Un ejemplo de función insertar podría ser:
Árbol insertar(Árbol árbol, Elemento e) {
si (árbol == null) {
return nuevoNodo(e);
}
si (e == árbol.raíz) {
// Aquí podríamos lanzar un error o ignorar la inserción si no permitimos duplicados
return árbol;
}
si (e < árbol.raíz) {
árbol.izquierdo = insertar(árbol.izquierdo, e);
} else {
árbol.derecho = insertar(árbol.derecho, e);
}
return árbol;
}
Un detalle importante al implementar la inserción es cómo modificar el árbol original. En lenguajes que manejan punteros, como C, podemos pasar un puntero al árbol para modificarlo directamente. En lenguajes funcionales o cuando usamos variables inmutables, la función insertar no modifica el árbol original, sino que devuelve uno nuevo con el elemento insertado.
Para ilustrar la inserción, imaginemos que empezamos con un árbol vacío y queremos insertar el 8. Como está vacío, el 8 se convierte en la raíz. Luego, si insertamos el 10, como es mayor que 8, lo colocamos en el subárbol derecho. Si insertamos el 4, que es menor que 8, va al subárbol izquierdo. Si después insertamos el 6, que es mayor que 4 pero menor que 8, lo colocamos en el subárbol derecho del nodo 4. Así, el árbol mantiene su orden y estructura.
Es fundamental tener cuidado al conectar los punteros o referencias en el árbol para evitar errores, especialmente en lenguajes que requieren manejo explícito de memoria. En Java, por ejemplo, se suele usar una clase con campos que pueden ser null y métodos que gestionan la inserción de forma segura.
Aunque hemos visto una forma común de implementar la inserción, existen múltiples variantes y estilos. La que hemos presentado es una de las más conocidas y también la que aparece en recursos como Wikipedia, pero no es la única.
La operación de eliminación en árboles binarios de búsqueda es más compleja y requiere un tratamiento especial, por lo que la dejaremos para un análisis posterior.