Árboles AVL

La semana pasada terminamos con un problema. Un árbol binario de búsqueda cuesta lo que mide su altura, y su altura la decide el orden en que llegan las claves. Con claves al azar la altura se quedó en menos de 3 veces log₂ n. Con claves ordenadas fue n − 1: una lista enlazada con pasos de más. Nuestro palabras.txt viene ordenado, así que insertarlo tal como viene tardaría, según estimamos, cerca de una hora. Mientras tanto, std::map recibió el mismo archivo, en el mismo orden, y tardó menos de un segundo. No tuvo suerte. Se reparó a sí mismo.

Hoy aprendemos a hacer eso. La idea es de Adelson-Velski y Landis, de 1962, y por sus iniciales estos árboles se llaman AVL: después de cada operación se revisa el camino por el que se pasó, y donde la forma se haya desequilibrado demasiado, se arregla con una operación local y barata que se llama rotación. El resultado es un árbol cuya altura es O(log n) para cualquier orden de las claves, sin suerte de por medio.

En el laboratorio agregarán esto al mapa de la semana pasada. Sus rotaciones no se quedan aquí: la semana 12 las usa sin cambios para los árboles rojinegros.

Ruta de lectura.

Antes de clase (15 a 20 minutos, obligatorio): La idea: reparar un poco en cada operación, La condición AVL y Rotación.

En clase: Por qué la altura es O(log n), Los cuatro casos, Insertar, Borrar y La invariante en las pruebas.

Después de clase: repasen con el Resumen y los Ejercicios, y lean Cuánto se gana y El código de la semana. Opcional: Open Data Structures, sec. 9.4 (Discussion and Exercises), que menciona los árboles AVL y los propone como ejercicio. Sobre AVL, estos apuntes son el texto principal.

Código. Los programas de este capítulo están en code/week-11. Dentro del entorno del curso, entren a esa carpeta y corran make para compilar los ejemplos y make test para comprobarlos. Los comandos de este capítulo se corren desde ahí. Los programas de errors/ tienen errores a propósito y se compilan a mano, como se muestra en cada caso.

La idea: reparar un poco en cada operación

¿Cómo evitar una altura de n? Lo primero que se le ocurre a cualquiera es exigir el mejor árbol posible: altura ⌊log₂ n⌋ después de cada operación. No funciona, porque cuesta demasiado. Tomen un árbol perfecto con n = 2^k − 1 claves: es el único de altura mínima con esas claves. Inserten una clave menor que todas, y luego borren la mayor. Vuelven a tener 2^k − 1 claves, y de nuevo la única forma permitida es el árbol perfecto. Pero cada posición del recorrido en orden tiene ahora la clave de su vecina: todos los nodos cambiaron de clave, o de lugar. Dos operaciones, Θ(n) trabajo, y se puede repetir para siempre.

La salida es pedir menos. No necesitamos la altura mínima: nos basta con una constante por log₂ n. Queremos una condición que cumpla dos cosas:

Sea lo bastante fuerte para que la altura quede en O(log n).
Sea lo bastante débil para que se pueda restaurar tocando pocos nodos, y solo en el camino que recorrió la operación.

Esa es la condición AVL. Es local, porque se revisa en cada nodo mirando a sus hijos, y por eso se puede reparar localmente. Lo sorprendente es que una condición local alcanza para limitar la altura de todo el árbol.

La condición AVL

Definición. El balance de un nodo es la altura de su subárbol izquierdo menos la de su subárbol derecho. Un árbol AVL es un árbol binario de búsqueda en el que cada nodo tiene balance −1, 0 o 1. Es decir: en cada nodo, las alturas de sus dos subárboles difieren en 1 como máximo.

Usamos el convenio de la semana pasada: la altura cuenta aristas, una hoja tiene altura 0, y un subárbol vacío tiene altura −1. Sin ese −1 las cuentas no salen: una hoja tiene balance (−1) − (−1) = 0, y un nodo con un solo hijo, que es una hoja, tiene balance 0 − (−1) = 1, o −1 si el hijo está a la derecha.

Veamos tres árboles, con el balance de cada nodo a su lado. Escribimos también la forma en una línea, como la semana pasada: clave(izquierdo,derecho), con _ si falta un hijo.

Tres árboles con el balance de cada nodo. El primero tiene raíz 5, con hijos 3 y 8, y el 3 tiene hijos 1 y 4. Es AVL: la raíz tiene balance 1, y los demás, 0. El segundo es la cadena 5, 3, 1 hacia la izquierda. No es AVL: la raíz tiene balance 2, el 3 tiene 1 y el 1 tiene 0. El tercero tiene raíz 5, la cadena 3, 1, 0 a la izquierda y la cadena 7, 8, 9 a la derecha. No es AVL: la raíz tiene balance 0, pero el 3 tiene 2 y el 7 tiene −2, y están marcados. — La condición se pide en cada nodo. El tercer árbol tiene una raíz perfecta, y aun así no es AVL.

El de la derecha es la trampa. Su raíz tiene balance 0, con dos subárboles de la misma altura, y aun así no es AVL: el 3 tiene balance 2 y el 7 tiene balance −2. Si se exigiera la condición solo en la raíz, se podrían colgar dos cadenas largas de ella: cumpliría la condición, y su altura seguiría siendo unos n/2.

Error común. Pensar que AVL significa “los dos lados de la raíz tienen alturas parecidas”. La condición es sobre cada nodo. Por eso check_invariants tiene que revisar todos, igual que el orden de la semana pasada.

También es falso lo contrario de lo que sugiere la intuición: un AVL no tiene todas sus hojas en dos niveles vecinos. Más adelante verán uno de altura 4 con una hoja a profundidad 2 y otra a profundidad 4.

Guardar la altura en cada nodo

Para saber el balance de un nodo hay que conocer la altura de sus dos subárboles. Calcularla bajando costaría Θ(tamaño del subárbol) y arruinaría todo. Así que cada nodo la guarda, en un campo más:

struct Node {
    K key;
    Node* left = nullptr;
    Node* right = nullptr;
    int height = 0;
};

Un nodo nuevo es una hoja, y por eso height empieza en 0. Tres funciones cortas hacen todo el trabajo:

static int height_of(const Node* node) { return node != nullptr ? node->height : -1; }

static void update_height(Node* node) {
    node->height = 1 + std::max(height_of(node->left), height_of(node->right));
}

// Positivo: pesa más la izquierda. Negativo: pesa más la derecha.
static int balance_of(const Node* node) { return height_of(node->left) - height_of(node->right); }

update_height no baja por el árbol: confía en la altura que ya guardan los hijos. Cuesta O(1), y por eso mismo el orden importa: hay que actualizar primero a los hijos y después al padre. Volveremos a esto, porque es el error de la semana.

La altura guardada pasa a ser parte de las invariantes de la clase. Son estas, en el comentario de AvlSet y en su check_invariants:

En cada nodo, todas las claves del subárbol izquierdo son menores que la suya, y todas las del derecho son mayores.
En cada nodo, height es la altura de su subárbol. Un nodo nulo tiene altura −1.
En cada nodo, las alturas de sus dos subárboles difieren en 1 como máximo.
El árbol tiene exactamente size_ nodos, y root_ es nulo si y solo si size_ == 0.

Por qué la altura es O(log n)

Esta es la pregunta central: si cada nodo cumple la condición, ¿qué tan alto puede ser el árbol con n nodos? Conviene darle la vuelta: para una altura h, ¿cuál es la menor cantidad de nodos que puede tener un AVL? Llamemos N(h) a esa cantidad. Si N(h) crece rápido con h, un árbol alto necesita muchos nodos, y entonces con n nodos no se puede ser alto.

Los casos pequeños se ven a mano. Con altura 0 hay un solo nodo: N(0) = 1. Con altura 1 hacen falta la raíz y un hijo: N(1) = 2.

Para h ≥ 2: un AVL de altura h con la menor cantidad de nodos tiene una raíz y dos subárboles. Uno de ellos debe tener altura h − 1, porque si no la raíz no tendría altura h. El otro puede tener altura h − 1 o h − 2, porque la condición no permite menos; para gastar pocos nodos, tendrá h − 2. Y cada uno de los dos es también un AVL, que queremos con la menor cantidad de nodos posible para su altura. Por lo tanto:

N(h) = N(h − 1) + N(h − 2) + 1

Con eso se llena la tabla: N(2) = 2 + 1 + 1 = 4, N(3) = 4 + 2 + 1 = 7, y N(4) = 7 + 4 + 1 = 12. Un AVL de altura 4 tiene como mínimo 12 nodos. Estos son los árboles, que se llaman árboles de Fibonacci. Cada uno lleva a su izquierda el anterior y a su derecha el de antes del anterior:

