Lecciones Interactivas de Matemáticas y Ciencias (ﾉ◕ヮ◕)ﾉ*:･ﾟ✧

Visualizador de árboles BST / AVL

Inserta valores y observa cómo crece el árbol. Cambia al modo AVL para ver el reequilibrio automático.

Cargando simulación interactiva...

La entrada ordenada es la peor entrada 🖖

Un árbol binario de búsqueda saca su velocidad de su forma, y la forma viene por completo del orden de inserción. Dale a esta herramienta 10, 20, 30, 40, 50, 60, 70 en ese orden: cada clave es mayor que la anterior, así que cada una cuelga a la derecha de la previa y el árbol se convierte en una cadena recta de altura 7. Es una lista enlazada cargando con el coste de los punteros de árbol, y encontrar el 70 cuesta siete comparaciones en lugar de tres. Nada en los datos era patológico — simplemente ya venían ordenados, que es como suelen llegar los datos. Cambia esos mismos siete valores a modo AVL y las rotaciones devuelven la altura a 3. Ese es todo el argumento a favor de los árboles autoequilibrados.

Cada paso descarta la mitad 🖖

Un árbol binario de búsqueda funciona como buscar una palabra en el diccionario: en cada nodo comparas y descartas de inmediato toda la mitad que no puede contener tu valor. Por eso un árbol bien formado encuentra cualquier valor entre un millón de entradas en unas 20 comparaciones. Pero la forma depende por completo del orden de inserción: introduce los valores ya ordenados (10, 20, 30, …) y observa cómo el árbol se derrumba en una única línea inclinada, tan lenta como recorrer una lista uno por uno.

El número áureo se esconde en los árboles AVL 🖖

Cambia al modo AVL y pregunta: ¿cuánto puede crecer en altura un árbol equilibrado para un número dado de nodos? La respuesta esconde el número áureo. El árbol AVL válido más disperso de cada altura es un árbol de Fibonacci, formado por dos árboles de Fibonacci más pequeños, de modo que sus cantidades de nodos siguen la sucesión de Fibonacci. Por eso la cota de altura lleva la constante 1.44: es exactamente 1 / log₂(φ), con φ ≈ 1.618, el número áureo.

ÁRBOLES BST Y AVL — LOS MISMOS VALORES, CUATRO ÁRBOLES DISTINTOS

¿Qué árbol te dará tu orden de inserción?

La forma de un árbol binario de búsqueda no la deciden los valores que guarda, sino el orden en que llegaron — y esa forma es todo el precio: cada búsqueda, inserción y eliminación recorre el camino de la raíz a una hoja, así que lo que cuesta es la altura. Dos preguntas resuelven en qué caso estás: ¿llegaron los valores ya ordenados, y hay algo rotándolos de vuelta al equilibrio?

BST equilibrado — el orden de llegada se entrelazó h = 3 = ⌈log₂(n + 1)⌉
BST degenerado — entrada ordenada y nada que reequilibre h = n = 7 ⇒ O(n)
Reequilibrio AVL — la rotación es local y barata |hL − hR| > 1 → ↻, h = 3
AVL con entrada ordenada — el caso para el que existen las rotaciones ↻ × 4 ⇒ h = 3 < 7

01

BST equilibrado — el orden de llegada se entrelazó

Qué sabes: Modo BST puro, sin rotaciones. Los valores llegan empezando por el medio, así que cada clave nueva cae en un subárbol todavía bajo y ningún lado se adelanta al otro.

Qué cuesta: h = 3 = ⌈log₂(n + 1)⌉

Ejemplo resuelto: 50, 30, 70, 20, 40, 60, 80 → raíz 50, 7 nodos, altura 3 — exactamente el ideal ⌈log₂(7+1)⌉ = 3, de modo que la búsqueda más profunda cuesta 3 comparaciones

Abrir este caso: Equilibrado
BST equilibrado — el orden de llegada se entrelazó. Siete nodos en tres niveles: cada hoja a la misma distancia de la raíz, y no se puede hacer mejor. Modo BST puro, sin rotaciones. Los valores llegan empezando por el medio, así que cada clave nueva cae en un subárbol todavía bajo y ningún lado se adelanta al otro.
Siete nodos en tres niveles: cada hoja a la misma distancia de la raíz, y no se puede hacer mejor.

02

BST degenerado — entrada ordenada y nada que reequilibre

Qué sabes: Modo BST puro otra vez, pero los valores llegan en orden ascendente. Cada uno es mayor que todo lo ya guardado, así que va a la derecha, todas y cada una de las veces.

Qué cuesta: h = n = 7 ⇒ O(n)

Ejemplo resuelto: 10, 20, 30, 40, 50, 60, 70 → raíz 10, 7 nodos, altura 7 en lugar de 3; encontrar el 70 cuesta 7 comparaciones, y la herramienta etiqueta el resultado como lista enlazada

