Qué es un árbol de datos
Cuando buscas una palabra en un diccionario grueso, no pasas las páginas una por una desde el principio. Lo abres por la mitad, decides si tu palabra está antes o después, y luego abres por la mitad de esa parte. Si colocas los datos en forma de ramas, puedes hacer lo mismo, porque cada paso hacia abajo reduce a la mitad los candidatos que hay que revisar.
Los datos se dividen en ramas
Antes vimos cómo poner los datos en una sola fila. Una fila se ve ordenada, pero para encontrar el valor que quieres a veces hay que recorrerla desde un extremo.
Así que esta vez cambiemos la forma. Pon una raíz arriba y haz que salgan dos ramas de ella, y luego dos más de cada una. Una forma que se divide así se llama árbol, y cada lugar que guarda un valor se llama nodo; en esta lección lo llamamos sitio.
Toca la raíz para desplegar las ramas. Cada toque las divide un nivel más.
Cuanto más se divide, más rápido se multiplican los sitios: cada nivel hacia abajo duplica su número.
Pero ¿por qué esta forma es buena para buscar? El secreto está en hacia dónde se ramifica. Al elegir una rama desde la raíz no vas a cualquier lado: sigues una regla y eliges solo un lado. Veamos esa regla.
Reducir a la mitad en cada paso
Al colocar valores en el árbol, se fija una regla: los valores menores que un sitio van a su rama izquierda, y los mayores, a su rama derecha. Un árbol que cumple esta regla se llama árbol binario de búsqueda.
Así buscar resulta muy fácil. Si el valor que buscas es menor que el sitio actual, descartas todo el lado derecho y miras solo a la izquierda. Si es mayor, descartas todo el lado izquierdo. Cada elección elimina la mitad de los candidatos que quedan.
Compara el objetivo con el sitio actual y toca izquierda si es menor o derecha si es mayor. Cada toque reduce a la mitad los candidatos que quedan.
Cada elección redujo los candidatos a la mitad. Las ramas descartadas ya no hay que revisarlas, porque gracias a la regla sabes que la respuesta no está en ellas.
Por eso, por muchos sitios que haya, unas pocas elecciones bastan para acotar enseguida. Ahora elijamos un objetivo real y sigámoslo desde la raíz.
Se encuentra en pocos pasos
Ahora elige un valor objetivo y síguelo desde la raíz. Compara la raíz con el objetivo y baja a la izquierda o a la derecha según la regla. En esa rama, vuelve a comparar y vuelve a bajar.
Repite lo mismo hasta llegar al objetivo. Si cuentas cuántos pasos hacen falta, te sorprenderá lo pocos que son.
Elige un objetivo y síguelo hacia abajo desde la raíz, sitio por sitio. Se cuentan los pasos que hacen falta.
Incluso en un árbol de siete sitios, bastaron como mucho tres pasos. Puesto en una sola fila, el valor del final habría necesitado siete revisiones.
Gracias a la forma de árbol, lo encontraste mirando muchas menos veces. Entonces, cuando hay más sitios, ¿el número de pasos crece en la misma medida? Hagamos crecer el árbol y veamos.
La profundidad es el número de pasos
La profundidad de un árbol es el número de pasos desde la raíz hasta abajo del todo. Ese es también el mayor número de pasos que puede llevar una búsqueda.
Lo interesante es que duplicar los sitios añade solo un paso de profundidad. Si se duplican otra vez, es un paso más. Por eso, aunque los datos se vuelvan enormes, el número de pasos crece muy despacio. Crecer un paso cada vez que el tamaño se duplica se llama crecimiento logarítmico.
Toca para duplicar el número de sitios. Los sitios se disparan, pero la profundidad (el número de pasos) crece despacio, de a un paso.
Aunque los sitios pasaron de mil a dos mil, la profundidad creció solo un paso. Incluso con un millón de sitios, llegas en menos de veinte pasos.
Ese es el verdadero poder de la forma de árbol. Por mucho que crezcan los datos, los pasos para encontrar algo casi no aumentan. Por eso los árboles se usan tanto con datos grandes.
En resumen
En pocas palabras: los datos se colocan en forma de ramas, en un árbol. Gracias a la regla de menor a la izquierda y mayor a la derecha, cada paso reduce los candidatos a la mitad.
Así, incluso entre miles, encuentras un valor en pocos pasos. El número de pasos, es decir, la profundidad, marca la velocidad. Cuando los datos se duplican, la profundidad crece solo un paso. Es igual que abrir un diccionario por la mitad e ir reduciendo la búsqueda a la mitad.
Toca en orden los puntos clave para repasar. (los datos se dividen en ramas → reducir a la mitad → se halla en pocos pasos → profundidad = pasos)
Ahora ya sabes por qué colocar los datos en un árbol hace que buscar sea rápido. Pero hay un detalle. Si los valores se meten en mal orden, por ejemplo del más pequeño al más grande, el árbol queda torcido y se estira solo hacia un lado.
Entonces se pierde la ventaja de reducir a la mitad y no es mejor que recorrer una fila. La próxima lección trata de cómo un árbol equilibra sus dos lados por sí solo.