Los árboles de Fibonacci de altura 0 a 4, con 1, 2, 4, 7 y 12 nodos. La raíz de cada uno tiene a la izquierda el árbol de altura h − 1, en azul, y a la derecha el de altura h − 2, en dorado. En el de altura 4 están señaladas una hoja a profundidad 4, la de más a la izquierda, y otra a profundidad 2, la de más a la derecha. Abajo, la recurrencia N(h) = N(h − 1) + N(h − 2) + 1, con N(4) = 7 + 4 + 1 = 12. — Cada árbol de Fibonacci se arma con los dos anteriores y una raíz. Esa es la recurrencia, dibujada.

Fíjense en el de altura 4. Tiene una hoja a profundidad 2, a la derecha, y otra a profundidad 4, a la izquierda. La condición AVL permite esa diferencia, y por eso la altura no es log₂ n, sino algo más.

Una cota sencilla

Sin ninguna fórmula ya podemos concluir algo. N crece con h, así que N(h − 1) > N(h − 2). Entonces:

N(h) = N(h − 1) + N(h − 2) + 1 > 2 · N(h − 2)

Cada vez que la altura sube en 2, la cantidad de nodos más que se duplica. Sigan esa desigualdad hasta abajo, de dos en dos: N(h) > 2 N(h − 2) > 4 N(h − 4) > 8 N(h − 6) > … En h/2 pasos se llega a N(0) = 1 si h es par, y en (h − 1)/2 pasos a N(1) = 2 si h es impar. En los dos casos, N(h) ≥ 2^(h/2).

Un AVL con n nodos y altura h cumple n ≥ N(h) ≥ 2^(h/2). Tomando logaritmos:

h ≤ 2 log₂ n

Eso ya resuelve el problema: la altura es O(log n). Con un millón de claves, la altura de un AVL es como máximo 39, y no 999 999. No hizo falta nada más que la recurrencia.

La cota exacta

La constante 2 se puede mejorar, porque la recurrencia dice más de lo que usamos. Sumen 1 a los dos lados:

N(h) + 1 = (N(h − 1) + 1) + (N(h − 2) + 1)

Si llamamos M(h) = N(h) + 1, queda M(h) = M(h − 1) + M(h − 2): cada término es la suma de los dos anteriores, con M(0) = 2 y M(1) = 3. Es la sucesión de Fibonacci, F(1) = F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5, a partir de su tercer término. Por lo tanto:

N(h) = F(h + 3) − 1

De Fibonacci se conoce la fórmula de Binet: F(k) es el entero más cercano a φ^k / √5, donde φ = (1 + √5)/2 ≈ 1.618 es la razón áurea. No la demostramos aquí, y en esta tabla la comprobamos en vez de creerla. Con ella, F(h + 3) > φ^(h+3)/√5 − 1, de modo que n + 2 ≥ N(h) + 2 = F(h + 3) + 1 > φ^(h+3)/√5. Tomando logaritmos en base φ y cambiando a base 2:

h < log_φ(n + 2) + log_φ √5 − 3, es decir, h < 1.4405 log₂(n + 2) − 1.3277

donde 1/log₂ φ = 1.44042… y 3 − log_φ √5 = 1.32772…. Escribimos 1.4405 redondeando hacia arriba, porque redondear hacia abajo daría una cota falsa: con 1.4404, el árbol de altura 18 ya no cumple la desigualdad. Esa es la forma exacta en nuestro convenio, en el que se cuentan aristas. Muchos libros cuentan nodos, de modo que su altura es 1 más que la nuestra, y escriben −0.3277 en vez de −1.3277. Es la misma cota.

En este curso diremos que la altura de un AVL es como máximo unas 1.44 veces log₂ n. El programa min_nodes calcula la recurrencia, la compara con Fibonacci y arma el árbol de verdad, insertando sus claves y midiendo su altura. log2n es log₂ de los nodos, 1.44log es 1.44 veces ese valor, y cota es la fórmula exacta de arriba:

$ build/min_nodes
  h    N(h) F(h+3)-1 medida  rot  log2n 1.44log    cota
  0       1        1      0    0   0.00    0.00    0.96
  1       2        2      1    0   1.00    1.44    1.55
  2       4        4      2    0   2.00    2.88    2.40
  3       7        7      3    0   2.81    4.04    3.24
  4      12       12      4    0   3.58    5.16    4.16
  5      20       20      5    0   4.32    6.22    5.10
  6      33       33      6    0   5.04    7.26    6.06
  7      54       54      7    0   5.75    8.29    7.04
  8      88       88      8    0   6.46    9.30    8.02
  9     143      143      9    0   7.16   10.31    9.01
 10     232      232     10    0   7.86   11.32   10.01
 11     376      376     11    0   8.55   12.32   11.01
 12     609      609     12    0   9.25   13.32   12.00
 16    4180     4180     16    0  12.03   17.32   16.00
 20   28656    28656     20    0  14.81   21.32   20.00
 24  196417   196417     24    0  17.58   25.32   24.00

Las columnas N(h) y F(h+3)-1 coinciden, y la altura medida es h: esos árboles existen y son AVL, y rot dice que se armaron sin ninguna rotación. La columna cota se pega a h: esos árboles casi la tocan, y por eso la constante no se puede bajar. Desde h = 20 queda a menos de 0.01 de h. La columna 1.44log, en cambio, va más de 1 unidad por encima desde h = 3.

Tres precisiones honestas sobre el número 1.44:

Es un redondeo hacia abajo. La constante de verdad es 1.44042…, que es mayor que 1.44. Por eso “h ≤ 1.44 log₂ n” no puede valer para todo n: el −1.3277 lo sostiene por mucho tiempo, pero al final pierde. Las pruebas de esta semana lo comprueban con enteros exactos: falla por primera vez en h = 4552, con un árbol cuya cantidad de nodos tiene 952 dígitos. Para todo árbol que puedan construir, vale.
Con n = 1 no es “por debajo”. Un solo nodo tiene h = 0 y 1.44 log₂ 1 = 0: son iguales. La frase correcta para árboles reales es h ≤ 1.44 log₂ n, con n ≥ 1. El árbol vacío tiene altura −1, y su log₂ 0 no existe.
Es el peor caso, y es raro. Hay que armar un árbol de Fibonacci a propósito para llegar ahí, como hacemos en fibonacci_tree.h. Con claves al azar la altura se queda bastante más abajo, y con claves ordenadas, más abajo aún. Lo medimos en la sección de mediciones.

Idea clave. Una condición local, en cada nodo, limita la altura total: un AVL alto necesita muchos nodos, porque la cantidad mínima crece como Fibonacci. Eso da h ≤ 2 log₂ n con una cuenta de una línea, y unas 1.44 veces log₂ n con la cuenta exacta.

Rotación

Ya sabemos que la condición basta. Falta poder restaurarla sin mover medio árbol. La herramienta es la rotación (rotation): una operación local que cambia la forma y conserva el orden.

Tomen un nodo x con hijo izquierdo y. Llamemos A y B a los subárboles de y, y C al subárbol derecho de x. Cualquiera de ellos puede estar vacío. Rotar a la derecha en x sube a y, y baja a x:

Animación en tres pasos, con líneas verticales que marcan una columna por cada parte y, abajo, el recorrido en orden A, y, B, x, C. Primero, x arriba con hijo izquierdo y y subárbol derecho C, y A y B cuelgan de y. Al rotar a la derecha en x, y sube y x baja, A sube un nivel, C baja un nivel, y B, resaltado, pasa de colgar de y a colgar de x. Al rotar a la izquierda en y, vuelve la forma inicial. En ningún paso cambia una columna ni el recorrido. — Las claves solo suben o bajan por su columna, así que el recorrido en orden no cambia. Solo B cambia de padre.

Rotar a la izquierda en y es la operación inversa. Una rotación se nombra por el nodo donde se aplica, x en el primer caso y y en el segundo, y por el lado hacia donde baja ese nodo. Noten lo que cambió:

x, antes padre de y, ahora es su hijo.
B, el subárbol del medio, cambió de padre: era hijo de y, y ahora es hijo de x.
A sigue colgado de y, y C sigue colgado de x.
Lo que colgaba del padre de x ahora es y.

Nada más. Son tres enlaces hacia abajo, sin importar cuántos nodos tengan A, B y C. Una rotación cuesta O(1).

Una rotación no rompe el orden

Afirmación. Una rotación conserva el recorrido en orden y, por lo tanto, la invariante de búsqueda.

El recorrido en orden de un subárbol es: en orden del izquierdo, el nodo, en orden del derecho. Apliquémoslo a los dos dibujos:

Antes: en orden de (y con A y B), luego x, luego C. Es decir, A, y, B, x, C.
Después: A, luego y, luego en orden de (x con B y C). Es decir, A, y, B, x, C.

