Reducir con forma de arbol

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.
Asi que esta vez cambiamos la forma.
Pon una raiz arriba
y dividela en dos ramas.
De cada rama, dos mas.
A esta forma que se divide la llamamos arbol.

Toca la raiz para desplegar ramas. Cada toque divide un nivel mas.

Cuanto mas se divide, mas rapido crecen los sitios.
Cada nivel duplica las ramas.
Pero ¿por que esta forma
es buena para buscar?
El secreto esta en hacia donde se divide.
Al elegir una rama desde la raiz
no vas a cualquier lado,
llevas una regla y eliges un lado.
Veamos esa regla a continuacion.

Cada paso reduce a la mitad

Al colocar valores en un arbol
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 facil.
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 eleccion,
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 eleccion,
los candidatos cayeron a la mitad.
Una rama descartada no se vuelve a mirar.
Gracias a la regla sabes
que la respuesta no esta dentro.
Asi que por muchos sitios que haya,
unas pocas elecciones lo reducen rapido.
Entonces, ¿elegimos un objetivo real
y lo seguimos desde la raiz?

Se encuentra en pocos pasos

Ahora elige un valor objetivo
y siguelo desde la raiz.
Compara el sitio raiz 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 cuantos pasos toma,
y el numero sorprendentemente pequeno te asombrara.

Fija un objetivo y baja desde la raiz sitio a sitio. Cuenta cuantos pasos toma.

Incluso un arbol de siete sitios
llego en tres pasos como mucho.
Si estuvieran en una fila
el ultimo valor necesitaria siete miradas.
Gracias a la forma de arbol
lo hallamos con muchas menos miradas.
Entonces, si hay muchos mas sitios,
¿el numero de pasos tambien se dispara?
Hagamoslo crecer nosotros a continuacion.

La profundidad es el numero de pasos

La profundidad de un arbol
es el numero de pasos de la raiz al fondo.
Eso es tambien el maximo de pasos
que puede tomar una busqueda.
Lo curioso: aunque dupliques los sitios,
la profundidad crece solo un paso.
Duplica otra vez, un paso mas.
Asi que aunque los datos se vuelvan enormes
el numero de pasos sube muy despacio.
A este ahondar lento decimos
que crece como un logaritmo.

Toca para duplicar el numero 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 crecio solo un paso.
Un millon de sitios
se alcanzan en unos veinte pasos.
Este es el verdadero poder de la forma de arbol.
Por mucho que crezcan los datos,
los pasos para hallar apenas aumentan.
Por eso, para datos grandes,
la forma de arbol se usa tanto.

Resumamos

Reunido en una linea, es esto.
Pon los datos con forma de rama, un arbol.
Con la regla menor izquierda, mayor derecha,
cada paso reduce a la mitad los candidatos.
Asi que hasta miles se hallan en pocos pasos.
El numero 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 que poner datos
con forma de arbol encuentra rapido.
Pero una cosa inquieta un poco.
Si el orden en que insertas valores es malo,
el arbol puede crecer largo hacia un lado,
un arbol torcido.
Entonces el encanto de reducir a la mitad se pierde.
¿Como mantener un arbol
parejo por ambos lados?
Veamos esa historia del equilibrio en la proxima leccion.