cómo Qué es un árbol equilibrado

Si se inclina a un lado, se vuelve lento

Antes aprendimos que un árbol encuentra cosas rápido
partiendo la búsqueda por la mitad a lo largo de sus ramas.
Cada paso de arriba abajo
reduce a la mitad el rango por mirar.
Pero, qué pasa si insertas valores
solo en orden, el más pequeño primero?
Cada valor nuevo se pega a un lado,
así que las ramas nunca se dividen
y se estiran en una sola línea larga.

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

Un árbol estirado en una línea
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 árbol que hicimos para encontrar rápido
se ha vuelto, al contrario, lento.
Así, no tiene sentido usar un árbol.

Mantener ambos lados con profundidad parecida

Aun con los mismísimos 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 árbol con ambos lados a profundidad parecida así
se le llama árbol equilibrado.

Los mismos valores en ambos. Toca el árbol inclinado y el equilibrado para comparar la profundidad. Cuál llega antes al fondo?

Con la misma cantidad,
el árbol equilibrado es mucho menos profundo.
Menos profundo significa menos pasos al fondo,
lo que significa que encontrar es rápido.
Pero aunque empiece bien equilibrado,
si sigues insertando y quitando valores
un lado puede ir poniéndose más pesado.
No podemos rearmarlo a mano cada vez,
así que el árbol debería arreglarse solo, no?

Reequilibrar con una rotación

Cuando un lado se pone pesado,
el árbol 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 rotación.
Mantiene intacta la regla de orden
y solo endereza la forma.

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

Con una sola rotación
el árbol torcido se enderezó.
Solo unos pocos nodos cambiaron de asiento,
y ya ambos lados están a profundidad parecida.
Lo que importa es que la regla de orden de los valores
no se alteró en absoluto.
La izquierda sigue pequeña, la derecha sigue grande.
Solo cambió la forma; la promesa se mantuvo,
así que encontrar funciona igual de bien.

La profundidad está garantizada, por mucho que haya

Mantener el equilibrio con una rotación
en cada inserción y borrado tiene su recompensa.
Por mucho que se acumulen los datos,
la profundidad del árbol crece solo despacio.
Aun cuando la cantidad se duplica,
la profundidad crece apenas un paso más.
A este crecimiento lento se le llama log.
Así que haya cien valores o un millón,
siempre garantiza encontrar algo en unos pocos pasos.

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

La profundidad del árbol inclinado se disparó
justo al ritmo de los datos crecientes.
Pero el árbol equilibrado,
aun cuando los datos se multiplicaron,
mantuvo su profundidad casi igual.
Esta misma diferencia
es lo que hace fiable a un árbol equilibrado.
Por muchos datos que lleguen,
puedes confiar en que encontrará cosas rápido.

Resumamos

Reunido en una línea, es esto.
Si un árbol crece solo por un lado
se vuelve casi una línea y se hace lento.
Un árbol equilibrado mantiene ambos lados a profundidad parecida.
Cuando un lado se pone pesado al insertar o quitar
recoloca las cosas con una rotación.
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 rotación -> garantizado por log)

Ahora sabes cómo un árbol
mantiene su propio equilibrio.
Este era su secreto para no perder
la búsqueda rápida aun mientras inserta y quita.
Solo tenemos que entregarle los valores,
y el árbol ordena su forma por sí mismo.
Las rotaciones enredadas se las dejamos al árbol,
y nosotros solo disfrutamos la búsqueda rápida.