Es la misma secuencia. Y la semana pasada vimos que un árbol binario es de búsqueda si y solo si su recorrido en orden sale ordenado. Además, lo de afuera no cambia: el subárbol sigue teniendo exactamente las mismas claves, y entonces sigue siendo correcto para todos los antepasados de x.

Se puede ver también con las desigualdades: todo lo de A es menor que y, todo lo de B está entre y y x, y todo lo de C es mayor que x. Los dos dibujos dicen exactamente eso. Por eso B cambia de padre: es lo único que cabe entre y y x.

rotation_demo lo muestra sobre un árbol pequeño, en el que A es el 10, B es el 30 y C es el 60:

$ build/rotation_demo
inicio: 40(20(10,30),60)
  en orden: 10 20 30 40 60
rotar a la derecha en 40: 20(10,40(30,60))
  en orden: 10 20 30 40 60
rotar a la izquierda en 20: 40(20(10,30),60)
  en orden: 10 20 30 40 60

La forma cambia, y la línea en orden no. Rotar y volver a rotar al otro lado deja el árbol como estaba.

Una rotación cambia las alturas

Para eso rotamos. En el dibujo, después de rotar a la derecha, A sube un nivel, C baja un nivel, y B se queda a la misma profundidad. Si A era el subárbol alto, la rotación arregla el desequilibrio.

Las únicas alturas guardadas que pueden cambiar son las de x e y. Las de A, B y C no se enteran, porque ningún nodo de adentro cambió de hijos. Y hay que recalcularlas en orden: primero x, que quedó abajo, y después y, que quedó arriba. Por encima de y, la altura del subárbol puede cambiar o no, y de eso se encarga quien sube reparando.

Rotar con y sin puntero al padre

Primero el pseudocódigo completo, con puntero al padre, que es lo que escribirán en el laboratorio. Cada enlace que cambia hacia abajo tiene su padre que cambia hacia arriba:

algoritmo rotar_izquierda(arbol, x)
    y ← hijo derecho de x
    medio ← hijo izquierdo de y
    hijo derecho de x ← medio
    si medio ≠ NULO entonces
        padre de medio ← x
    fin si
    poner a y en el lugar de x: en el enlace del padre de x, o en la raíz de arbol
    padre de y ← padre de x
    hijo izquierdo de y ← x
    padre de x ← y
    devolver y
fin algoritmo

rotar_derecha es el espejo: se cambia “derecho” por “izquierdo” en todas las líneas. Son tres enlaces hacia abajo y tres hacia arriba, y uno de ellos puede ser la raíz del árbol, que no es un enlace de ningún nodo. Por eso existe la función replace_child de la semana pasada.

La clase de los apuntes, AvlSet, es más simple: no tiene puntero al padre, y quien la llama se encarga de escribir el resultado en el enlace que corresponda. Así queda en C++:

// Sube al hijo derecho de x, y devuelve la nueva raíz del subárbol. Solo cambia enlaces.
Node* rotate_left(Node* x) {
    Node* y = x->right;
    x->right = y->left;
    y->left = x;
    rotations_++;
    return y;
}

Error común. En la versión con padre, olvidar el parent de B, el subárbol del medio. El árbol se ve bien y el recorrido en orden sale perfecto, porque ese recorrido baja por left y right. Falla mucho después, al subir por parent desde adentro de B. Por eso check_invariants revisa los padres, y por eso el laboratorio tiene una prueba solo para ese enlace. Además, B puede ser nulo: hay que preguntar antes de escribir middle->parent.

En C++. Una rotación solo cambia enlaces: ningún nodo cambia de clave ni de dirección. Por eso un puntero a un valor, o un iterador, sigue siendo válido después de una rotación, igual que en std::map. En cambio, el borrado de la semana pasada copia la clave del sucesor, y por eso nuestros punteros valen solo hasta el próximo erase.

Los cuatro casos

Después de insertar o borrar, subimos desde el punto del cambio. Supongamos que encontramos un nodo x con balance 2 o −2, y que todos los que están debajo de él ya están bien. Llamamos a x el nodo desbalanceado más bajo. Hay cuatro casos, que son dos y sus espejos. Se nombran por el camino hacia la parte pesada, desde x.

Izquierda-izquierda: una rotación simple

x tiene balance 2 y su hijo izquierdo y tiene balance 1: lo pesado está a la izquierda de la izquierda. Una rotación a la derecha en x lo arregla. Escribimos las alturas al lado de cada subárbol, en función de un número k:

          x  (k+3)                         y  (k+2)
         / \                              / \
 (k+2)  y   C  (k)     rotar a la        A   x  (k+1)
       / \             derecha en x   (k+1) / \
(k+1) A   B  (k)                           B   C
                                         (k)   (k)

A sube un nivel, que es justo lo que le sobraba. Antes de la rotación, el balance de x era (k + 2) − k = 2. Después, x tiene balance 0 y y tiene balance 0.

derecha-derecha es el espejo: x con balance −2, su hijo derecho con balance −1, y una rotación a la izquierda en x.

Izquierda-derecha: una rotación doble

x tiene balance 2 y su hijo izquierdo y tiene balance −1: lo pesado está a la derecha de la izquierda. Ahora una rotación a la derecha en x no sirve. El subárbol pesado es el del medio, y el del medio no sube al rotar, solo se muda. Veámoslo con el ejemplo más pequeño, 30, 10 y 20. errors/single_on_zigzag.cpp rota solo una vez:

