Qué es un árbol equilibrado
En la lección anterior dijimos que un árbol encuentra las cosas rápido reduciendo la búsqueda a la mitad a lo largo de sus ramas. Pero ¿qué pasa si el árbol crece largo solo por un lado? Si las ramas dejan de dividirse y se estira en una sola línea, no es mejor que contar uno por uno desde el principio, y se vuelve lento. Por eso un árbol inteligente se reacomoda cada vez que entran o salen valores, para que sus dos lados tengan más o menos la misma profundidad.
Inclinarse hacia un lado lo vuelve lento
En un árbol, cada paso hacia abajo reduce a la mitad lo que queda por revisar. Pero ¿qué pasa si metes los valores solo en orden, del más pequeño al más grande?
Cada valor nuevo es mayor que todos los que ya se metieron, así que siempre se engancha en el extremo derecho. Las ramas dejan de dividirse y el árbol se estira en una línea larga. Es árbol solo de nombre: por su forma, es igual que la fila que vimos antes.
Mete los valores en orden. El árbol se alarga por un solo lado hasta ser casi una línea, y los pasos para encontrar un valor se disparan.
Un árbol estirado en una línea prácticamente no tiene ramas. Al bajar desde arriba, lo que queda por revisar no se reduce a la mitad, sino de uno en uno.
Así que, para encontrar el valor del final, hay que contar uno por uno de principio a fin. Un árbol hecho para buscar rápido ha terminado siendo lento. Así no tiene sentido usar un árbol.
Mantener ambos lados con una profundidad parecida
Incluso con los mismos valores, una forma mejor lo cambia todo. En lugar de amontonarlo todo en un lado, se pone el valor del medio arriba y se ramifican los menores a la izquierda y los mayores a la derecha.
Así, cada paso hacia abajo reduce de verdad a la mitad lo que queda por revisar. Un árbol que mantiene así sus dos lados con una profundidad parecida se llama árbol equilibrado.
Estos dos árboles se hicieron con los mismos valores. Toca el árbol inclinado y el equilibrado para comparar su profundidad. ¿Cuál llega antes al fondo?
La cantidad es la misma, pero el árbol equilibrado es mucho menos profundo. Menos profundidad significa menos pasos hasta el fondo, es decir, una búsqueda más rápida.
Pero incluso un árbol que empieza bien equilibrado puede irse cargando poco a poco de un lado a medida que entran y salen valores. Nadie puede rehacerlo a mano cada vez, así que el árbol tiene que corregirse solo.
Reequilibrar con rotaciones
Cuando un lado se carga, el árbol cambia un poco de lugar algunos nodos: sube un nodo del lado pesado y baja un nivel el nodo que estaba encima.
Entonces el peso que se había acumulado en un lado se reparte entre los dos, y el árbol vuelve a estar equilibrado. Reacomodarse así se llama rotación. Solo corrige la forma, sin dejar de cumplir la regla de orden: los valores menores a la izquierda y los mayores a la derecha.
Este árbol pesa más a la derecha. Toca rotar. El nodo del medio sube arriba y los dos lados se equilibran.
Una sola rotación enderezó el árbol torcido. Solo se movieron unos pocos nodos, y aun así los dos lados vuelven a tener una profundidad parecida.
Lo importante es que la regla de orden no se alteró en absoluto: la izquierda sigue siendo menor y la derecha, mayor. Solo cambió la forma y la promesa se mantuvo, así que la búsqueda funciona igual de bien. Hay varios tipos de árboles que se equilibran así, cada uno con reglas un poco distintas para juzgar el equilibrio.
Profundidad garantizada, por muchos datos que haya
Mantener el equilibrio con rotaciones en cada inserción y eliminación tiene una gran ventaja: por mucho que crezcan los datos, la profundidad del árbol crece muy despacio.
Aunque la cantidad se duplique, la profundidad solo aumenta un nivel. Como vimos en la lección anterior, a este crecimiento lento se le llama logarítmico. Por eso, haya cien valores o un millón, siempre puedes encontrar uno en pocos pasos.
Aumenta la cantidad de datos. La profundidad del árbol inclinado crece tanto como los datos, pero el árbol equilibrado se hace más profundo despacio, de a un nivel.
A medida que crecían los datos, la profundidad del árbol inclinado se disparaba con ellos. En cambio, la del árbol equilibrado casi no cambiaba aunque los datos se multiplicaran varias veces.
Justamente esa diferencia hace que los árboles equilibrados sean fiables: por muchos datos que lleguen, puedes confiar en que la búsqueda seguirá siendo rápida.
En resumen
En pocas palabras: un árbol que crece por un solo lado se vuelve casi una línea y se hace lento. Un árbol equilibrado mantiene sus dos lados con una profundidad parecida.
Cuando un lado se carga al insertar o eliminar, se reacomoda con rotaciones. Gracias a eso, por muchos datos que haya, la profundidad crece despacio (log), así que siempre puedes encontrar un valor en pocos pasos.
Toca en orden los puntos clave para repasar. (inclinado es lento → ambos lados parejos → reacomodar con rotación → garantizado por log)
Ahora ya sabes cómo un árbol cuida su propio equilibrio. Ese es el secreto para seguir buscando rápido incluso mientras entran y salen valores. Nosotros solo entregamos los valores, y el árbol se encarga de las rotaciones.
Los índices de las bases de datos también se construyen con árboles equilibrados como estos, pero usan árboles anchos y poco profundos, en los que cada nodo guarda varios valores y tiene muchísimas ramas. La próxima lección mira cómo se usan esos índices en una base de datos.