Arboles que se equilibran solos

Si se inclina a un lado, se vuelve lento

Antes aprendimos que un arbol encuentra cosas rapido
partiendo la busqueda por la mitad a lo largo de sus ramas.
Cada paso de arriba abajo
reduce a la mitad el rango por mirar.
Pero, que pasa si insertas valores
solo en orden, el mas pequeno primero?
Cada valor nuevo se pega a un lado,
asi que las ramas nunca se dividen
y se estiran en una sola linea larga.

Inserta valores uno por uno. Crece largo por un lado casi como una linea, y los pasos para encontrar se disparan.

Un arbol estirado en una linea
en realidad casi no se ramifica.
Bajar no parte el rango por la mitad;
solo le quita uno cada vez.
Entonces, para hallar un valor al otro extremo,
hay que contar uno por uno de principio a fin.
El arbol que hicimos para encontrar rapido
se ha vuelto, al contrario, lento.
Asi, no tiene sentido usar un arbol.

Mantener ambos lados con profundidad parecida

Aun con los mismisimos valores,
darle buena forma cambia la historia.
En vez de amontonar a un lado,
pon un valor del medio arriba,
los menores a la izquierda, los mayores a la derecha,
dividiendo las ramas hacia ambos lados.
Entonces cada paso desde arriba
de verdad parte el rango por la mitad.
A un arbol con ambos lados a profundidad parecida asi
se le llama arbol equilibrado.

Los mismos valores en ambos. Toca el arbol inclinado y el equilibrado para comparar la profundidad. Cual llega antes al fondo?

Con la misma cantidad,
el arbol equilibrado es mucho menos profundo.
Menos profundo significa menos pasos al fondo,
lo que significa que encontrar es rapido.
Pero aunque empiece bien equilibrado,
si sigues insertando y quitando valores
un lado puede ir poniendose mas pesado.
No podemos rearmarlo a mano cada vez,
asi que el arbol deberia arreglarse solo, no?

Reequilibrar con una rotacion

Cuando un lado se pone pesado,
el arbol mueve un poco los asientos de los nodos.
Sube un nodo del lado pesado
y baja un paso al que estaba arriba.
Entonces el peso amontonado en un lado
se reparte a ambos y vuelve a equilibrarse.
A este recolocar
se le llama una rotacion.
Mantiene intacta la regla de orden
y solo endereza la forma.

Este arbol pesa a la derecha. Toca rotar. El nodo del medio sube arriba y los dos lados se equilibran.

Con una sola rotacion
el arbol torcido se enderezo.
Solo unos pocos nodos cambiaron de asiento,
y ya ambos lados estan a profundidad parecida.
Lo que importa es que la regla de orden de los valores
no se altero en absoluto.
La izquierda sigue pequena, la derecha sigue grande.
Solo cambio la forma; la promesa se mantuvo,
asi que encontrar funciona igual de bien.

La profundidad esta garantizada, por mucho que haya

Mantener el equilibrio con una rotacion
en cada insercion y borrado tiene su recompensa.
Por mucho que se acumulen los datos,
la profundidad del arbol crece solo despacio.
Aun cuando la cantidad se duplica,
la profundidad crece apenas un paso mas.
A este crecimiento lento se le llama log.
Asi que haya cien valores o un millon,
siempre garantiza encontrar algo en unos pocos pasos.

Aumenta la cantidad de datos. La profundidad del arbol inclinado sube otro tanto, pero el equilibrado se ahonda despacio, paso a paso.

La profundidad del arbol inclinado se disparo
justo al ritmo de los datos crecientes.
Pero el arbol equilibrado,
aun cuando los datos se multiplicaron,
mantuvo su profundidad casi igual.
Esta misma diferencia
es lo que hace fiable a un arbol equilibrado.
Por muchos datos que lleguen,
puedes confiar en que encontrara cosas rapido.

Resumamos

Reunido en una linea, es esto.
Si un arbol crece solo por un lado
se vuelve casi una linea y se hace lento.
Un arbol equilibrado mantiene ambos lados a profundidad parecida.
Cuando un lado se pone pesado al insertar o quitar
recoloca las cosas con una rotacion.
Gracias a eso, por mucho dato que haya,
la profundidad crece despacio (log)
y siempre garantiza encontrar algo en unos pocos pasos.

Toca los puntos clave en orden para repasar. (inclinado = lento -> lados parejos -> recolocar con rotacion -> garantizado por log)

Ahora sabes como un arbol
mantiene su propio equilibrio.
Este era su secreto para no perder
la busqueda rapida aun mientras inserta y quita.
Solo tenemos que entregarle los valores,
y el arbol ordena su forma por si mismo.
Las rotaciones enredadas se las dejamos al arbol,
y nosotros solo disfrutamos la busqueda rapida.