$ g++ -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined errors/single_on_zigzag.cpp -o build/single_on_zigzag && build/single_on_zigzag
insertar 30: 30
insertar 10: 30(10,_)
insertar 20: 10(_,30(20,_))
single_on_zigzag: errors/broken_avl.h:202: static int BrokenAvl<bug>::check(const Node*) [with Bug bug = Bug::single_on_zigzag]: Assertion `std::abs(left - right) <= 1' failed.

La rotación convirtió un zigzag en otro, el espejo del anterior, igual de desbalanceado. check_invariants lo detiene.

La solución son dos rotaciones. Abramos el subárbol del medio en su raíz z, con hijos B y C. Primero, rotar a la izquierda en y sube a z y convierte el zigzag en el caso izquierda-izquierda. Después, rotar a la derecha en x, como en el caso simple:

Animación en tres pasos, con dos árboles a la vez. A la izquierda, el caso general: x de altura k + 3, su hijo y de altura k + 2, D de altura k, A de altura k, z de altura k + 1, y B y C de altura k o k − 1. A la derecha, 30 con balance 2, su hijo 10 con balance −1 y el 20. Rotar a la izquierda en y sube a z sobre y, y a la derecha sube el 20 sobre el 10. Rotar a la derecha en x deja a z arriba, de altura k + 2, con y y x de altura k + 1, y queda A, B bajo y, C, D bajo x; a la derecha queda 20 arriba, con 10 y 30, todos con balance 0. — Dos rotaciones, y el del medio queda arriba. A la izquierda, con subárboles y alturas; a la derecha, lo mismo con 30, 10 y 20.

B y C tienen altura k o k − 1, según dónde haya caído la última clave. Las alturas finales son las del último paso en los dos casos: z sube dos niveles y queda arriba, y queda un árbol con y y x como sus dos hijos. Es una sola idea, escrita como dos rotaciones: el del medio sube hasta arriba, y B y C se reparten entre y y x.

derecha-izquierda es el espejo: x con balance −2, su hijo derecho con balance 1. Primero se rota a la derecha en ese hijo, y después a la izquierda en x.

Cómo se decide

Se decide con dos signos, el de x y el del hijo pesado:

Balance de x	Balance del hijo pesado	Caso	Reparación
2	1	izquierda-izquierda	rotar a la derecha en x
2	0	izquierda-izquierda (solo al borrar)	rotar a la derecha en x
2	−1	izquierda-derecha	rotar a la izquierda en el hijo, y a la derecha en x
−2	−1	derecha-derecha	rotar a la izquierda en x
−2	0	derecha-derecha (solo al borrar)	rotar a la izquierda en x
−2	1	derecha-izquierda	rotar a la derecha en el hijo, y a la izquierda en x

La forma de recordarlo: si los dos signos coinciden, una rotación; si son opuestos, dos. El balance 0 del hijo no puede aparecer al insertar, y volveremos a él al borrar. Estas son las cuatro reparaciones sobre 3 claves:

$ build/avl_trace 30 20 10
insertar 30: 30
insertar 20: 30(20,_)
insertar 10: 20(10,30)
    reparo en 30: izquierda-izquierda
altura 1, rotaciones 1
$ build/avl_trace 10 20 30
insertar 10: 10
insertar 20: 10(_,20)
insertar 30: 20(10,30)
    reparo en 10: derecha-derecha
altura 1, rotaciones 1
$ build/avl_trace 30 10 20
insertar 30: 30
insertar 10: 30(10,_)
insertar 20: 20(10,30)
    reparo en 30: izquierda-derecha
altura 1, rotaciones 2
$ build/avl_trace 10 30 20
insertar 10: 10
insertar 30: 10(_,30)
insertar 20: 20(10,30)
    reparo en 10: derecha-izquierda
altura 1, rotaciones 2

Los cuatro terminan en el mismo árbol, 20(10,30). Ese es el resumen de la reparación: el árbol de 3 nodos bien balanceado, con la clave del medio arriba. La simple usa una rotación, y la doble, dos.

La reparación, en pseudocódigo y en C++

algoritmo reparar(arbol, x)
    si balance(x) > 0 entonces
        y ← hijo izquierdo de x
        si balance(y) < 0 entonces
            z ← rotar_izquierda(arbol, y)
            actualizar la altura de y
            actualizar la altura de z
        fin si
        arriba ← rotar_derecha(arbol, x)
    sino
        y ← hijo derecho de x
        si balance(y) > 0 entonces
            z ← rotar_derecha(arbol, y)
            actualizar la altura de y
            actualizar la altura de z
        fin si
        arriba ← rotar_izquierda(arbol, x)
    fin si
    actualizar la altura de x
    actualizar la altura de arriba
    devolver arriba
fin algoritmo

En AvlSet, sin padre, el enlace se escribe a mano. Esta es la mitad izquierda, y la otra es su espejo:

Node* repair_left_heavy(Node* x) {
    Node* y = x->left;
    // Con balance 0 en y, que solo pasa al borrar, basta la rotación simple.
    if (balance_of(y) < 0) {
        last_repairs_.push_back({x->key, "izquierda-derecha"});
        x->left = rotate_left(y);
        update_height(y);
        update_height(x->left);
    } else {
        last_repairs_.push_back({x->key, "izquierda-izquierda"});
    }
    Node* top = rotate_right(x);
    update_height(x);
    update_height(top);
    return top;
}

Observen que las rotaciones no tocan las alturas: de eso se encarga quien las llama. Se podría meter update_height dentro de la rotación, y muchos libros lo hacen. Aquí las separamos porque la semana 12 reutiliza las rotaciones en un árbol que tiene colores y no alturas.

Error común. Rotar y no actualizar las alturas, o actualizar la del padre antes que la del hijo. Después de rotate_right(x), el padre es top y el hijo es x: va primero x. Lo vemos con programas de verdad en la sección de las pruebas.

Insertar

Insertar en un AVL es insertar como la semana pasada, y luego subir desde el nodo nuevo hasta la raíz. En cada nodo del camino se actualiza la altura y, si el balance quedó en 2 o −2, se repara:

algoritmo subir_reparando(arbol, nodo)
    mientras nodo ≠ NULO hacer
        actualizar la altura de nodo
        si balance(nodo) > 1 o balance(nodo) < -1 entonces
            nodo ← reparar(arbol, nodo)
        fin si
        nodo ← padre de nodo
    fin mientras
fin algoritmo

algoritmo insertar(arbol, clave)
    bajar como en un árbol de búsqueda, y colgar un nodo nuevo donde se llegue a NULO
    si la clave ya estaba entonces
        devolver falso
    fin si
    subir_reparando(arbol, padre del nodo nuevo)
    devolver verdadero
fin algoritmo

Solo pueden cambiar las alturas de los antepasados del nodo nuevo, porque son los únicos cuyo subárbol cambió. Por eso basta subir por ese camino.

AvlSet lo hace con recursión. La llamada baja, y la vuelta de la recursión es la subida. Cada nivel escribe en su enlace lo que le devuelve el nivel de abajo, que puede ser un nodo distinto si hubo una rotación:

Node* insert_at(Node* node, const K& key, bool& added) {
    if (node == nullptr) {
        added = true;
        return new Node{key};
    }
    if (key < node->key) {
        node->left = insert_at(node->left, key, added);
    } else if (node->key < key) {
        node->right = insert_at(node->right, key, added);
    } else {
        return node;
    }
    return rebalance(node);
}

Node* rebalance(Node* node) {
    update_height(node);
    int balance = balance_of(node);
    if (balance > 1) {
        return repair_left_heavy(node);
    }
    if (balance < -1) {
        return repair_right_heavy(node);
    }
    return node;
}

La semana pasada dijimos que la recursión gasta pila proporcional a la altura, y que por eso un árbol sin balance puede tumbar el programa. Aquí esa objeción desaparece: con n = 1 000 000, la altura es como máximo 27, porque N(28) ya pasa de un millón, así que son menos de 30 marcos de llamada. El balance es lo que hace segura la recursión. Mantener la invariante paga también esto.

Paso a paso: 1, 2, 3, 4, 5, 6, 7

El peor orden de la semana pasada, y la primera pregunta de repaso de la guía:

$ build/avl_trace 1 2 3 4 5 6 7
insertar 1: 1
insertar 2: 1(_,2)
insertar 3: 2(1,3)
    reparo en 1: derecha-derecha
insertar 4: 2(1,3(_,4))
insertar 5: 2(1,4(3,5))
    reparo en 3: derecha-derecha
insertar 6: 4(2(1,3),5(_,6))
    reparo en 2: derecha-derecha
insertar 7: 4(2(1,3),6(5,7))
    reparo en 5: derecha-derecha
altura 2, rotaciones 4

Cada línea reparo en es una reparación. Esta animación sigue toda la secuencia, con la altura que guarda cada nodo, y muestra el árbol antes y después de cada reparación:

Animación en once pasos, con las claves 1 a 7 en columnas fijas, la altura guardada en cada nodo y un contador de rotaciones. Se insertan 1 y 2. Al insertar 3, el 1 queda con balance −2 y, al rotar a la izquierda, queda 2(1,3). Se inserta 4. Al insertar 5, el 3 queda con balance −2, y la raíz todavía guarda altura 2; al rotar, queda 2(1,4(3,5)). Al insertar 6, la raíz 2 queda con balance −2; al rotar, sube el 4 y el 3 pasa a ser hijo derecho del 2, de modo que el 4 tiene hijos 2 y 5. Al insertar 7, el 5 queda con balance −2; al rotar, queda el árbol perfecto 4(2(1,3),6(5,7)), de altura 2, con 4 rotaciones. — Sin balance, estas claves dan una cadena. Cada vez que la cadena crece demasiado, una rotación la acorta, y el subárbol reparado vuelve a la altura que tenía.

La tercera es la interesante. Al insertar el 6, el camino de subida pasa por 5, por 4 y por 2. El 5 y el 4 quedan con balance −1, y es el 2, la raíz, el que queda con −2. El hijo pesado es 4, con balance −1: caso derecha-derecha. Se rota a la izquierda en 2. El 4 sube, y su hijo izquierdo, el 3, se muda a ser hijo derecho del 2. Ese es el subárbol del medio de la rotación, y aquí no está vacío.

Al final queda el árbol perfecto, con 4 rotaciones en 7 inserciones. Sin balance, estas claves dan una cadena.

Paso a paso: 30, 10, 20

La segunda pregunta de repaso. La salida de build/avl_trace 30 10 20 ya la vimos: al insertar el 20, el 30 queda con balance 2 y su hijo 10 con balance −1. Signos opuestos: caso izquierda-derecha, con dos rotaciones. Es el lado derecho de la animación de la rotación doble, más arriba: primero se rota a la izquierda en 10, y luego a la derecha en 30, y queda 20(10,30).

Un caso con subárboles de verdad

En ese ejemplo, B y C eran vacíos. Veamos la rotación doble cuando no lo son:

$ build/avl_trace 50 20 70 10 30 25
insertar 50: 50
insertar 20: 50(20,_)
insertar 70: 50(20,70)
insertar 10: 50(20(10,_),70)
insertar 30: 50(20(10,30),70)
insertar 25: 30(20(10,25),50(_,70))
    reparo en 50: izquierda-derecha
altura 2, rotaciones 2

       50                   50                     30
      /  \                 /  \                  /    \
    20    70     --->    30    70     --->     20      50
   /  \                 /                     /  \       \
 10    30             20                    10    25      70
      /              /  \
    25             10    25

Aquí x es 50, y es 20, z es 30, y B es el 25, que termina como hijo derecho de 20. Si hubiéramos insertado el 35 en vez del 25, habría terminado como hijo izquierdo de 50: es el subárbol C.

Basta una reparación

Afirmación. En una inserción, basta una reparación, simple o doble: como máximo, 2 rotaciones. Después de ella, ningún antepasado queda desbalanceado.

La razón está en los dibujos con k. Antes de insertar, el nodo x tenía altura k + 2: su subárbol pesado tenía k + 1, y el otro, k. Veamos cuánto mide el subárbol completo después de reparar:

Caso	Altura de x antes de insertar	Altura tras insertar, sin reparar	Altura de la raíz tras reparar
izquierda-izquierda	k + 2	k + 3	k + 2
izquierda-derecha	k + 2	k + 3	k + 2

La reparación deja el subárbol con la misma altura que tenía antes de la inserción. Y los antepasados de x estaban bien antes de insertar, con esa altura. Para ellos, nada cambió. No pueden quedar desbalanceados.

Por qué el antes es así: antes de insertar, x tenía balance 1, porque si hubiera tenido 0 o −1 un aumento de 1 a la izquierda no llegaría a 2. Y el hijo y tenía balance 0, porque si hubiera tenido ±1 tras crecer de un lado, o bien su altura no habría cambiado, o bien él sería el desbalanceado más bajo. Por eso, después de una inserción, el hijo pesado tiene balance 1 o −1, y nunca 0. Es la razón de que esa fila de la tabla sea “solo al borrar”.

Hay que leer bien la frase “basta una reparación”. Dice que se hace como máximo una reparación. No dice:

Que la subida sea corta. Para encontrar el nodo desbalanceado hay que subir actualizando alturas, y eso son O(log n) pasos. Si no hay nada que reparar, hay que subir hasta que la altura de un nodo no cambie, o hasta la raíz.
Que siempre haya una. Muchas inserciones no reparan nada.
Que valga al borrar. No vale, como veremos.

Comprobemos la afirmación de la forma más directa. all_orders prueba todos los órdenes de inserción de n claves, y anota lo peor que ocurrió en una sola inserción:

$ build/all_orders
  n ordenes  h.min  h.max  max.reparaciones  max.rotaciones
  1       1      0      0                 0               0
  2       2      1      1                 0               0
  3       6      1      1                 1               2
  4      24      2      2                 1               2
  5     120      2      2                 1               2
  6     720      2      2                 1               2
  7    5040      2      3                 1               2
  8   40320      3      3                 1               2
  9  362880      3      3                 1               2

Son 362 880 órdenes para n = 9, y ninguna inserción necesitó más de una reparación ni más de 2 rotaciones. Eso, por sí solo, no demuestra nada para n grande: lo que lo demuestra es el argumento de las alturas. La prueba de la semana también lo revisa con un millón de claves.

Comparen las columnas de altura con la semana pasada. Allí, las 720 maneras de insertar 6 claves daban alturas de 2 a 5. Aquí son todas de altura 2. Con 7 claves ya aparece un 3, porque 7 = N(3) permite un árbol de Fibonacci de altura 3.

La cuenta de la inserción

Bajar: O(altura) comparaciones, igual que sin balance.
Subir: O(altura) actualizaciones, cada una O(1).
Reparar: como máximo una vez, O(1).

Como la altura es O(log n), insertar cuesta O(log n) en el peor caso, para cualquier orden de las claves. Eso no es un promedio ni un costo amortizado: vale para cada inserción.

Borrar

Borrar sigue la misma idea, y tiene dos diferencias que importan. Se borra como la semana pasada: sin hijos se quita, con un hijo este sube, y con dos hijos se copia el sucesor y se quita su nodo. Después se sube reparando desde el padre del nodo que salió de verdad del árbol:

algoritmo borrar(arbol, clave)
    nodo ← el nodo con esa clave
    si nodo = NULO entonces
        devolver falso
    fin si
    si nodo tiene dos hijos entonces
        sucesor ← el mínimo del subárbol derecho de nodo
        copiar a nodo la clave de sucesor
        nodo ← sucesor
    fin si
    padre ← padre de nodo
    poner al único hijo de nodo, o NULO, en el lugar de nodo
    liberar nodo
    subir_reparando(arbol, padre)
    devolver verdadero
fin algoritmo

Error común. Subir reparando desde el padre del nodo con la clave borrada, en vez de desde el padre del sucesor. En el caso de dos hijos, esos son dos lugares distintos: entre ellos pueden quedar alturas viejas. Por eso remove_node del laboratorio de la semana pasada devuelve el padre del nodo que salió.

En AvlSet, otra vez, la vuelta de la recursión hace la subida. La rama de dos hijos se llama a sí misma para quitar el sucesor del subárbol derecho, y toda la cadena de vuelta pasa por rebalance:

erased = true;
if (node->left == nullptr || node->right == nullptr) {
    Node* child = node->left != nullptr ? node->left : node->right;
    delete node;
    return child;
}
// Dos hijos: se copia el sucesor, y se quita su nodo del subárbol derecho.
const Node* next = node->right;
while (next->left != nullptr) {
    next = next->left;
}
node->key = next->key;
bool ignored = false;
node->right = erase_at(node->right, node->key, ignored);

Un ejemplo con dos hijos. Borrar el 5 aquí sube a 8, su sucesor, y el 9 toma el lugar del 8. Con eso, la raíz, que ahora guarda el 8, queda con el lado derecho muy bajo:

$ build/avl_trace 5 3 8 2 4 9 1 -5
insertar 5: 5
insertar 3: 5(3,_)
insertar 8: 5(3,8)
insertar 2: 5(3(2,_),8)
insertar 4: 5(3(2,4),8)
insertar 9: 5(3(2,4),8(_,9))
insertar 1: 5(3(2(1,_),4),8(_,9))
borrar 5: 3(2(1,_),8(4,9))
    reparo en 8: izquierda-izquierda
altura 2, rotaciones 1

La línea reparo en 8 nombra la clave que tenía el nodo desbalanceado en ese momento: es la raíz, ya con la clave copiada.

Primera diferencia: el hijo pesado puede tener balance 0

Al borrar, el lado que baja no es el del hijo pesado. Es el otro. Así que el hijo pesado no se tocó, y puede tener balance 0. Con dos subárboles de la misma altura, ¿qué rotación va? La simple:

 borrar 5:     4                   4                  2
              / \                 /                  / \
             2   5    --->       2      --->        1   4
            / \                 / \                    /
           1   3               1   3                  3

$ build/avl_trace 4 2 5 1 3 -5
insertar 4: 4
insertar 2: 4(2,_)
insertar 5: 4(2,5)
insertar 1: 4(2(1,_),5)
insertar 3: 4(2(1,3),5)
borrar 5: 2(1,4(3,_))
    reparo en 4: izquierda-izquierda
altura 2, rotaciones 1

¿Por qué no la doble? Porque la doble sube al nieto del medio, y aquí no hay razón para confiar en él. Si el hijo pesado tiene balance 0, sus dos subárboles miden lo mismo, y el del medio puede tener un subárbol alto y otro bajo. Al repartirlos entre x e y, puede quedar un lado con diferencia 2. El ejemplo es el de la prueba erase_zero_balance_uneven_grandchildren, donde la rotación simple sí funciona:

$ build/avl_trace 5 2 10 1 8 12 7 13 -1
insertar 5: 5
insertar 2: 5(2,_)
insertar 10: 5(2,10)
insertar 1: 5(2(1,_),10)
insertar 8: 5(2(1,_),10(8,_))
insertar 12: 5(2(1,_),10(8,12))
insertar 7: 5(2(1,_),10(8(7,_),12))
insertar 13: 5(2(1,_),10(8(7,_),12(_,13)))
borrar 1: 10(5(2,8(7,_)),12(_,13))
    reparo en 5: derecha-derecha
altura 3, rotaciones 1

Aquí x es 5, y su hijo pesado 10 tiene balance 0. Con la doble subiría el 8, y el 10 quedaría con solo el 12(_,13) a su derecha y nada a su izquierda: balance −2. En un caso como 2(1,4(3,5)), en cambio, la doble da un árbol correcto por casualidad, y la forma no es la misma. Si la condición del código está mal, solo se nota en algunos casos: fíjense bien en el < y el <=, porque ahí está este error.

Error común. Decidir entre simple y doble con balance_of(y) <= 0 en vez de balance_of(y) < 0. Al insertar nunca se nota, porque ahí el hijo pesado no tiene balance 0. El error aparece solo al borrar, y no en todos los borrados.

Segunda diferencia: la altura puede seguir bajando

Al insertar, la reparación devolvía al subárbol la altura que tenía antes de la operación, y por eso se terminaba el problema. Al borrar no pasa eso. Antes de borrar, x tiene altura k + 2, con el hijo pesado de altura k + 1 y el otro lado de altura k, que baja a k − 1:

Balance del hijo pesado	Reparación	Altura de la raíz tras reparar	Comparada con antes
1 (mismo signo)	simple	k + 1	bajó
0	simple	k + 2	igual: aquí se termina
−1 (signo opuesto)	doble	k + 1	bajó

En dos de los tres casos, el subárbol reparado es 1 más bajo que antes. Para el padre de x, un lado acaba de bajar, y eso es exactamente el mismo problema que había abajo. Puede desbalancearse él, y luego su padre.

El ejemplo extremo es un árbol de Fibonacci. Cada nodo tiene el lado derecho más bajo que el izquierdo, así que basta bajar algo a la derecha para encadenar el problema. Armamos el de altura 4 y borramos su clave mayor:

$ build/avl_trace 8 5 11 3 7 10 12 2 4 6 9 1 -12
insertar 8: 8
insertar 5: 8(5,_)
insertar 11: 8(5,11)
insertar 3: 8(5(3,_),11)
insertar 7: 8(5(3,7),11)
insertar 10: 8(5(3,7),11(10,_))
insertar 12: 8(5(3,7),11(10,12))
insertar 2: 8(5(3(2,_),7),11(10,12))
insertar 4: 8(5(3(2,4),7),11(10,12))
insertar 6: 8(5(3(2,4),7(6,_)),11(10,12))
insertar 9: 8(5(3(2,4),7(6,_)),11(10(9,_),12))
insertar 1: 8(5(3(2(1,_),4),7(6,_)),11(10(9,_),12))
borrar 12: 5(3(2(1,_),4),8(7(6,_),10(9,11)))
    reparo en 11: izquierda-izquierda
    reparo en 8: izquierda-izquierda
altura 3, rotaciones 2

Animación en cuatro pasos sobre el árbol de Fibonacci de altura 4, con la altura de cada nodo. Primero, el árbol con raíz 8, y el 5 y el 11 como hijos. Sale el 12, y el 11 queda con balance 2. Al reparar en 11 sube el 10, con 9 y 11 como hijos: ese subárbol baja de altura 2 a 1, y la raíz 8 queda con balance 2. Al reparar en 8 sube el 5, y queda con el 3 y el 8 como hijos, de altura 3. — La primera reparación deja el subárbol más bajo, y eso desbalancea más arriba. Es el peor caso: ⌊h/2⌋ = 2 reparaciones con h = 4.

Quitar el 12 desbalancea al 11. Se repara, y el subárbol pasa de altura 2 a 1. Eso desbalancea a la raíz, que tenía 3 a la izquierda y ahora 1 a la derecha. Se repara también. Dos reparaciones en un árbol de altura 4.

¿Cuántas reparaciones puede necesitar un borrado? Si hay una reparación en x, el hijo por donde se subió medía 2 menos que x antes de borrar. Es decir: cada reparación cuesta 2 de altura, y no 1. Si el camino hacia arriba pasa por k reparaciones, la altura del último nodo reparado es como mínimo 2k, y esa altura no supera a la del árbol. Por lo tanto, un borrado hace como máximo ⌊h/2⌋ reparaciones, si h es la altura del árbol antes de borrar. Cada una es de 1 o 2 rotaciones, así que son O(log n) en total.

Los árboles de Fibonacci llegan a ese límite. repair_counts lo comprueba hasta h = 26:

$ build/repair_counts
     operacion        n    rep/op    rot/op   max    h/2
insertar orden     1000     0.990     0.990     1      4
 insertar azar     1000     0.462     0.680     1      5
   borrar azar     1000     0.261     0.358     2      5
insertar orden    32000     1.000     1.000     1      7
 insertar azar    32000     0.466     0.701     1      8
   borrar azar    32000     0.270     0.379     4      8
insertar orden  1024000     1.000     1.000     1      9
 insertar azar  1024000     0.466     0.700     1     11
   borrar azar  1024000     0.266     0.373     5     11
Borrar la clave mayor de un arbol de Fibonacci
  h        n reparaciones rotaciones    h/2  h despues
  2        4            1          1      1          1
  3        7            1          1      1          2
  4       12            2          2      2          3
  5       20            2          2      2          4
  6       33            3          3      3          5
  7       54            3          3      3          6
  8       88            4          4      4          7
  9      143            4          4      4          8
 10      232            5          5      5          9
 14     1596            7          7      7         13
 18    10945            9          9      9         17
 22    75024           11         11     11         21
 26   514228           13         13     13         25

Lean las dos tablas por separado.

La segunda tabla es el peor caso del borrado: reparaciones igual a ⌊h/2⌋, una en cada antepasado del nodo borrado. “Una reparación en cada nivel” es correcto en este sentido: cada nivel de ese camino, y ese camino, en estos árboles, es corto y mide h/2. No hay un borrado con h reparaciones.

La primera tabla dice qué pasa normalmente. rep/op y rot/op son las reparaciones y rotaciones por operación, y max es lo máximo que ocurrió en una sola. En esta corrida:

Con claves ordenadas, casi cada inserción repara una vez, con una rotación simple. Las pruebas comprueban que el total de rotaciones es exactamente n − ⌊log₂ n⌋ − 1, para todo n hasta 5000. No lo demostramos.
Con claves al azar, menos de la mitad de las inserciones repara algo: 0.47 reparaciones y 0.70 rotaciones por inserción. max es 1.
Al borrar al azar se repara menos seguido, unas 0.27 veces por operación, pero max llegó a 5. Aunque el peor caso sea mayor, un borrado típico cuesta poco.

Son medidas, con una semilla fija, y no un teorema. Lo que sí está demostrado son los máximos: 1 al insertar, ⌊h/2⌋ al borrar.

Error común. Aplicar “basta una reparación” al borrado, y terminar la subida tras la primera. Pasa todas las pruebas de inserción, y pasa muchos borrados.

$ g++ -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined errors/stop_after_first_repair.cpp -o build/stop_after_first_repair && build/stop_after_first_repair
5000 inserciones al azar: todas pasan check_invariants
antes de borrar 12: 8(5(3(2(1,_),4),7(6,_)),11(10(9,_),12))
despues de borrar 12: 8(5(3(2(1,_),4),7(6,_)),10(9,11))
stop_after_first_repair: errors/broken_avl.h:202: static int BrokenAvl<bug>::check(const Node*) [with Bug bug = Bug::stop_after_first_repair]: Assertion `std::abs(left - right) <= 1' failed.