Abrir este caso: Degenerado
BST degenerado — entrada ordenada y nada que reequilibre. Cada nodo tiene un solo hijo: la búsqueda recorre los siete niveles, no más rápido que barrer un arreglo. Modo BST puro otra vez, pero los valores llegan en orden ascendente. Cada uno es mayor que todo lo ya guardado, así que va a la derecha, todas y cada una de las veces.
Cada nodo tiene un solo hijo: la búsqueda recorre los siete niveles, no más rápido que barrer un arreglo.

03

Reequilibrio AVL — la rotación es local y barata

Qué sabes: Modo AVL. Tras cada inserción el árbol vuelve subiendo hacia la raíz, y el primer nodo cuyas dos alturas de subárbol difieren en más de 1 se rota. Las insignias junto a cada nodo muestran la altura izquierda menos la derecha.

Qué cuesta: |hL − hR| > 1 → ↻, h = 3

Ejemplo resuelto: 30, 20, 10, 25, 35, 40 en modo AVL → insertar 10 inclina el nodo 30 a +2 y una rotación a la derecha eleva el 20 a su lugar; más tarde el 40 inclina un nodo a −2 y una rotación a la izquierda lo arregla. 2 rotaciones, 6 nodos, altura 3.

Abrir este caso: Reequilibrio AVL
Reequilibrio AVL — la rotación es local y barata. Los nodos con anillo fueron elevados por una rotación; cada insignia está de nuevo dentro de ±1. Modo AVL. Tras cada inserción el árbol vuelve subiendo hacia la raíz, y el primer nodo cuyas dos alturas de subárbol difieren en más de 1 se rota. Las insignias junto a cada nodo muestran la altura izquierda menos la derecha.
Los nodos con anillo fueron elevados por una rotación; cada insignia está de nuevo dentro de ±1.

04

AVL con entrada ordenada — el caso para el que existen las rotaciones

Qué sabes: Modo AVL, alimentado exactamente con los valores que produjeron la cadena dos casos más arriba. Cada inserción cae en el extremo derecho y empuja el balance de algún antepasado a −2, así que casi cada inserción dispara un arreglo.

Qué cuesta: ↻ × 4 ⇒ h = 3 < 7

Ejemplo resuelto: 10, 20, 30, 40, 50, 60, 70 en modo AVL → 4 rotaciones a la izquierda, y la raíz termina siendo 40 y no 10. Altura 3, no 7: la misma entrada, los mismos siete nodos, menos de la mitad de la profundidad.

Abrir este caso: Ordenado en AVL
AVL con entrada ordenada — el caso para el que existen las rotaciones. Los mismos valores ordenados del caso 2, rotados de vuelta a tres niveles mientras llegan. Modo AVL, alimentado exactamente con los valores que produjeron la cadena dos casos más arriba. Cada inserción cae en el extremo derecho y empuja el balance de algún antepasado a −2, así que casi cada inserción dispara un arreglo.
Los mismos valores ordenados del caso 2, rotados de vuelta a tres niveles mientras llegan.
Referencias (1)
  • Insight block 3 — the Fibonacci tree that sets the AVL height bound: D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd edition, §6.2.3. Addison-Wesley, 1998. ISBN 978-0-201-89685-5 — the sparsest legal AVL tree of each height, and the logφ bound that follows.

Problema resuelto al detalle

  1. Un árbol de altura siete con siete nodos 5 pasos

    Siete nodos y un árbol de altura siete. Un árbol equilibrado tendría altura 3. Averigüe qué hizo la entrada y cuál es su coste a escala.

    1. Las claves por defecto son 10, 20, 30, … —ya ordenadas—. Al seguir la regla de inserción, cada nueva clave es mayor que todo lo que hay en el árbol, por lo que va a la derecha en todos los casos.

    2. El resultado no presenta ramificación alguna. Cada nodo tiene un solo hijo, de modo que la estructura es una lista enlazada dibujada como un árbol, y la altura coincide con la cantidad de nodos.

    3. La mejor altura posible para siete nodos es 3, ya que un árbol de altura h alberga a lo sumo 2ʰ − 1 nodos, y 2³ − 1 = 7 exactamente. Esta entrada alcanza el peor caso aun estando disponible la opción equilibrada.

    4. La búsqueda recorre el árbol desde la raíz, por lo que el coste equivale a la altura: 7 comparaciones en este caso frente a 3.

    5. La proporción es la clave, y crece. Con un millón de nodos, la altura equilibrada es 20 y la altura con la entrada ordenada es de un millón.

    Respuesta

    La herramienta muestra una altura de 7 para 7 nodos frente a un ideal de 3. La lección es que O(log n) nunca fue una propiedad del árbol binario de búsqueda: es una propiedad del orden de inserción, y el orden más natural que un programador pueda proporcionarle —los datos ordenados— es precisamente el que lo destruye. Esa es la razón de ser de los árboles AVL y rojo-negro: cuestan una o dos rotaciones por inserción para ofrecer dicha garantía de forma incondicional. Cambie el modo a AVL y observe cómo las mismas siete claves se acomodan a una altura de 3.

· Actualizado

Contrastado con fuentes publicadas. Se agradecen correcciones. Política editorial · Correcciones

Todas las lecciones de Informática →

Problemas de ejemplo