cómo Qué es un árbol de datos

Los datos se dividen en ramas

Antes aprendimos a
poner datos en una sola fila.
Una fila se ve ordenada,
pero para hallar un valor del medio
a veces caminas desde un extremo.
Así que esta vez cambiamos la forma.
Pon una raíz arriba
y divídela en dos ramas.
De cada rama, dos más.
A esta forma que se divide la llamamos árbol.

Toca la raíz para desplegar ramas. Cada toque divide un nivel más.

Cuanto más se divide, más rápido crecen los sitios.
Cada nivel duplica las ramas.
Pero ¿por qué esta forma
es buena para buscar?
El secreto está en hacia dónde se divide.
Al elegir una rama desde la raíz
no vas a cualquier lado,
llevas una regla y eliges un lado.
Veamos esa regla a continuación.

Cada paso reduce a la mitad

Al colocar valores en un árbol
fijas una regla.
Los valores menores que un sitio van a la rama izquierda,
los mayores van a la rama derecha.
Entonces buscar se vuelve muy fácil.
Si tu objetivo 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.
Con cada elección,
desaparece la mitad de los candidatos restantes.

Compara el objetivo con el sitio actual: toca izquierda si es menor, derecha si es mayor. Cada toque reduce a la mitad los candidatos.

Con cada elección,
los candidatos cayeron a la mitad.
Una rama descartada no se vuelve a mirar.
Gracias a la regla sabes
que la respuesta no está dentro.
Así que por muchos sitios que haya,
unas pocas elecciones lo reducen rápido.
Entonces, ¿elegimos un objetivo real
y lo seguimos desde la raíz?

Se encuentra en pocos pasos

Ahora elige un valor objetivo
y síguelo desde la raíz.
Compara el sitio raíz con el objetivo
y por la regla baja a izquierda o derecha.
En esa rama compara otra vez y baja otra vez.
Hasta llegar al sitio objetivo
repites lo mismo.
Cuenta cuántos pasos toma,
y el número sorprendentemente pequeño te asombrará.

Fija un objetivo y baja desde la raíz sitio a sitio. Cuenta cuántos pasos toma.

Incluso un árbol de siete sitios
llegó en tres pasos como mucho.
Si estuvieran en una fila
el último valor necesitaría siete miradas.
Gracias a la forma de árbol
lo hallamos con muchas menos miradas.
Entonces, si hay muchos más sitios,
¿el número de pasos también se dispara?
Hagámoslo crecer nosotros a continuación.

La profundidad es el número de pasos

La profundidad de un árbol
es el número de pasos de la raíz al fondo.
Eso es también el máximo de pasos
que puede tomar una búsqueda.
Lo curioso: aunque dupliques los sitios,
la profundidad crece solo un paso.
Duplica otra vez, un paso más.
Así que aunque los datos se vuelvan enormes
el número de pasos sube muy despacio.
A este ahondar lento decimos
que crece como un logaritmo.

Toca para duplicar el número de sitios. Los sitios saltan, pero la profundidad (pasos) crece de a un paso.

Aunque los sitios pasen de mil a dos mil
la profundidad creció solo un paso.
Un millón de sitios
se alcanzan en unos veinte pasos.
Este es el verdadero poder de la forma de árbol.
Por mucho que crezcan los datos,
los pasos para hallar apenas aumentan.
Por eso, para datos grandes,
la forma de árbol se usa tanto.

Resumamos

Reunido en una línea, es esto.
Pon los datos con forma de rama, un árbol.
Con la regla menor izquierda, mayor derecha,
cada paso reduce a la mitad los candidatos.
Así que hasta miles se hallan en pocos pasos.
El número de pasos, la profundidad, es la velocidad.
Cuando los datos se duplican
la profundidad crece solo un paso.
Es igual que abrir un diccionario
por el medio y reducir a la mitad.

Toca los puntos clave en orden para repasar. (se divide en ramas -> reducir a la mitad -> hallar en pocos pasos -> profundidad es los pasos)

Ahora sabes por qué poner datos
con forma de árbol encuentra rápido.
Pero una cosa inquieta un poco.
Si el orden en que insertas valores es malo,
el árbol puede crecer largo hacia un lado,
un árbol torcido.
Entonces el encanto de reducir a la mitad se pierde.
¿Cómo mantener un árbol
parejo por ambos lados?
Veamos esa historia del equilibrio en la próxima lección.