Con ese error, 5000 inserciones al azar pasan check_invariants. El árbol de Fibonacci lo atrapa: después de reparar el 11, nadie repara la raíz, que queda con 3 a la izquierda y 1 a la derecha.

La cuenta del borrado

Bajar, buscar el sucesor y subir son O(altura) pasos. Las reparaciones son O(altura) también, cada una O(1). Borrar cuesta O(log n) en el peor caso. A diferencia de la inserción, también en la cantidad de rotaciones.

Idea clave. Una inserción repara como máximo una vez, porque la reparación devuelve la altura de antes. Un borrado puede reparar en muchos niveles, hasta ⌊h/2⌋, porque la reparación suele dejar el subárbol 1 más bajo. Las dos cuestan O(log n).

La invariante en las pruebas

Con una estructura así, un error rara vez se nota enseguida. El árbol sigue dando respuestas correctas, porque el orden no se rompe: lo que se rompe es la promesa de que será bajo. Por eso, otra vez, check_invariants se llama después de cada operación en las pruebas al azar. Esta es la parte nueva, dentro de la revisión recursiva de la semana pasada:

assert(node->height == 1 + std::max(height_of(node->left), height_of(node->right)));
assert(std::abs(balance_of(node)) <= 1);

Son dos revisiones distintas, y las dos hacen falta:

La primera detecta una altura guardada que miente. Como se revisa en todos los nodos, de los hijos hacia arriba, una altura mala se detecta en el primer nodo donde no calza. No hace falta volver a bajar: si cada nodo calza con sus hijos, todas las alturas son las reales.
La segunda detecta un árbol de verdad desbalanceado. Sin la primera, no serviría de nada: si las alturas mienten, un balance perfecto no quiere decir nada.

Rotar sin actualizar las alturas

errors/no_height_update.cpp rota bien, pero no actualiza las alturas de los dos nodos de la rotación:

$ g++ -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined errors/no_height_update.cpp -o build/no_height_update && build/no_height_update
con 1, 2, 3: 2(1,3), altura guardada 1
con 1000 claves ordenadas: altura real 17, altura guardada 24
no_height_update: errors/broken_avl.h:201: static int BrokenAvl<bug>::check(const Node*) [with Bug bug = Bug::no_height_update]: Assertion `node->height == 1 + std::max(left, right)' failed.

Con 3 claves, la forma es correcta, y la raíz hasta guarda la altura correcta, por casualidad: el 2 ya tenía 1 antes de subir. Pero el 1, que ahora es una hoja, sigue guardando 2. Con 1000 claves, la altura real llegó a 17, cuando el árbol correcto tiene 9, y la guardada dice 24. Las decisiones se toman con números falsos, y el árbol se repara donde no debe y deja de hacerlo donde debe. Sigue siendo un árbol de búsqueda: todas las búsquedas responden bien, solo que más lentas. Sin check_invariants, una prueba que solo mire el contenido no lo vería.

Actualizar primero al padre

errors/parent_before_child.cpp actualiza las dos alturas, en el orden contrario:

$ g++ -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined errors/parent_before_child.cpp -o build/parent_before_child && build/parent_before_child
con 1, 2, 3: 2(1,3), altura real 1, altura guardada 3
con 1000 claves ordenadas: altura real 13, altura guardada 15
parent_before_child: errors/broken_avl.h:202: static int BrokenAvl<bug>::check(const Node*) [with Bug bug = Bug::parent_before_child]: Assertion `std::abs(left - right) <= 1' failed.

Sigamos las 3 claves, con 2 subiendo y 1 bajando. Antes de actualizar, el 1 todavía guarda altura 2, de cuando era la raíz de la cadena. El 2 se calcula primero: 1 + máx(2, 0) = 3, con la altura vieja de su nuevo hijo. Luego el 1 se corrige a 0, tarde. El 2 queda con altura guardada 3 y real 1. La regla es sencilla: update_height usa las alturas de los hijos, así que los hijos van primero. Después de una rotación, el hijo es el que bajó.

Idea clave. Toda altura guardada se calcula con las de sus hijos. Por eso se actualiza de abajo hacia arriba, tanto en la subida como dentro de una rotación.

Las pruebas de la clase

test_structures.cpp prueba AvlSet con casos dirigidos, con todos los órdenes de 8 claves, con los árboles de Fibonacci, y con 20 000 operaciones al azar, con semilla fija, comparando con std::set y llamando a check_invariants en cada paso. En cada una, además, revisa los máximos: una reparación al insertar y ⌊h/2⌋ al borrar.

Cuánto se gana

Todo esto vale si se nota en los números. Empecemos por la altura, que no depende de la máquina. height_table inserta n claves ordenadas y al azar. Sus árboles sin balance son el BstSet de la semana pasada, en plain_tree.h, reducido a lo que hay que medir. Con claves ordenadas sin balance, se detiene en 16 000, porque cuesta Θ(n²):

$ build/height_table
Claves ordenadas
        n  log2n 1.44log   avl  sin.bal
     1000   10.0    14.4     9      999
     4000   12.0    17.2    11     3999
    16000   14.0    20.1    13    15999
    64000   16.0    23.0    15        -
   256000   18.0    25.9    17        -
  1024000   20.0    28.8    19        -
Claves al azar, tres semillas
        n  log2n 1.44log   a1   a2   a3 prof.avl   s1   s2   s3 prof.sin
     1000   10.0    14.4   11   11   11     8.20   22   19   23    11.12
     4000   12.0    17.2   13   13   13    10.22   26   24   25    13.12
    16000   14.0    20.1   16   16   16    12.26   28   30   30    15.97
    64000   16.0    23.0   19   18   18    14.30   41   38   39    19.34
   256000   18.0    25.9   21   20   20    16.33   47   46   43    22.30
  1024000   20.0    28.8   23   23   23    18.35   49   51   49    24.73

En la primera tabla, avl es la altura del AVL y sin.bal la del árbol sin balance. En la segunda, a1 a a3 y s1 a s3 son las alturas con y sin balance, para tres semillas, y prof.avl y prof.sin son la profundidad media de un nodo, promediada entre esas semillas: lo que cuesta una búsqueda típica.

Tres cosas para leer aquí:

Claves ordenadas: lo mejor posible. La altura del AVL es exactamente ⌊log₂ n⌋, la altura mínima, en todas las filas. Las pruebas lo revisan para todo n hasta 5000. Era el peor caso de un árbol sin balance, y en el AVL resultó ser el mejor. Es una medición, no un teorema de estos apuntes.
Claves al azar: entre 1.1 y 1.2 veces log₂ n. Todas las filas quedan por debajo de 1.44 log₂ n, y la altura sin balance es entre 1.7 y 2.3 veces la del AVL. La profundidad media es menor que log₂ n y unos 25% menor que sin balance: la mayoría de los nodos está en los últimos niveles.
Nada se acerca a 1.44 log₂ n, salvo a propósito. Solo los árboles de Fibonacci de min_nodes lo hacen, y para armarlos hay que elegir las claves.

El reloj

avl_times usa -O2, sin sanitizers, y la mediana de 3 repeticiones. Los tiempos dependen de la máquina, que aquí es una laptop arm64 con otras tareas corriendo. En la primera tabla, x dice cuántas veces más tarda el árbol sin balance:

$ build/avl_times
Claves ordenadas: insertar (s)
        n       avl   sin.bal        x
     1000   0.00005   0.00091     18.9
     2000   0.00009   0.00358     38.6
     4000   0.00020   0.01432     70.1
     8000   0.00046   0.06139    134.6
    16000   0.00095   0.24263    254.9
Claves al azar: insertar y buscar todas (s)
        n   ins.avl   ins.sin  avl/sin   bus.avl   bus.sin  sin/avl
    16000   0.00270   0.00184     1.47   0.00150   0.00150     1.00
   128000   0.03328   0.02897     1.15   0.02228   0.02268     1.02
   512000   0.39233   0.26606     1.47   0.18000   0.18255     1.01

Claves ordenadas. El AVL crece apenas más que n, y el árbol sin balance se multiplica por 4 al duplicar n. La razón x se duplica, aproximadamente, en cada fila desde 4000 claves, y eso se repitió en todas las corridas; alguna fila con 2000 salió desviada. Con 16 000 claves, entre 230 y 300 veces.

Claves al azar. Aquí hay que ser honestos: el AVL no gana. En las corridas que hicimos, más de cinco, insertar costó entre 1.1 y 1.6 veces lo que cuesta sin balance: es el trabajo de actualizar alturas y rotar. Y buscar, que debería ganar porque la profundidad media es unos 25% menor, salió empatado: la columna sin/avl se movió entre 0.76 y 1.13, y con 512 000 claves el AVL perdió en casi todas las corridas. Las comparaciones sí bajan, como cuenta la tabla de arriba. El reloj no lo refleja, y no sabemos por qué. Una posibilidad es que las rotaciones dejen a padres e hijos más lejos en la memoria, pero no lo medimos, y este entorno no tiene perf. Lo dejamos como una pregunta abierta.

Lo que un AVL compra no es velocidad con datos al azar, donde un árbol sin balance ya va bien. Compra una garantía: ningún orden de llegada lo vuelve lento. Es la misma diferencia entre std::map y std::unordered_map, de la semana pasada.

El caso de la semana pasada

La promesa de la introducción. dictionary_avl carga palabras.txt tal como viene y barajado, con -O2 y mediana de 3:

$ build/dictionary_avl ../../data/palabras.txt
orden de bytes: si
AVL, tal como vienen: 1045757 palabras, altura 19, rotaciones 1045737, 0.196784 s
std::set, tal como vienen: 1045757 palabras, 0.161904 s
AVL, barajadas: 1045757 palabras, altura 23, rotaciones 729058, 1.30662 s
std::set, barajadas: 1045757 palabras, 1.29662 s
sin balance, barajadas: 1045757 palabras, altura 49, 1.51672 s

El archivo completo, en el orden malo: altura 19, y una fracción de segundo. La semana pasada estimamos cerca de una hora sin balance. Además, ese es el orden que resultó más rápido: barajadas, las mismas palabras tardan entre 6 y 7 veces más, aunque el árbol solo mide 4 niveles más. Es probable que ayude que cada palabra nueva baje por el mismo camino, recién visitado; no lo medimos.

std::set y nuestro AvlSet salen parecidos en esta tabla. std::set usa, en esta biblioteca, un árbol rojinegro. Compararlos con cuidado es el trabajo de la semana 12.

En la biblioteca. El estándar de C++ no dice qué árbol usa std::map: dice qué debe cumplir. Entre otras cosas, O(log n) para buscar, insertar y borrar una clave, y que insertar no invalide iteradores ni referencias. Un AVL con la inserción de hoy cumple esa última parte, porque una rotación no mueve el contenido de los nodos. Nuestro borrado no cumpliría lo que std::map promete al borrar, porque copia al sucesor: es el ejercicio 11 de la semana pasada.

El código de la semana

En code/week-11:

Archivo	Qué contiene
`avl_set.h`, `avl_trace.cpp`	El conjunto `AvlSet`, y un programa que lo sigue operación por operación
`rotation_demo.cpp`	Una rotación, a mano, con su recorrido en orden
`min_nodes.cpp`, `fibonacci_tree.h`	La recurrencia, Fibonacci, y los AVL más flacos, de verdad
`all_orders.cpp`, `repair_counts.cpp`	Cuántas reparaciones hace cada operación: conteos
`height_table.cpp`, `plain_tree.h`	La altura con y sin balance: conteos
`avl_times.cpp`, `dictionary_avl.cpp`, `bench.h`	Mediciones con `-O2` y sin sanitizers
`test_structures.cpp`	Pruebas de `AvlSet`: dirigidas, exhaustivas y al azar, contra `std::set`
`errors/`	Los programas con errores a propósito de este capítulo
`lab/`	Lo que deben completar en el laboratorio, con sus pruebas públicas

avl_trace les sirve para revisar cualquier ejercicio: cada argumento es una clave que se inserta, y una clave con signo menos se borra.

make compila, y make test lo comprueba todo. Eso incluye volver a correr los comandos de este capítulo, y revisar con enteros exactos, hasta h = 5000, las cuentas de la cota. Las mediciones no se comparan, porque dependen de la máquina; lo que se compara son conteos, como las alturas y las reparaciones.

El laboratorio

Esta semana hay una sola sesión de laboratorio, porque la otra es para la Práctica 3. Así que el código de partida ya trae lo que no es el tema. lab/avl_map.h tiene AvlMap<K, V>, que es el mapa de la semana 10 completo y funcionando, con su nombre cambiado y con un campo más al final del nodo: int height = 0;. Ustedes escriben únicamente lo propio de AVL.

make test-base       # el mapa de partida: pasa desde el inicio
make test-rotations  # paso 1: update_height y las rotaciones
make test-insert     # paso 2: inserción con balance, y check_invariants
make test-erase      # paso 3: borrado con balance, contra std::map
make test-lab        # todo
make bench           # paso 4: la tabla para su informe, con -O2 y sin sanitizers

Si su BstMap de la semana pasada pasó sus pruebas y prefieren seguir con el suyo, pueden: reemplacen en lab/avl_map.h los métodos que vienen de la semana 10 por los suyos, y dejen lo que está bajo el comentario Lo propio de AVL. Mientras make test-base siga pasando, el resto no cambia. Si su mapa quedó incompleto, no tienen que hacer nada: el de partida funciona.

Paso 1: altura y rotaciones (unos 30 minutos). Vienen hechos height_of y balance_of. Escriben update_height, rotate_left y rotate_right, con esta firma exacta, porque la semana 12 las usa tal como están:

Node* rotate_left(Node*) { not_implemented("rotate_left"); }
Node* rotate_right(Node*) { not_implemented("rotate_right"); }

Reciben el nodo que baja y devuelven el que sube. Arreglan los enlaces, los padres y root_. Suman 1 a rotations_. No tocan las alturas. replace_child de la semana pasada les resuelve el enlace del padre, y el caso de la raíz. Las pruebas de este paso rotan a mano sobre árboles armados en un orden que no provoca reparaciones, así que no dependen de los pasos que siguen. También comprueban que no tocan las alturas y que ningún nodo cambia de contenido.

Paso 2: insertar (unos 40 minutos). Escriben repair y rebalance_up, a partir del pseudocódigo de reparar y de subir_reparando. repair suma 1 a repairs_. Llaman a rebalance_up en insert_node, y no en insert: si no, operator[] insertaría sin balancear. Luego agregan a check_invariants las dos líneas nuevas. Las pruebas broken_* dañan árboles sanos, y exigen que las dos revisiones funcionen, también con una altura mal puesta justo en la raíz.

Paso 3: borrar (unos 25 minutos). Una sola línea, si rebalance_up está bien: remove_node ya devuelve el padre del nodo que salió. El tiempo es para los errores que aparezcan, porque las pruebas al azar con std::map revisan todo a la vez. Para encontrar un error, busquen la secuencia corta con avl_trace, que da las formas correctas, y comparen con pre_order_keys.

Paso 4: medir (unos 15 minutos). make bench viene hecho, y compara su mapa con el árbol sin balance y con 1.44 log₂ n. Con esa tabla responden las preguntas cortas de lab/report.md.

Además, este laboratorio cuenta: rotations() y repairs() son públicas, y las pruebas exigen una reparación como máximo por inserción, y exactamente ⌊h/2⌋ al borrar la clave mayor de un árbol de Fibonacci. Una reparación de más también se nota.

Resumen

La condición AVL: en cada nodo, las alturas de sus dos subárboles difieren en 1 como máximo. Cada nodo guarda su altura, con −1 para el nulo.
El AVL con menos nodos para una altura h cumple N(h) = N(h − 1) + N(h − 2) + 1, es decir N(h) = F(h + 3) − 1. N(4) = 12. Esos son los árboles de Fibonacci.
De ahí salen h ≤ 2 log₂ n, con una cuenta corta, y h < log_φ(n + 2) + log_φ √5 − 3, es decir, h < 1.4405 log₂(n + 2) − 1.3277, la forma exacta contando aristas. Lo resumimos como “unas 1.44 veces log₂ n”.
Una rotación cambia la forma, y conserva el recorrido en orden. Cuesta O(1): tres enlaces hacia abajo, y sus tres padres. Solo pueden cambiar las alturas de los dos nodos que rotan.
Hay cuatro casos. Si los signos del balance de x y de su hijo pesado coinciden, va una rotación simple; si son opuestos, una doble. Con balance 0 en el hijo, que solo pasa al borrar, va la simple.
Insertar: bajar, colgar y subir actualizando alturas y reparando. Basta una reparación, de 1 o 2 rotaciones, porque devuelve al subárbol su altura de antes. La subida sigue costando O(log n).
Borrar: igual, desde el padre del nodo que salió de verdad. Una reparación puede dejar el subárbol 1 más bajo y desbalancear más arriba: como máximo ⌊h/2⌋ reparaciones, O(log n) en total.
Las alturas se actualizan de abajo hacia arriba: primero el hijo, y después el padre. Tras una rotación, el hijo es el que bajó.
check_invariants revisa cada altura guardada contra sus hijos, y cada balance. Se llama después de cada operación en las pruebas al azar.
Con claves ordenadas, la altura medida fue ⌊log₂ n⌋. Al azar, entre 1.1 y 1.2 veces log₂ n. Solo un árbol de Fibonacci armado a propósito se acerca a 1.44 log₂ n.
Con claves al azar, un AVL no fue más rápido que un árbol sin balance. Lo que compra es que ningún orden lo vuelva lento: un millón de palabras ordenadas, en una fracción de segundo.

Ejercicios

Para los primeros, comprueben sus respuestas con build/avl_trace.

Inserten 20, 4, 26, 3, 9, 15 en un AVL vacío, a mano. Digan qué caso se presenta y dibujen el árbol tras cada reparación. Luego, cambien el 15 por un 8 y repitan.
Digan si estos árboles son AVL, y calculen el balance de cada nodo: 5(3(1,_),8(7,9(_,10))), 4(2(1,3),6(5,7)), 6(3(2(1,_),_),9(7,10)).
Inserten 1, 2, …, 15 en orden en un AVL. ¿Cuántas rotaciones hacen? ¿Qué forma queda? Comparen con n − ⌊log₂ n⌋ − 1.
¿Cuál es la menor cantidad de nodos de un AVL de altura 6? ¿Y la mayor? Dibujen los dos primeros niveles del que tiene menos, y den un orden de inserción que lo arme sin ninguna rotación.
Dibujen el caso derecha-izquierda con las alturas en función de k, como aquí se hizo con izquierda-derecha. Muestren que el subárbol termina con la altura que tenía antes de la inserción.
Con avl_trace, armen un árbol de Fibonacci de altura 6 y encuentren un borrado que haga 3 reparaciones. ¿Cuál es el orden de las claves para armarlo? Usen fibonacci_keys de fibonacci_tree.h.
Expliquen por qué, al insertar, el hijo pesado no puede tener balance 0, y den un árbol pequeño en el que, al borrar, sí lo tenga.
Sobre su rebalance_up, agreguen la parada temprana: si un nodo no se reparó y su altura no cambió, ninguno de los de arriba cambia, y se puede terminar. Cuenten cuántos nodos visita la subida, con y sin parada, al insertar y al borrar 100 000 claves al azar. Tengan cuidado: ¿por qué no basta con “balance 0”?
En vez de la altura, guarden solo el balance, −1, 0 o 1, en cada nodo. ¿Qué cambia en rotate_left, en la subida y en la reparación? ¿Qué ganarían en memoria con claves int y valores int? Comprueben con sizeof. ¿Por qué los libros que hacen esto tienen tablas de casos para actualizarlo?
Con repair_counts como modelo, midan las reparaciones por borrado si siempre se borra la clave menor, en vez de una al azar. Corran con 3 tamaños antes de concluir.
Sobre AvlMap, agreguen std::size_t count en cada nodo y const K* kth(std::size_t i) const en O(log n). ¿Dónde hay que actualizar count? ¿Qué hay que actualizar después de cada rotación, y en qué orden? Compárenlo con el ejercicio 6 de la semana pasada.
El número 1.44 está redondeado hacia abajo. Sin programa, solo con la fórmula exacta: ¿para qué valor de log₂ n pasa 1.44 log₂ n a estar por debajo de 1.44042 log₂ n − 1.3277? Luego comparen con lo que dice la prueba test_rounded_constant_fails_only_for_huge_n.