Árboles binarios, un ejemplo práctico

Muchas veces nos es difícil entender para qué nos enseñan algo sin explicarnos la aplicación. El tiempo que llevo dando clases particulares he podido ver apuntes con mucho contenido y con pocos ejemplos prácticos, esto desmotiva mucho porque el estudiante piensa ¿Para qué me enseñan esto?.

Esto pasa generalmente con el tema de árboles, te explican los tipos de árboles existen (binarios, múltiples, balanceados, etc) y cómo recorrerlos (pre-orden, post-orden, etc), sin embargo son muy pocos los ejemplos prácticos que he podido encontrar.

El objetivo de este post es mostrar un ejemplo práctico en que se podría hacer uso de los árboles, aunque también se puede hacer uso de otras soluciones.

Tenemos un fichero de texto que contiene en cada linea la edad de personas encuestadas para un estudio de mercado, lo que nos interesa es leer el fichero y mostrar en pantalla la cantidad de repeticiones por cada edad, es decir la edad que más se repiten en la muestra.

Partimos de la premisa que la información no está ordenada y es una muestra de 1000 personas.

Utilizaremos para cada número una estructura (o clase) que almacene el valor de la edad y el valor de la repetición: public struct elemMuestra { public int edad; public int frecuencia; } El algoritmo que podríamos plantear es el siguiente: 1. Leer número del fichero 2. Buscar el número en la estructura ordenada 2.1. Si el número existe en la estructura, incrementar el número de repeticiones 2.1. Si el número NO existe en la estructura, inserto el número en la estructura 3. Cuando termino de leer todos los números del fichero, imprimo cada número con su frecuencia de repetición guardada en la estructura.

En el punto 2 vemos que utilizamos una estructura ordenada, aquí podríamos utilizar un vector, una lista de punteros, un árbol binario,etc. lo importante es que la estructura que definamos nos sea útil tanto para buscar si el número ya existe en la estructura, como para insertar un nuevo número en la estructura.

Si utilizamos un vector, podríamos realizar una búsqueda binaria, debido a que los índices del vector ayudan a este tipo de búsqueda, sin embargo si utilizamos una lista de punteros o un árbol binario tendríamos que usar una búsqueda secuencial, pero sin duda el recorrido en un árbol podría ser mucho más eficiente que el recorrido en una lista de punteros, debido a que la forma del árbol no requiere recorrer a todos sus elementos sino que al tener un orden binario es como si realmente se hiciera una búsqueda binaria, a la búsqueda en un árbol binario se le llama búsqueda Silaina.

El otro punto a evaluar es el tema de la inserción, cuando ya sabemos que el número que hemos leído de fichero aún no existe en la estructura que hemos escogido, utilizar un vector podría ser lo menos eficiente, puesto que si tenemos ordenados 900 números en 20 edades distintas, y llega una nueva edad que es la menor de todas, debemos desplazar todas las edades a una casilla posterior para insertar la nueva edad de forma ordenada, ese desplazamiento puede ser muy costoso. En una lista de punteros la inserción es relativamente sencilla y en un árbol también.

A nivel de programación los árboles son más fáciles de trabajar con funciones recursivas, por tanto si tenéis poca experiencia en funciones recursivas y la cantidad de elementos de la muestra no es tan grande, puede ser más sencillo de programar con vectores + búsqueda binaria o secuencial, sin embargo si veis que la muestra es muy grande y luego vais a realizar muchas búsquedas sobre la estructura cargada y ordenada es mejor trabajarla con árboles binarios + búsqueda sobre árboles binarios.

Ahora bien, para que la búsqueda en un árbol binario sea aun más eficiente deberíamos lograr que el árbol tenga el menor numero de niveles, para esto se realiza lo que se llama el balanceo de árboles: