Árboles rojinegros

La semana pasada, un AVL se reparaba con rotaciones y un número guardado en cada nodo: su altura. Funciona, y con las rotaciones ya hechas podríamos dar el tema por cerrado. Sin embargo, si abren el código de std::map en la biblioteca del curso no van a encontrar alturas. Van a encontrar un color.

Hoy vemos ese árbol, el árbol rojinegro (red-black tree). Si se presenta como una lista de reglas de color y una tabla de casos, parece arbitrario, y se olvida a la semana siguiente. Por eso no vamos a empezar por ahí. Vamos a empezar por otra forma de mantener un árbol balanceado, que se entiende en un dibujo: nodos con más de una clave, y todas las hojas a la misma profundidad. Se llama árbol 2-3-4. Después vamos a escribir esos nodos con nodos binarios y un color, y las cinco propiedades, la altura y cada caso de la inserción van a salir de ahí. El color no es un truco: dice qué nodos binarios forman juntos un solo nodo del árbol 2-3-4.

De paso veremos la idea de los B-trees, que son los árboles de las bases de datos, y al final mediremos AVL, rojinegro y std::map con las mismas claves. Algunos resultados van a ir en contra de lo que se suele repetir.

En el laboratorio escribirán RedBlackMap con las rotaciones de la semana pasada, tal como están.

Ruta de lectura.

• Antes de clase (15 a 20 minutos, obligatorio): Otra forma de balancear: nodos con más de una clave, Insertar en un árbol 2-3-4, La idea de los B-trees y Representar un nodo de 3 o 4 hijos con nodos binarios.
• En clase: Las cinco propiedades, Por qué la altura es O(log n), Insertar, La comparación de verdad: árbol 2-3-4 contra árbol rojinegro, La invariante en las pruebas y ✂️ Eliminación: la idea, y por qué tiene tantos casos. La eliminación se ve solo si alcanza el tiempo.
• Después de clase: repasen con el Resumen y los Ejercicios, y lean AVL, rojinegro y std::map, medidos y El código de la semana. Opcional: Open Data Structures, secs. 9.1 (2-4 Trees) y 9.2 (RedBlackTree), que usa la variante inclinada a la izquierda (este curso usa la clásica); CLRS, capítulo Red-Black Trees, y capítulo B-Trees solo para la idea.

Código. Los programas de este capítulo están en code/week-12. 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.

Otra forma de balancear: nodos con más de una clave

Un AVL permite que las hojas estén a distintas profundidades, y limita la diferencia. Ahora vamos a pedir algo que parece imposible: todas las hojas a la misma profundidad, siempre. Con nodos binarios no se puede, salvo con 2^k − 1 claves exactas. Pero si un nodo puede tener más de una clave, tenemos holgura: una clave nueva puede entrar en un nodo que ya existe, sin crear un nivel.

Definición. Un árbol 2-3-4 (2-3-4 tree) es un árbol de búsqueda en el que:

• Cada nodo tiene 1, 2 o 3 claves, ordenadas.
• Un nodo con k claves que no es hoja tiene exactamente k + 1 hijos. Por eso hay nodos de 2, de 3 y de 4 hijos, y de ahí el nombre.
• Las claves del hijo número i caen entre las claves i − 1 e i de su padre: es el orden de un árbol de búsqueda, con más casilleros.
• Todas las hojas están a la misma profundidad.

Escribimos un nodo entre corchetes, con sus claves, y sus hijos después, entre paréntesis:

[20]([10 15],[25 30])

              [20]
            /      \
      [10 15]      [25 30]

Buscar es lo que se imaginan: dentro del nodo se comparan hasta 3 claves, y se baja por el hijo que corresponde.

¿Por qué sirve? Un árbol con L niveles y todas las hojas en el último tiene, como mínimo, un nodo arriba, 2 en el siguiente, 4 en el siguiente, y así hasta 2^(L−1) abajo, cada uno con al menos una clave. Sumando: n ≥ 1 + 2 + 4 + … + 2^(L−1) = 2^L − 1. Es decir, L ≤ log₂(n + 1). Una condición simple, sin alturas guardadas, y la altura queda limitada. Todo el problema está en mantener la condición al insertar.

Insertar en un árbol 2-3-4

La regla central: una clave nueva siempre entra en una hoja que ya existe. Nunca se crea un nodo debajo de una hoja. Con eso, las hojas no pueden quedar a distintas profundidades.

Se baja como en una búsqueda hasta una hoja. Si tiene lugar, es decir, 1 o 2 claves, la clave entra ahí y se terminó. El problema es la hoja llena, con 3 claves. Entonces se divide (split): la clave del medio de esas 3 sube al padre, y las otras dos quedan como dos nodos separados. La clave nueva entra en el que le corresponde.

$ build/tree_234_trace 5 3 8 1
insertar 5: [5]
insertar 3: [3 5]
insertar 8: [3 5 8]
insertar 1: [5]([1 3],[8])
    se divide [3 5 8]
niveles 2, divisiones 1

Al insertar el 1, la hoja [3 5 8] está llena. El 5, que era el del medio, sube. Como no hay padre, se crea uno nuevo.

Que suba una clave al padre puede llenarlo a él. Entonces se repite lo mismo un nivel más arriba: el padre, si está lleno, se divide, y así sucesivamente. Hay dos finales posibles:

• Se llega a un nodo con lugar, y ahí se termina.
• Se divide la raíz. Entonces aparece una raíz nueva con una sola clave, y el árbol crece un nivel. Es la única forma en que crece, y por eso todas las hojas bajan un nivel juntas y siguen a la misma profundidad.

Una cascada completa. Con estas diez claves en orden, la última llena dos nodos seguidos, y divide la raíz:

$ build/tree_234_trace 1 2 3 4 5 6 7 8 9 10
insertar 1: [1]
insertar 2: [1 2]
insertar 3: [1 2 3]
insertar 4: [2]([1],[3 4])
    se divide [1 2 3]
insertar 5: [2]([1],[3 4 5])
insertar 6: [2 4]([1],[3],[5 6])
    se divide [3 4 5]
insertar 7: [2 4]([1],[3],[5 6 7])
insertar 8: [2 4 6]([1],[3],[5],[7 8])
    se divide [5 6 7]
insertar 9: [2 4 6]([1],[3],[5],[7 8 9])
insertar 10: [4]([2]([1],[3]),[6 8]([5],[7],[9 10]))
    se divide [7 8 9]
    se divide [2 4 6]
niveles 3, divisiones 5

Idea clave. Un árbol 2-3-4 crece desde arriba: las hojas nunca bajan por su cuenta, y el árbol gana un nivel solo cuando se divide la raíz. Por eso todas las hojas están siempre a la misma profundidad.

Cuándo se divide

Hay un detalle que esta semana importa: cuándo se divide. Hay por lo menos tres reglas razonables:

1. Dividir solo cuando hace falta, y subir la del medio de las 3 que tenía el nodo. Es la que acabamos de ver. Es la regla de este capítulo, y la llamaremos dividir al hacer overflow.
2. Dividir solo cuando hace falta, pero juntar primero las 4 claves y subir siempre la segunda. Open Data Structures, en la sec. 9.1, describe así la división: deja dos y tres hijos.
3. Dividir de camino hacia abajo: al bajar, se divide cada nodo lleno que se encuentre, haga falta o no. Así, cuando se llega a la hoja seguro tiene lugar, y una inserción nunca tiene que volver a subir. CLRS lo hace así en los B-trees.

Las tres mantienen las reglas del árbol 2-3-4, y en las tres la inserción cuesta O(log n). Pero no dan el mismo árbol. Cuando comparemos con el árbol rojinegro, esto va a importar.

La cuenta, y por qué no se programa así

Bajar y subir son O(L) pasos, cada uno con un trabajo constante, porque un nodo tiene como máximo 3 claves. Insertar cuesta O(log n) en el peor caso.

El árbol 2-3-4 es limpio en un dibujo, y no tanto en código: tres tamaños de nodo, o un nodo de un solo tamaño con lugares vacíos, y un ciclo más dentro de cada paso. Nuestro tree_234.h existe para comparar, y usa dos std::vector en cada nodo. Pronto vamos a ver que se puede tener la misma estructura con nodos binarios. Antes, una idea que nace de aquí.

La idea de los B-trees

Un B-tree es la misma idea llevada lejos: todas las hojas a la misma profundidad, y nodos con muchas claves, no 3 sino cientos. Se inserta igual: la clave entra en una hoja, y si se llena, se divide, y la clave del medio sube al padre. Un árbol 2-3-4 es un B-tree con muy pocas claves por nodo.

¿Para qué tantas claves? Porque el costo cambia cuando el árbol vive en disco. Un disco no entrega bytes sueltos: entrega bloques enteros, una página, de unos pocos KB. Leer una página cuesta muchísimo más que comparar claves dentro de una que ya está en memoria, unas mil veces más o bastante más, según el disco. Lo que hay que contar entonces no son las comparaciones: son las páginas leídas, una por cada nivel que se baja, si cada nodo ocupa una página.

btree_levels cuenta los niveles que necesitan mil millones de claves, en el mejor caso, con todos los nodos llenos. Con m claves por nodo, cada nodo tiene m + 1 hijos, y L niveles guardan (m + 1)^L − 1 claves:

$ build/btree_levels
 claves.por.nodo  niveles
               1       30
               3       15
              15        8
             100        5
             500        4
            1000        3

Un árbol binario perfecto baja 30 niveles, es decir, 30 lecturas de disco. Con 1000 claves por nodo bastan 3 lecturas. Esa es la respuesta a por qué una base de datos prefiere nodos con muchas claves: no busca ahorrar comparaciones, porque hace unas cuantas más dentro de cada nodo. Busca ahorrar lecturas de disco. En memoria, ese mismo argumento pierde casi toda su fuerza, y por eso seguimos con nodos binarios.

Aquí nos quedamos con la idea. El curso de Bases de Datos los construye de verdad, con páginas de disco, y con la variante B+ tree que usan los sistemas reales.

Representar un nodo de 3 o 4 hijos con nodos binarios

Ahora el paso central. Queremos un árbol binario de búsqueda común, con sus rotaciones y su find de siempre, que por dentro sea un árbol 2-3-4. La idea: cada nodo 2-3-4 se escribe como un nodo negro arriba, con sus demás claves como hijos rojos. Un enlace a un hijo rojo no es un nivel de verdad: dice “esta clave pertenece al mismo nodo 2-3-4 que su padre”.

En los dibujos, y en toda la salida de los programas, una r después de la clave marca los nodos rojos. Los demás son negros. A, B, C y D son los subárboles que cuelgan del nodo.

Lean bien el dibujo, porque cada forma importa:

• Un nodo con 1 clave tiene una sola forma.
• Un nodo con 3 claves tiene una sola forma: el del medio arriba, negro, con sus dos vecinos rojos. Una cadena como 5(3r(1r,_),_) no es una forma de escribirlo: tiene un rojo con hijo rojo, y eso está prohibido.
• Un nodo con 2 claves tiene dos formas, según cuál de las dos quede arriba. En un árbol rojinegro clásico, las dos son válidas.

Idea clave. Rojo quiere decir “soy parte del nodo de mi padre”. Si juntan cada nodo negro con sus hijos rojos, reaparece el árbol 2-3-4. A esa operación la llamaremos colapsar el árbol.

Colapsar

Esta es la salida de rb_trace, que muestra cada árbol y, debajo, lo que da al colapsarlo:

$ build/rb_trace 10 20 30 15 25
insertar 10: 10
    en 10: raiz roja: pintar de negro
    2-3-4: [10]
insertar 20: 10(_,20r)
    2-3-4: [10 20]
insertar 30: 20(10r,30r)
    en 10: tio negro, en linea: una rotacion
    2-3-4: [10 20 30]
insertar 15: 20(10(_,15r),30)
    en 20: tio rojo: recolorear
    en 20: raiz roja: pintar de negro
    2-3-4: [20]([10 15],[30])
insertar 25: 20(10(_,15r),30(25r,_))
    2-3-4: [20]([10 15],[25 30])
altura 2, negros 2, rotaciones 1, recoloreos 1

Después de las líneas en, que veremos pronto, fíjense en la última forma. El árbol final, y el árbol 2-3-4 al que colapsa:

         20                      [20]
        /  \                    /    \
      10    30           [10 15]      [25 30]
        \   /
        15r 25r

Los dos nodos de 2 claves del resultado están escritos de formas distintas: 10 con 15r a su derecha, y 30 con 25r a su izquierda. En un árbol clásico, esto ocurre tal cual, sin ningún arreglo posterior.

Cuántos árboles rojinegros tiene un árbol 2-3-4

La relación tiene una dirección clara:

• Un árbol rojinegro colapsa a exactamente un árbol 2-3-4. Colapsar no tiene ninguna decisión que tomar.
• Un árbol 2-3-4 viene de varios árboles rojinegros. Si tiene t nodos de 2 claves, cada uno se puede escribir de dos formas, y las decisiones son independientes: son exactamente 2^t árboles rojinegros.

No hace falta creerlo. all_shapes genera todos los árboles rojinegros válidos con las claves 1 a n, sin insertar nada: arma todas las combinaciones de formas y colores que cumplen las propiedades. Colapsa cada uno y comprueba que cada árbol 2-3-4 aparece exactamente 2^t veces. Si en algún caso no fuera así, el programa se detendría. Luego prueba todos los órdenes de inserción y cuenta cuántos de esos árboles se pueden obtener insertando:

$ build/all_shapes
  n rojinegros  2-3-4  suma.2^t  alcanzables h.todos  h.ins   cota
  1          1      1         1            1       0      0   1.00
  2          2      1         2            2       1      1   2.17
  3          2      2         2            1       1      1   3.00
  4          4      2         4            4       2      2   3.64
  5          8      4         8            6       2      2   4.17
  6         16      5        16           12       3      3   4.61
  7         33      9        33           29       3      3   5.00
  8         56     15        56           48       3      3   5.34
  9         90     28        90           58       3      3   5.64

rojinegros y suma.2^t coinciden en todas las filas. La columna alcanzables cuenta otra cosa, y es más baja: no todo árbol rojinegro válido se puede obtener insertando. Con 3 claves hay dos árboles válidos, 20(10r,30r) y 20(10,30), y al insertar siempre sale el primero. El segundo, todo negro, es correcto, pero la inserción nunca lo produce a partir de un árbol vacío. Las columnas h.todos, h.ins y cota las leemos más adelante.

Este curso usa el árbol clásico

Hay más de un árbol que se llama rojinegro. Open Data Structures, en su sec. 9.2, usa una variante inclinada a la izquierda (left-leaning): agrega la propiedad de que un hijo derecho rojo solo puede existir si el izquierdo también es rojo. Con eso, cada nodo de 2 claves tiene una sola forma, y cada árbol 2-3-4 tiene un único árbol rojinegro. Según el libro, eso reduce la cantidad de casos.

Este curso, CLRS y la biblioteca del curso usan el árbol clásico, que no tiene esa propiedad y que tiene dos formas para cada nodo de 2 claves. Pueden leer el capítulo de Open Data Structures para el puente con los árboles 2-4, que es lo mismo que aquí, pero no mezclen sus casos de inserción con los nuestros. Si en su árbol aparece un 10(_,15r), como el de arriba, en la variante de ese libro sería un error, y aquí es correcto.

Las cinco propiedades

Definición. Un árbol rojinegro es un árbol binario de búsqueda en el que cada nodo tiene un color, y se cumple:

1. Cada nodo es rojo o negro.
2. La raíz es negra.
3. Las hojas nulas son negras.
4. Un nodo rojo solo tiene hijos negros.
5. Todo camino desde un nodo hasta sus hojas nulas pasa por la misma cantidad de negros.

Las hojas nulas son los lugares vacíos: cada nullptr donde podría colgar un hijo. Se las piensa como negras y sin clave, y por eso un nodo sin hijos se puede considerar interno. En CLRS son un nodo centinela. Nosotros no reservamos nada: nullptr es la hoja nula, y una función pequeña dice de qué color es:

static bool is_red(const Node* node) { return node != nullptr && node->color == Color::red; }

Cada propiedad tiene una razón en el árbol 2-3-4:

La última es la clave. Cada nodo negro de un camino es exactamente un nodo 2-3-4 que ese camino atraviesa. Contar negros es contar niveles. Y por lo que dice la propiedad 4, los rojos no alteran la cuenta, porque cada rojo pertenece al nodo de su padre.

Colapsar funciona porque se cumplen estas propiedades, y no por casualidad. La 4 garantiza que un negro con sus hijos rojos abarca todo su grupo: 1, 2 o 3 claves. La 5 garantiza que todas las hojas nulas quedan a la misma profundidad en el árbol colapsado.

Error común. Pensar que la propiedad 5 se refiere solo a la raíz. Dice desde cada nodo. Y la cuenta es sobre caminos hasta las hojas nulas, no hasta los nodos sin hijos: 10(5,_) tiene un solo nodo sin hijos, y no es válido, porque el camino por la derecha del 10 llega a una hoja nula con un negro, y el de la izquierda con dos.

La cantidad de negros en un camino desde la raíz hasta una hoja nula tiene nombre: es la altura negra (black height) del árbol. CLRS define la altura negra de un nodo sin contar ese nodo, y contando la hoja nula. Son dos maneras de contar lo mismo, y dan el mismo número para la raíz, que es negra. Nuestro black_height() cuenta los negros de la raíz para abajo, sin la hoja nula. Con esa definición, b es exactamente la cantidad de niveles del árbol 2-3-4.

El nodo:

struct Node {
    K key;
    Node* left = nullptr;
    Node* right = nullptr;
    Color color = Color::red;
};

Por qué la altura es O(log n)

Ahora la cota, sin inducción. Son dos cuentas, y las dos se leen en el árbol colapsado. Sea un árbol rojinegro con n claves, y sea b su altura negra.

Primera cuenta: b es pequeño. Colapsen el árbol. Por lo anterior, queda un árbol 2-3-4 con b niveles, todas sus hojas en el último. Cada nodo tiene al menos 2 hijos, salvo en el último nivel, y por eso el nivel i tiene por lo menos 2^i nodos, cada uno con al menos una clave. Sumando niveles:

n ≥ 1 + 2 + 4 + … + 2^(b−1) = 2^b − 1, es decir, b ≤ log₂(n + 1)

Segunda cuenta: un camino tiene como máximo 2b nodos. Tomen un camino cualquiera desde la raíz hacia abajo. Tiene b negros, o menos si no llega hasta una hoja nula. ¿Cuántos rojos? Por la propiedad 4, cada rojo tiene un padre negro, y dos rojos no pueden ir seguidos. Además, la raíz es negra. Cada rojo del camino va entonces justo después de un negro distinto, y eso da como máximo b rojos.

Por lo tanto, cualquier camino tiene como máximo 2b nodos. Nuestra altura cuenta aristas, como en las semanas anteriores: un camino de 2b nodos tiene 2b − 1 aristas. Juntando las dos cuentas:

h ≤ 2b − 1 ≤ 2 log₂(n + 1) − 1

Es la cota de la guía, con un detalle a nuestro favor: la forma usual, h ≤ 2 log₂(n + 1), es cierta aquí y sobra en 1, porque CLRS cuenta también la arista que llega a la hoja nula, y nosotros no. Con cualquiera de las dos, la altura es O(log n). Con un millón de claves, 2 log₂(n + 1) − 1 da unos 39. Es menos ajustada que los 1.44 log₂ n de un AVL.

El camino más largo y el más corto, desde un mismo nodo

Tomen ahora un nodo x cualquiera, y dos caminos desde x hasta hojas nulas. Por la propiedad 5, los dos pasan por la misma cantidad de negros, digamos b_x, contando a x si es negro. ¿Cuánto puede medir cada uno, en nodos, sin contar la hoja nula?

• Si x es negro: el más corto tiene al menos b_x nodos, todos negros. El más largo tiene como máximo 2 b_x, alternando negro y rojo. El largo es a lo sumo el doble del corto.
• Si x es rojo: tiene que contarse a sí mismo en los dos. El corto tiene al menos b_x + 1 nodos. El largo tiene como máximo 2 b_x + 1, alternando rojo y negro. Como 2 b_x + 1 ≤ 2 (b_x + 1), tampoco pasa del doble.

Por eso, desde un mismo nodo, un camino hasta una hoja nula puede tener como máximo el doble de nodos que otro. Ese es el balance de un árbol rojinegro: más flojo que el de AVL, pero sigue siendo balance. La explicación en una frase: entre dos caminos, solo los rojos hacen la diferencia, y no puede haber más rojos que negros, salvo uno más si el camino empieza en rojo.

Qué tan cerca se llega

all_orders prueba todos los órdenes de inserción de n claves. En la columna cuentas revisa los dos pasos de la cota en cada árbol final: n ≥ 2^b − 1 y h + 1 ≤ 2b:

$ build/all_orders
  n ordenes  h.min  h.max  cota  max.rotaciones  max.recoloreos  cuentas
  1       1      0      0  1.00               0               0       si
  2       2      1      1  2.17               0               0       si
  3       6      1      1  3.00               2               0       si
  4      24      2      2  3.64               2               1       si
  5     120      2      2  4.17               2               1       si
  6     720      2      3  4.61               2               1       si
  7    5040      2      3  5.00               2               1       si
  8   40320      3      3  5.34               2               1       si
  9  362880      3      3  5.64               2               1       si

Aquí cota es 2 log₂(n + 1) − 1. Con tan pocas claves, queda holgada. Para ver cuánto se puede acercar, height_bound calcula el árbol rojinegro válido con menos nodos para cada altura. Sale de armar el camino más largo posible, alternando colores, y colgar de cada nodo del camino el subárbol más barato que la propiedad 5 permita:

$ build/height_bound
  h  min.nodos negros     cota h/log2n
  0          1      1     1.00    0.00
  1          2      1     2.17    1.00
  2          4      2     3.64    1.00
  3          6      2     4.61    1.16
  4         10      3     5.92    1.20
  5         14      3     6.81    1.31
  6         22      4     8.05    1.35
  8         46      5    10.11    1.45
 10         94      6    12.14    1.53
 12        190      7    14.15    1.59
 16        766      9    18.17    1.67
 20       3070     11    22.17    1.73
 24      12286     13    26.17    1.77
 32     196606     17    34.17    1.82
 40    3145726     21    42.17    1.85

La cota queda a unas 2 unidades de h en cada fila desde h = 4, y h/log2n sube despacio hacia 2: la constante 2 no se puede bajar, si solo se sabe que el árbol cumple las propiedades. Las columnas h.todos de all_shapes confirman esta tabla para n ≤ 9, y las pruebas lo comparan. Y como ven en esa misma tabla, para cada n, h.ins llega a lo mismo que h.todos en estas filas: con tan pocas claves, insertando se llega a la altura máxima.

Insertar

Ya sabemos qué queremos mantener. Insertar empieza como en cualquier árbol de búsqueda: se baja, y se cuelga un nodo nuevo donde se llegue a una hoja nula. La pregunta es de qué color.

Por qué el nodo nuevo es rojo

Si fuera negro, ese camino tendría un negro más que todos los demás. La propiedad 5 se rompería en todos los antepasados a la vez, y arreglar eso es un problema global. Y en el árbol 2-3-4, un nodo negro nuevo es un nodo 2-3-4 nuevo, debajo de una hoja: justo lo que dijimos que nunca se hace.

Si es rojo, la propiedad 5 no cambia, porque el rojo no cuenta. Lo único que se puede romper es la 4, si su padre también es rojo, o la 2, si el nodo nuevo es la raíz. Las dos son problemas locales, en un solo lugar. Y en el árbol 2-3-4, un nodo rojo nuevo es una clave que entra en un nodo que ya existe, que es exactamente la regla.

errors/new_node_black.cpp lo pinta de negro:

$ g++ -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined errors/new_node_black.cpp -o build/new_node_black && build/new_node_black
insertar 10: 10
insertar 20: 10(_,20)
new_node_black: errors/broken_rb.h:178: static int BrokenRb<bug>::check_node(const Node*, const int*, const int*, std::size_t&) [with Bug bug = Bug::new_node_black; std::size_t = long unsigned int]: Assertion `left == right' failed.

Con solo dos claves, a la izquierda del 10 hay cero negros debajo, y a la derecha hay uno.

La inserción, en pseudocódigo

Llamamos z al nodo rojo que puede estar en conflicto. Si su padre es rojo, hay un problema: un rojo con hijo rojo. Como la raíz es negra, ese padre rojo no es la raíz, y por eso z tiene abuelo, que es negro. Llamamos tío al otro hijo del abuelo. Un tío nulo es una hoja nula, así que cuenta como negro.

algoritmo insertar(arbol, clave)
    bajar como en un árbol de búsqueda
    si la clave ya estaba entonces
        devolver falso
    fin si
    colgar un nodo nuevo z, rojo, donde se llegó a NULO
    reparar_insercion(arbol, z)
    devolver verdadero
fin algoritmo

algoritmo reparar_insercion(arbol, z)
    mientras el padre de z es rojo hacer
        padre ← padre de z
        abuelo ← padre de padre
        si padre es hijo izquierdo de abuelo entonces
            tio ← hijo derecho de abuelo
            si tio es rojo entonces
                pintar de negro a padre y a tio
                pintar de rojo a abuelo
                z ← abuelo
            sino
                si z es hijo derecho de padre entonces
                    z ← padre
                    padre ← rotar_izquierda(arbol, z)
                fin si
                pintar de negro a padre
                pintar de rojo a abuelo
                rotar_derecha(arbol, abuelo)
            fin si
        sino
            lo mismo, cambiando izquierdo por derecho y rotar_izquierda por rotar_derecha
        fin si
    fin mientras
    pintar de negro a la raiz de arbol
fin algoritmo

Las rotaciones son las de la semana pasada: reciben el nodo que baja, devuelven el que sube, y no saben nada de colores. Hay tres situaciones, cada una con su equivalente en el árbol 2-3-4. Las vemos una por una, para el lado izquierdo. El derecho es su espejo.

Primera situación: el padre es negro

No hay nada que hacer: ninguna propiedad se rompió. En el árbol 2-3-4, la clave entró en un nodo con lugar, y además quedó bien escrita:

[10]  → [5 10]           10        →        10
                                           /
                                          5r

[3 5] → [3 5 8]           5        →         5
                         /                  / \
                       3r                 3r   8r

El segundo caso es un nodo de 2 claves que pasa a 3 sin ningún arreglo, porque el nodo nuevo cayó justo del lado libre del negro.

Segunda situación: tío negro. Un nodo de 2 claves pasa a 3, con la forma equivocada

El padre es rojo y el tío es negro. Entonces el grupo del abuelo es un nodo con 2 claves: el abuelo negro y su único hijo rojo, el padre. El tío no pertenece al grupo, porque es negro. La clave nueva tiene lugar: el nodo pasa a 3 claves. Ningún nodo 2-3-4 se divide, y el árbol 2-3-4 queda con la forma correcta. El problema es solamente cómo está escrito en binario: quedó como una cadena negro-rojo-rojo, y un nodo de 3 claves tiene una sola forma, con el del medio arriba. La arreglamos con rotaciones.

En línea. z, el padre y el abuelo están en línea recta. El del medio ya es el padre. Basta rotar a la derecha en el abuelo y cambiar los colores. Es una rotación:

En zigzag. z es hijo derecho y el padre es hijo izquierdo, o al revés. El del medio es z, y está abajo. Primero se rota en el padre, y eso convierte el zigzag en una línea, con los papeles cambiados: el z de antes pasa a ser el padre, y el padre de antes pasa a ser el z. Por eso el pseudocódigo escribe z ← padre antes de rotar. Luego se hace lo mismo que en el caso anterior. Son dos rotaciones:

Es la misma forma de pensar de la semana pasada: el del medio sube hasta arriba, y los subárboles se reparten. Y el resultado es el dibujo del nodo de 3 claves: un negro con dos hijos rojos. Comparen con los dos casos dobles y simples de AVL.

Error común. Olvidar z ← padre en el zigzag, o, en general, seguir el ciclo con el nodo equivocado. Después de las rotaciones, el z que quedó es el negro que subió, y su padre nuevo puede ser rojo. El ciclo vuelve a entrar, y arregla algo que no estaba roto. Este error se escapa en árboles pequeños, porque hace falta un padre rojo arriba. A nosotros nos lo atrapó la prueba al azar, mientras escribíamos este material.

¿Qué pasa con el tío negro? En la primera vuelta del ciclo, con z recién insertado, un tío negro es siempre nulo: el padre es rojo y tiene un hijo nulo, así que debajo del abuelo por ese lado no hay ningún negro, y por la propiedad 5 tampoco por el otro. Solo se encuentra un tío negro de verdad en las vueltas siguientes, después de un recoloreo.

Tercera situación: tío rojo. Un nodo lleno se divide

El padre es rojo y el tío es rojo. Entonces el grupo del abuelo es un nodo con 3 claves, lleno: el abuelo negro con sus dos hijos rojos. La clave nueva no cabe. Hay que dividirlo, y la del medio, que es el abuelo, sube.

Dividirlo con colores es casi gratis. Se pintan el padre y el tío de negro, con lo que cada uno pasa a ser parte de arriba de su propio nodo. Se pinta el abuelo de rojo, con lo que ahora pertenece al nodo de su padre. Y z queda rojo debajo del padre, con lo que queda en el nodo que le corresponde. Sin mover ningún enlace. Ninguna rotación, tres cambios de color:

Pero subir el abuelo al nodo de arriba es igual que insertar una clave allí, y ese nodo puede estar lleno, o quedar mal escrito. En código es lo mismo: el abuelo ahora es un rojo que puede tener padre rojo. Por eso, z ← abuelo, y sigue el ciclo. Aquí, entonces, el problema sube, y está en marcha lo que en el árbol 2-3-4 era una cascada de divisiones.

Cada vuelta del ciclo sube z dos niveles, y por eso hay como máximo ⌊h/2⌋ recoloreos, con h la altura del árbol con el nodo nuevo ya colgado.

Fíjense en que la división es la del overflow, y la que sube es la del medio de las 3 que tenía el nodo, sin importar dónde cae z. Ahí está la razón de que el árbol rojinegro calce con el árbol 2-3-4 de esa regla, y no con las otras dos.

Al final: la raíz

Si el ciclo llegó a la raíz con un recoloreo, el abuelo es la raíz y quedó roja. La propiedad 2 está rota. Se pinta de negro, y listo. Esa línea tiene significado: es dividir la raíz del árbol 2-3-4, la clave del medio queda sola en un nodo nuevo, arriba. Es el único momento en el que la altura negra aumenta, y el equivalente exacto de “el árbol 2-3-4 gana un nivel”. También se ejecuta con la primera clave, que entra roja en un árbol vacío.

Error común. Olvidar pintar la raíz de negro al final. El árbol sigue encontrando todo, y de vez en cuando deja la raíz roja. En el mapa con puntero al padre es peor: si la raíz es roja y tiene un hijo rojo, el ciclo busca el abuelo, que es nulo, y falla.

$ g++ -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined errors/no_root_paint.cpp -o build/no_root_paint && build/no_root_paint
insertar 10: 10r
insertar 20: 10r(_,20r)
insertar 30: 20(10r,30r)
insertar 40: 20r(10,30(_,40r))
insertar 50: 20r(10,40(30r,50r))
encuentra el 40: si
no_root_paint: errors/broken_rb.h:58: void BrokenRb<bug>::check_invariants() const [with Bug bug = Bug::no_root_paint]: Assertion `!is_red(root_)' failed.

La búsqueda responde bien, y check_invariants lo detiene.

La tabla de casos

Con la tabla al lado, la pregunta 2 de la guía tiene una respuesta exacta. Un nodo rojo con hijo rojo rompe la propiedad 4. En el árbol 2-3-4 corresponde a una de dos situaciones, y las dos son transitorias, en medio de una inserción: un nodo lleno que ya no puede recibir otra clave, si el tío es rojo, o un nodo de 3 claves bien formado pero mal escrito, si el tío es negro.

Paso a paso: 10, 20, 30, 15, 25

Esta es la pregunta de repaso de la guía. La salida ya la vimos. Ahora, con los árboles:

Caso por caso: el 10, solo pintar la raíz. El 20, nada. El 30, tío negro en línea, 1 rotación. El 15, tío rojo, 1 recoloreo, y pintar la raíz, que es el momento en que el árbol 2-3-4 gana un nivel. El 25, nada. Al terminar, altura 2, altura negra 2, 1 rotación, 1 recoloreo. Y en el árbol final aparecen las dos formas de un nodo de 2 claves.

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

El mismo orden de la semana pasada, donde el AVL terminó en el árbol perfecto 4(2(1,3),6(5,7)), de altura 2, con 4 rotaciones:

$ build/rb_trace 1 2 3 4 5 6 7 | tail -4
insertar 7: 2(1,4r(3,6(5r,7r)))
    en 5: tio negro, en linea: una rotacion
    2-3-4: [2 4]([1],[3],[5 6 7])
altura 3, negros 2, rotaciones 3, recoloreos 2

El rojinegro termina con altura 3, y su raíz tiene a un lado un solo nodo y al otro una rama de 3 niveles. Un AVL no lo permitiría, porque esa raíz tendría balance −2. Un árbol rojinegro tolera un desbalance que un AVL repara, y por eso puede hacer menos trabajo al insertar y quedar más alto. Vamos a medir cuánto.

Un caso con todo: el problema sube, y arriba encuentra un tío negro

Es el ejemplo que conviene seguir con lápiz:

$ build/rb_trace 11 2 14 1 7 15 5 8 4
insertar 11: 11
    en 11: raiz roja: pintar de negro
    2-3-4: [11]
insertar 2: 11(2r,_)
    2-3-4: [2 11]
insertar 14: 11(2r,14r)
    2-3-4: [2 11 14]
insertar 1: 11(2(1r,_),14)
    en 11: tio rojo: recolorear
    en 11: raiz roja: pintar de negro
    2-3-4: [11]([1 2],[14])
insertar 7: 11(2(1r,7r),14)
    2-3-4: [11]([1 2 7],[14])
insertar 15: 11(2(1r,7r),14(_,15r))
    2-3-4: [11]([1 2 7],[14 15])
insertar 5: 11(2r(1,7(5r,_)),14(_,15r))
    en 2: tio rojo: recolorear
    2-3-4: [2 11]([1],[5 7],[14 15])
insertar 8: 11(2r(1,7(5r,8r)),14(_,15r))
    2-3-4: [2 11]([1],[5 7 8],[14 15])
insertar 4: 7(2r(1,5(4r,_)),11r(8,14(_,15r)))
    en 7: tio rojo: recolorear
    en 11: tio negro, zigzag: dos rotaciones
    2-3-4: [2 7 11]([1],[4 5],[8],[14 15])
altura 3, negros 2, rotaciones 2, recoloreos 3

Corran build/tree_234_trace con las mismas claves y comparen: los árboles 2-3-4 son los mismos. Veamos la última inserción, que hace las dos cosas. Antes de ella, el árbol es este:

           11
         /    \
       2r      14
      /  \       \
     1    7      15r
         / \
       5r   8r

El 4 cae a la izquierda del 5. Su padre 5 es rojo, y su tío 8 es rojo: el nodo [5 7 8] está lleno. Recolorear: 5 y 8 a negro, y 7 a rojo. Es la división, y el 7 sube.

Ahora z es el 7. Su padre 2 es rojo, y su tío 14 es negro, un negro de verdad, que no es nulo. En el árbol 2-3-4, el 7 acaba de llegar al nodo [2 11], que tiene lugar y pasa a [2 7 11]. Lo único que falta es escribirlo bien. El 7 es hijo derecho y el 2 es hijo izquierdo: zigzag. Rotar a la izquierda en 2, y a la derecha en 11, y cambiar colores:

              7
           /     \
         2r       11r
        /  \     /   \
       1    5   8     14
           /            \
         4r             15r

Un negro, el 7, con dos hijos rojos, el 2 y el 11: es la única forma de escribir [2 7 11]. Los cuatro subárboles que quedaron debajo son los hijos de ese nodo, en orden. Fueron una división, en colores, y dos rotaciones.

Como máximo dos rotaciones

Afirmación. Una inserción hace como máximo 2 rotaciones. Después de ellas, el ciclo termina.

El argumento es directo. Una vuelta con tío rojo no rota nada. Una vuelta con tío negro hace 1 o 2 rotaciones, y deja negro al nodo que queda arriba del subárbol, con z como hijo. En la siguiente comprobación del ciclo, el padre de z es negro, y el ciclo se termina. Por lo tanto, en cada inserción se rota como máximo en una vuelta.

Comprobémoslo de la forma más directa. La tabla de all_orders de la sección anterior lo revisó en todos los órdenes de hasta 9 claves: max.rotaciones nunca pasa de 2, y llega a 2 desde n = 3. Lo mismo ocurre en los órdenes al azar de un millón de claves que veremos más adelante. Eso, por sí solo, no demuestra nada para n grande: lo que lo demuestra es el argumento.

Lo que no tiene ese límite es el recoloreo. La columna max.recoloreos vale 1 con tan pocas claves, porque el árbol es bajo; en count_table vamos a ver 18 recoloreos en una sola inserción. Crece con la altura, y por lo que vimos es como máximo ⌊h/2⌋.

La cuenta de la inserción

• Bajar: O(altura) comparaciones.
• Subir recoloreando: O(altura) en el peor caso, cada paso en O(1).
• Rotar: como máximo 2 veces, O(1).

Insertar cuesta O(log n) en el peor caso, para cualquier orden de las claves. Y hay una diferencia con la semana pasada: el ciclo termina en cuanto el padre de z es negro, y muchas veces eso ocurre enseguida.

En C++

Los apuntes usan RedBlackSet, en rb_set.h, igual que la semana pasada usaron AvlSet: es recursivo y no tiene puntero al padre. Como no hay padre, no hay z que suba. El ciclo se vuelve a la vuelta de la recursión: cada nivel se pregunta como abuelo si debajo de él hay un rojo con hijo rojo. Toma las mismas decisiones en el mismo orden, y las pruebas lo comprueban: todos los órdenes de hasta 7 claves, y 4000 claves al azar, dan la misma forma y las mismas cuentas que el mapa con puntero al padre.

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 repair_from_grandparent(node);
}

Esta es la reparación, para el lado izquierdo:

Node* left = grandparent->left;
Node* right = grandparent->right;
if (is_red(left) && (is_red(left->left) || is_red(left->right))) {
    if (is_red(right)) {
        recolor(grandparent);
        return grandparent;
    }
    if (is_red(left->right)) {
        last_steps_.push_back({grandparent->key, "tio negro, zigzag: dos rotaciones"});
        grandparent->left = rotate_left(left);
    } else {
        last_steps_.push_back({grandparent->key, "tio negro, en linea: una rotacion"});
    }
    Node* top = rotate_right(grandparent);
    top->color = Color::black;
    grandparent->color = Color::red;
    return top;
}

En el laboratorio escribirán la otra versión, con ciclo y puntero al padre, a partir del pseudocódigo. Las rotaciones no conocen el color: cambiar colores es de quien las llama, igual que en AVL lo eran las alturas. Por eso sirven sin cambios.

La comparación de verdad: árbol 2-3-4 contra árbol rojinegro

Hemos dicho que el árbol rojinegro es un árbol 2-3-4. Pongamos esa frase a prueba. collapse_check arma los dos con las mismas claves, colapsa el rojinegro y compara la forma completa: las claves de cada nodo y el orden de sus hijos. Lo hace con las tres reglas de división, y con todos los órdenes de hasta 9 claves:

$ build/collapse_check
  n ordenes    medio  segunda al.bajar
  1       1        0        0        0
  2       2        0        0        0
  3       6        0        0        0
  4      24        0       12        0
  5     120        0       60        0
  6     720        0      432        0
  7    5040        0     3216        0
  8   40320        0    28032        0
  9  362880        0   267840    31104
Primer orden en que no calza
  al hacer overflow, sube la del medio de las 3: ninguno
  al hacer overflow, sube siempre la segunda de las 4: 1 3 4 2
    rojinegro: [3]([1 2],[4])
    2-3-4:     [2]([1],[3 4])
  al bajar, se divide todo nodo lleno: 1 2 3 4 5 6 7 8 9
    rojinegro: [2 4 6]([1],[3],[5],[7 8 9])
    2-3-4:     [4]([2]([1],[3]),[6]([5],[7 8 9]))
Claves al azar, tres semillas, comparando tras cada insercion
  semilla 12: calza
  semilla 13: calza
  semilla 14: calza

Cada columna cuenta los órdenes en que no calzan. Lo que se encontró:

• La inserción clásica calza exactamente con el árbol 2-3-4 que se divide al hacer overflow, subiendo la del medio de las 3 que tenía. En los 362 880 órdenes de 9 claves, y en las 3000 claves al azar de cada semilla, no hay ninguna diferencia. Hasta 8 claves y con esas semillas, además se compara después de cada inserción: la misma forma, tantas divisiones como recoloreos, y tantos niveles como negros.
• Si se juntan las 4 claves y sube siempre la segunda, no calza, y la diferencia aparece con solo 4 claves. Con 1, 3, 4 y 2, el nodo [1 3 4] recibe el 2. El rojinegro hace subir al 3, que era el del medio, y el 2 se queda con el
  1. La otra regla ordena 1, 2, 3, 4, y hace subir al 2. Open Data Structures describe esa regla en la sec. 9.1. Es un árbol 2-3-4 correcto, solo que no es el nuestro.
• Si se divide al bajar, tampoco calza. Hasta 8 claves no se nota en ningún orden. Con 9 sí. Con las claves en orden, el nodo [2 4 6] está lleno y la clave 9 no lo necesita: la hoja [7 8] tenía lugar. Quien divide al bajar lo divide igual, y gana un nivel que el otro no tiene: 3 niveles contra 2.

Por lo tanto, la frase correcta no es “un árbol rojinegro es un árbol 2-3-4”, sin más. Es esta:

Idea clave. Todo árbol rojinegro colapsa a un árbol 2-3-4 válido. Y la inserción clásica, que repara de abajo hacia arriba, hace exactamente lo mismo, paso a paso, que un árbol 2-3-4 que se divide solo al hacer overflow, subiendo la del medio de las 3. Con otra regla de división se obtiene otro árbol 2-3-4, también válido.

Existen árboles rojinegros que reparan de arriba hacia abajo, al bajar. Corresponden a la tercera regla. No son los que usamos aquí.

La invariante en las pruebas

Como en AVL, un error en estos árboles rara vez se nota enseguida. El orden no se rompe: lo que se rompe es la promesa de que será bajo. Las búsquedas siguen respondiendo bien, como acabamos de ver con la raíz roja. Por eso check_invariants se llama después de cada operación en las pruebas al azar.

Esta es la parte central de la revisión. Es recursiva, y devuelve los negros de cada subárbol hasta una hoja nula:

assert(node->color == Color::red || node->color == Color::black);
if (is_red(node)) {
    assert(!is_red(node->left) && !is_red(node->right));
}
int left = check_node(node->left, low, &node->key, count);
int right = check_node(node->right, &node->key, high, count);
assert(left == right);
return left + (is_red(node) ? 0 : 1);

Vale la pena decir con exactitud qué hace cada línea por las cinco propiedades, porque no todas se revisan igual:

• Propiedad 1. Color tiene solo dos valores con nombre. Solo se puede romper con un cast o con memoria dañada. Se revisa igual, con la primera línea, porque cuesta poco.
• Propiedad 2. Es una línea aparte, en check_invariants: assert(!is_red(root_));.
• Propiedad 3. Se cumple sola: un nullptr no tiene color guardado, e is_red dice que no es rojo. No hay árbol que la rompa. Lo que sí se comprueba es que su is_red diga eso: si dijera lo contrario, los árboles sanos fallarían en la propiedad 4.
• Propiedad 4. La condición del if.
• Propiedad 5. left == right, en cada nodo. Si todos los nodos lo cumplen, se cumple para todos los caminos.

A eso se suman, como siempre, el orden, los padres, en el mapa, y el tamaño.

Error común. Comprobar la propiedad 5 contando los negros solo por el camino de más a la izquierda y por el de más a la derecha. El error puede estar en medio: en 20(10(5,15r),30(25,35)), los dos caminos de los extremos tienen 3 negros, y el que pasa por el 15 tiene 2. Por eso el laboratorio trae árboles así.

Antes de usar el verificador, verifíquenlo

Un check_invariants con un error es peor que no tener ninguno, porque da confianza. Por eso, antes de confiar en él, el laboratorio se lo prueba con árboles rotos que se arman a mano, sin pasar por insert. Hay un árbol por cada forma de romper algo: raíz roja, rojos seguidos en distintos lugares, negros desiguales en los extremos y por dentro, orden roto solo contra un antepasado lejano, un padre mal puesto, un tamaño falso, y un color que no es ninguno de los dos.

Cada prueba revisa primero un árbol sano, para que un verificador que siempre falla tampoco pase.

Los otros dos errores de esta semana

Rotar en el zigzag solo una vez. Como en AVL, un zigzag se convierte en su espejo:

$ 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(10r,_)
insertar 20: 10(_,30r(20r,_))
single_on_zigzag: errors/broken_rb.h:174: static int BrokenRb<bug>::check_node(const Node*, const int*, const int*, std::size_t&) [with Bug bug = Bug::single_on_zigzag; std::size_t = long unsigned int]: Assertion `!is_red(node->left) && !is_red(node->right)' failed.

Rotar y no cambiar los colores deja la forma bien y el color mal, y errors/no_repaint_after_rotation.cpp lo muestra.

✂️ Eliminación: la idea, y por qué tiene tantos casos

Borrar no se implementa en este curso: RedBlackMap no ofrece erase. Pero conviene saber qué pasa, y una vez más el árbol 2-3-4 lo explica.

Se empieza igual que siempre: si la clave tiene dos hijos, se la cambia por su sucesor, y lo que sale de verdad es un nodo con un hijo como máximo. Hay dos casos fáciles, y uno difícil:

• Sale un nodo rojo. No cambia ninguna cuenta de negros. En el árbol 2-3-4, una clave sale de un nodo que tenía más de una. Se terminó.
• Sale un negro con un hijo rojo. Ese hijo sube y se pinta de negro. También aquí el nodo 2-3-4 tenía otra clave. Se terminó.
• Sale un negro sin hijos. Este es el difícil. Ese nodo era un nodo 2-3-4 con una sola clave, y al sacarla queda vacío. Todos los caminos por ahí tienen un negro de menos. CLRS lo expresa como un negro “doble” sobre la hoja nula que queda, un negro de deuda.

Para pagar la deuda hay que mirar al hermano, y ver si en el árbol 2-3-4 tiene claves que prestar:

Son 4 casos, con sus espejos, 8. Por eso tiene fama de difícil. Lo que pasa es que la operación en el árbol 2-3-4 es sencilla, fusión o préstamo, y la complicación está en las dos formas de un nodo de 2 claves, que multiplican los dibujos. Lo mismo pasó en la inserción, con la línea y el zigzag.

La cuenta de rotaciones sale de la tabla. Solo la fusión hace subir el problema, y no rota. El hermano rojo rota una vez, y después de él el problema ya no sube. Un préstamo termina. Son como máximo 3 rotaciones por borrado, y O(log n) recoloreos. Recuerden que un borrado en AVL podía hacer hasta ⌊h/2⌋ reparaciones. Esa es la ventaja de peor caso que se suele citar.

En la biblioteca. La versión de libstdc++ es la de CLRS, con dos cambios. El que importa aquí: cuando la clave tiene dos hijos, no copia al sucesor, sino que enlaza su nodo en el lugar del borrado. Por eso std::map::erase solo invalida los iteradores del elemento borrado, como vimos en la semana 10. El propio comentario de stl_tree.h lo explica.

AVL, rojinegro y std::map, medidos

Es hora de los números. Lo que se suele decir es: “AVL es más bajo, y rojinegro hace menos rotaciones”. Veamos cuánto, y cuándo.

Altura

height_table inserta las mismas claves en los dos árboles. avl y rn son las alturas, negros la altura negra del rojinegro, y prof la profundidad media de un nodo. cota es 2 log₂(n + 1) − 1. Son conteos, y no dependen de la máquina:

$ build/height_table
Claves ordenadas, de menor a mayor
        n  log2n   cota   avl    rn  negros  prof.avl  prof.rn
     1000   10.0   18.9     9    16       9      7.99     8.41
     4000   12.0   22.9    11    20      11      9.98    10.40
    16000   14.0   26.9    13    24      13     11.98    12.39
    64000   16.0   30.9    15    28      15     13.98    14.39
   256000   18.0   34.9    17    32      17     15.98    16.39
  1024000   20.0   38.9    19    36      19     17.98    18.39
Claves al azar, tres semillas
        n  log2n   cota   a1  a2  a3   r1  r2  r3  prof.avl  prof.rn
     1000   10.0   18.9   11  11  11   11  11  12      8.24     8.28
     4000   12.0   22.9   13  13  13   13  14  13     10.22    10.28
    16000   14.0   26.9   16  16  16   16  16  16     12.26    12.33
    64000   16.0   30.9   18  18  18   19  18  19     14.29    14.35
   256000   18.0   34.9   20  21  21   21  21  21     16.31    16.40
  1024000   20.0   38.9   23  23  23   23  24  23     18.36    18.41

Dos resultados muy distintos:

• Claves al azar: empate. La altura difiere en 1 como máximo, y a veces son iguales. La profundidad media del rojinegro es menos de 1% mayor. “AVL es más bajo” es cierto, por muy poco.
• Claves ordenadas: casi el doble. El AVL queda en ⌊log₂ n⌋, el mínimo posible. El rojinegro llega a 36 con un millón de claves, cerca de su cota de 38.9, y en estas filas da unas 2 log₂ n − 4. El orden que resultó el mejor para AVL está cerca del límite de lo que la cota permite al rojinegro. Lean lo que eso significa: al insertar en orden, una rama queda negra y roja por turnos.

Pero miren la profundidad media en esa misma tabla: 17.98 contra 18.39, un 2% más. El camino más largo casi se duplica, y el camino típico no. La mayoría de los nodos está lejos de esa rama larga. Es buena idea no confundir la altura, que es el peor caso, con el costo de una búsqueda típica.

Rotaciones y recoloreos

count_table cuenta por inserción. max.rot y max.rec son lo máximo que hizo el rojinegro en una sola inserción, y el recoloreo es una vez el caso del tío rojo, que pinta 3 nodos:

$ build/count_table
     claves        n  rot.avl   rot.rn recol.rn  max.rot  max.rec
 crecientes     1000    0.990    0.983    0.978        1        8
decrecientes     1000    0.990    0.983    0.978        1        8
       azar     1000    0.702    0.583    0.506        2        5
 crecientes    32000    1.000    0.999    0.999        1       13
decrecientes    32000    1.000    0.999    0.999        1       13
       azar    32000    0.701    0.587    0.511        2        9
 crecientes  1024000    1.000    1.000    1.000        1       18
decrecientes  1024000    1.000    1.000    1.000        1       18
       azar  1024000    0.697    0.582    0.513        2       11

• Con claves al azar, el rojinegro hace menos rotaciones: 0.58 frente a 0.70 por inserción, unas 17% menos.
• Con claves ordenadas, empate: 1.000 y 1.000, por inserción, con un millón de claves. En palabras, unas 17 rotaciones de diferencia sobre un millón de inserciones, como ven en la tabla de palabras.txt de más abajo. El rojinegro, en orden, también rota casi en cada inserción, y además recolorea casi en cada una.
• max.rot nunca pasó de 2, y max.rec llegó a 18, la mitad de la altura de ese árbol. Son medidas con una semilla fija, y no teoremas; lo que está demostrado es el límite de arriba.

Por lo tanto, “rojinegro hace menos rotaciones al insertar” es cierto con claves al azar, y no con claves ordenadas. Y una rotación es muy barata, unas pocas asignaciones de punteros. No va a ser eso lo que decida el reloj.

El reloj

make bench-times del laboratorio mide los tres mapas, con claves int: el AvlMap de la semana pasada, el RedBlackMap de esta semana, y std::map. Se compila con -O2 y sin sanitizers, y ins incluye destruir el mapa, igual para los tres. Los tiempos dependen de la máquina, que es una laptop arm64. Cada mapa y cada n corren en su propio proceso, y cada tiempo es la mediana de 7 repeticiones. Las dos cosas vienen de errores nuestros. Esta es una corrida de AVL con un millón de claves en orden, con el tiempo de cada repetición y sus fallos de página, es decir, las veces que el programa tocó memoria nueva por primera vez:

0.264 s (12 mil fallos)   0.107 (0)   0.073 (0)   0.066 (0)   0.065 (0)   0.065 (0)   0.065 (0)

La primera repetición paga la memoria nueva. La segunda sigue cara, sin fallos de página, y no sabemos por qué. Después se estabiliza. Con la mediana de 3 de nuestra primera versión, el resultado era justo esa segunda repetición, 0.11 s, y nos hizo creer que el rojinegro le ganaba a AVL casi por el doble. Con 7, la mediana cae donde ya se estabilizó. Es una trampa fácil de pisar: si un resultado cambia según el orden o el número de repeticiones, desconfíen de la conclusión.

$ make --no-print-directory LAB_DIR=solution bench-times
avl
        n ins.orden bus.orden  ins.azar  bus.azar
    16000    0.0007    0.0014    0.0025    0.0012
    64000    0.0033    0.0086    0.0144    0.0089
   256000    0.0146    0.0514    0.0765    0.0514
  1024000    0.0695    0.4802    0.9906    0.7676
rn
        n ins.orden bus.orden  ins.azar  bus.azar
    16000    0.0006    0.0012    0.0021    0.0014
    64000    0.0026    0.0081    0.0123    0.0090
   256000    0.0117    0.0483    0.0644    0.0526
  1024000    0.0560    0.4569    0.8611    0.7604
std
        n ins.orden bus.orden  ins.azar  bus.azar
    16000    0.0009    0.0017    0.0017    0.0016
    64000    0.0058    0.0119    0.0099    0.0098
   256000    0.0382    0.0641    0.0464    0.0554
  1024000    0.2345    0.6758    0.5561    0.9037

Lo corrimos 3 veces. Esto es lo que se repitió en las 3, y lo que no:

Buscar: AVL y rojinegro empatan, incluso con claves ordenadas. Con un millón de claves ordenadas, 0.47 a 0.48 s para AVL, y 0.46 a 0.47 s para rojinegro, aunque uno mida 19 y el otro 36. Tiene sentido con la tabla de altura: la profundidad media difiere en un 2%. “AVL es más bajo” no se convirtió en búsquedas más rápidas, en ningún orden que hayamos medido. Con claves al azar, cuál gana depende de la corrida. std::map busca más lento que los dos: unas 1.4 veces con claves ordenadas y entre 1.1 y 1.2 con claves al azar, en la última fila.

Insertar con claves al azar: std::map gana con claridad. Entre 0.53 y 0.56 s con un millón de claves, frente a entre 0.86 y 0.89 para nuestro rojinegro, y entre 0.95 y 1.01 para AVL.

Insertar con claves ordenadas: gana nuestro rojinegro, entre 0.055 y 0.057 s, frente a entre 0.066 y 0.070 para AVL y unos 0.23 para std::map.

Ahora, los motivos, porque los números no explican nada solos. No tenemos perf aquí, y por eso cada explicación se comprobó cambiando una sola cosa en el código, 3 veces.

¿Por qué std::map inserta tan rápido con claves al azar, si es el mismo árbol? La bajada de nuestro insert_node, que viene de la semana 10, hace dos comparaciones por nivel: key < node->key, y si no, node->key < key. La de std::map hace una, y se fija si la clave es repetida solo al final. Cambiamos nuestra bajada para que haga lo mismo, y con un millón de claves al azar nuestro rojinegro bajó de entre 0.84 y 0.88 s a 0.52 o 0.53 s, frente a entre 0.54 y 0.56 s de std::map. La diferencia no estaba en el árbol: estaba en una comparación. Con claves al azar, es probable que esa segunda comparación además sea difícil de predecir para el procesador, pero eso no lo medimos.

¿Por qué nuestro rojinegro le gana a AVL? La respuesta fácil es “menos rotaciones”. No lo comprobamos así. Nuestro AvlMap sube siempre hasta la raíz, actualizando alturas, y el RedBlackMap se detiene en cuanto el padre es negro. Es el ejercicio 8 de la semana pasada. Le agregamos a AvlMap esa parada temprana. Con claves ordenadas pasó de unos 0.07 a 0.038 s, y le ganó al rojinegro, que estaba en unos 0.06: la ventaja se dio vuelta. Con claves al azar, el AVL pasó de cerca de 1.0 a unos 0.94 s, y el rojinegro siguió delante, con entre 0.84 y 0.88. Por lo tanto, buena parte de la ventaja de tiempo de nuestro rojinegro al insertar viene de cómo está escrito nuestro AVL, y no de la estructura.

¿Por qué std::map es casi 4 veces más lento que nuestro rojinegro con claves ordenadas? No lo sabemos del todo. Las repeticiones dan una pista. Nuestros mapas bajan a unos 0.06 s una vez que el proceso ya tiene memoria, y std::map se queda en unos 0.23 s, repetición tras repetición. Si corre justo después de nuestro rojinegro, en el mismo proceso, su primera repetición tarda solo 0.09 s, sin pedir memoria nueva, y las siguientes vuelven a estar cerca de 0.2. Es probable que destruya sus nodos en otro orden, y que los bloques libres queden dispersos para la repetición siguiente, como en las listas barajadas de la semana 5. No medimos dónde quedan los nodos. Nuestro experimento con una sola comparación también hizo más lento el caso ordenado, de unos 0.06 a 0.11 s, y eso podría explicar otra parte.

Entonces, ¿qué elegir?

En esta biblioteca, además, std::map es un rojinegro. El estándar de C++ no exige eso.

En la biblioteca. El estándar de C++ no nombra ningún árbol: pide que buscar, insertar y borrar una clave cuesten O(log n), que el recorrido salga ordenado, y que insertar no invalide iteradores ni referencias. Que sea un rojinegro es decisión de cada biblioteca. En la del curso, libstdc++ 14, se puede leer. En bits/stl_tree.h, al comienzo: “Red-black tree class, designed for use in implementing STL associative containers”, y que los algoritmos “are based on those in Cormen, Leiserson, and Rivest”. Ahí está también el nodo, con su _M_color, _M_parent, _M_left y _M_right, y en bits/stl_map.h se ve que std::map guarda uno de esos árboles, como _Rep_type. El código de la reparación está compilado en la biblioteca, y no en el encabezado, de modo que eso sí no lo vimos. std::map no tiene ninguna función que entregue su altura: por eso, en estas tablas, la altura es solo de los dos árboles propios.

El código de la semana

En code/week-12:

rb_trace les sirve para revisar cualquier ejercicio: cada argumento es una clave. make compila, y make test lo comprueba todo: vuelve a correr los comandos de este capítulo, y compara todo lo que se puede contar.

El laboratorio

Sesión 1: la inserción. lab/red_black_map.h trae RedBlackMap<K, V>: el mapa de búsqueda de las semanas anteriores, completo y funcionando, con find, los iteradores y la regla de los cinco, sin erase, y con color en cada nodo. Lo que falta es lo propio de esta semana.

make test-base       # el mapa de partida: pasa desde el inicio
make test-rotations  # paso 1: sus rotaciones
make test-check      # paso 2: check_invariants, con árboles sanos y rotos
make test-insert     # paso 3: la inserción, contra std::map
make test-measure    # paso 5: lo que mide
make test-lab        # todo
make bench-counts    # paso 4
make bench-times     # paso 5
make bench-words     # paso 5

Paso 1: rotaciones (unos 5 minutos). Copien rotate_left y rotate_right de su avl_map.h de la semana 11, sin cambiar nada. Si las escribieron como se pidió, no tocan las alturas, y por eso compilan aquí. Las pruebas rotan a mano, y comprueban que un nodo rojo siga siendo rojo después de rotar. Si la semana pasada no llegaron a terminarlas, las tienen en lab/avl_map.h, de la próxima sección.

Paso 2: check_invariants (unos 35 minutos). Escríbanlo antes que la inserción, con una función auxiliar recursiva, y comprueben con make test-check que detecta los árboles rotos. Las pruebas broken_* arman árboles a mano, sin pasar por insert, así que funcionan aunque la inserción no exista todavía. Son 17 árboles, y cada uno rompe una sola cosa. Revisen la prueba si no entienden uno.

Paso 3: insertar (unos 60 minutos). Escriban fix_insert a partir del pseudocódigo de reparar_insercion, y llámenlo en insert_node, no en insert, para que operator[] también repare. recolors_ suma 1 por cada vuelta con tío rojo, y nada más. Las pruebas comparan las formas exactas, también contra RedBlackSet, en todos los órdenes de hasta 7 claves. Si difieren, rb_trace les da la forma correcta y el paso en que se separan. Por último, prueban al azar contra std::map.

Sesión 2: medir. lab/avl_map.h es el mapa AVL de la semana 11 ya terminado, para que todos midan contra el mismo. Solo se compila: no tienen que tocarlo. Si prefieren medir el suyo, cámbienlo por el suyo.

Paso 4: contar (unos 15 minutos). make bench-counts viene hecho.

Paso 5: medir (unos 45 minutos). Escriban time_inserts y time_finds en lab/measure.h, con el median_seconds de siempre. put y has ya vienen, y dejan usar los tres mapas igual. make test-measure comprueba que hacen el trabajo que dicen, contando llamadas, y no mirando el reloj. Corran make bench-times 3 veces, y make bench-words.

Paso 6: la conclusión (unos 60 minutos). Escriban lab/report.md: qué estructura elegirían para muchas lecturas, cuál para muchas escrituras, y cuándo no vale la pena dejar std::map, con sus números. Si sus números no permiten decidir, escribir eso es una buena conclusión. Si quieren ir más allá, prueben a cambiar una sola cosa, como hicimos aquí.

Resumen

• Un árbol 2-3-4 tiene nodos con 1 a 3 claves, y todas sus hojas a la misma profundidad. Por eso, sus niveles son como máximo log₂(n + 1).
• Al insertar, una clave entra en una hoja que ya existe. Si está llena, se divide: la del medio de sus 3 claves sube al padre. El árbol solo crece al dividir la raíz.
• Un B-tree es la misma idea con nodos enormes, para leer pocas páginas de disco. Con 1000 claves por nodo, mil millones de claves caben en 3 niveles. Bases de Datos los construye.
• Un árbol rojinegro escribe cada nodo 2-3-4 como un negro con hijos rojos. El nodo de 3 claves tiene una sola forma, y el de 2 claves tiene dos, ambas válidas en el árbol clásico. Open Data Structures usa una variante inclinada a la izquierda, con una sola forma. No hay que mezclarlas.
• Un rojinegro colapsa a un árbol 2-3-4. Un árbol 2-3-4 con t nodos de 2 claves viene de 2^t rojinegros, y no todos se obtienen insertando.
• Cinco propiedades: rojo o negro; raíz negra; hojas nulas negras; un rojo solo tiene hijos negros; desde cada nodo, misma cantidad de negros hasta sus hojas nulas.
• La altura: colapsar da b ≤ log₂(n + 1), y un camino tiene como máximo 2b nodos. Por lo tanto, h ≤ 2b − 1 ≤ 2 log₂(n + 1) − 1, contando aristas. La constante 2 no se puede bajar.
• El nodo nuevo es rojo, porque eso rompe algo local, y equivale a entrar en un nodo que ya existe.
• Padre negro: nada. Tío negro: un nodo de 2 claves pasa a 3, y se arregla la forma con 1 rotación en línea y 2 en zigzag. Tío rojo: un nodo lleno se divide, solo con colores, y el problema sube. Raíz roja al final: se pinta de negro, y el árbol 2-3-4 gana un nivel.
• Una inserción hace como máximo 2 rotaciones, porque después de rotar el ciclo termina, y hasta ⌊h/2⌋ recoloreos.
• La inserción clásica calza exactamente con un árbol 2-3-4 que se divide solo al hacer overflow, y sube la del medio de las 3. Se comprobó en todos los órdenes de hasta 9 claves. Con otras reglas, no calza.
• ✂️ Borrar es fusión o préstamo en el árbol 2-3-4. Tiene 4 casos y sus espejos, porque hay dos formas de nodo de 2 claves. Hace como máximo 3 rotaciones.
• Medido: con claves al azar, AVL y rojinegro casi empatan en altura; con claves ordenadas, 19 contra 36, pero la profundidad media difiere en 2%. El rojinegro rota 17% menos con claves al azar, y empata con claves ordenadas. Buscar empató. Insertar dependió más de cómo está escrito cada mapa que del árbol: std::map, con una comparación por nivel, ganó con claves al azar.
• std::map es rojinegro en libstdc++. El estándar no lo exige. Para casi todo programa, no vale la pena dejarlo.

Ejercicios

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

1. Dibujen el árbol 2-3-4 [4]([2],[6 8]) como un árbol rojinegro. ¿De cuántas formas se puede? Escriban todas en el formato de rb_trace. Hagan lo mismo con [5 9]([1 3],[7],[11 13 15]), sin dibujarlas todas: ¿cuántas son?
2. Digan si estos árboles son rojinegros válidos. Si no, digan qué propiedad se rompe y en qué nodo: 10(5r,15r), 10r(5,15), 10(5,15r), 10(5r(3r,_),15r), 20(10r(5,15),30), 20(10r(5,15),30r(25,35)).
3. Inserten 41, 38, 31, 12, 19, 8 en un árbol rojinegro vacío, a mano. Por cada una, digan qué caso se aplica y cómo queda el árbol 2-3-4.
4. Inserten las mismas claves en un árbol 2-3-4, a mano, dividiendo al hacer overflow. Comparen con build/tree_234_trace. Comparen también con su colapso del ejercicio 3.
5. Encuentren un orden de inserción de las claves 1 a 5 que dé 4(2(1r,3r),5). Luego, con las claves 1, 2 y 3, expliquen por qué ningún orden da 2(1,3), que es un árbol válido.
6. ¿Por qué un árbol rojinegro con n ≥ 2 no puede tener todos sus nodos rojos salvo la raíz, si tiene altura 2? ¿Cuántos rojos puede tener, como máximo, un árbol de altura negra b? Den el árbol, y comprueben con check_invariants.
7. En el ejemplo de collapse_check, en el que [1 3 4] recibe el 2, expliquen por qué subir la segunda de las cuatro claves, el 2, no se puede lograr con colores y sin rotaciones. ¿Qué tendría que pasar en el árbol rojinegro?
8. Con collapse_check como modelo, busquen el primer orden de 10 claves en el que un árbol 2-3-4 con división al bajar tiene menos divisiones que uno con división al hacer overflow. ¿Existe? Si no encuentran uno, digan hasta dónde buscaron, y por qué eso no prueba que no exista.
9. ¿Cuál es la menor cantidad de nodos de un árbol rojinegro de altura 5? Dibújenlo, a partir de build/height_bound. ¿Se puede obtener insertando? Con las claves 1 a 14, prueben órdenes al azar con un programa, y digan cuántos probaron.
10. Cambien la bajada de insert_node para que haga una sola comparación por nivel, como std::map, sin dejar de detectar las claves repetidas. Corran make test-lab y make bench-times 3 veces. ¿Cuánto cambia con claves al azar? ¿Y con claves ordenadas?
11. Sobre lab/avl_map.h, agreguen la parada temprana del ejercicio 8 de la semana 11. Midan los dos AVL contra RedBlackMap, cada uno en su propio proceso. ¿Cambia su conclusión del informe?
12. ✂️ Sobre el árbol 20(10(5r,15r),30), describan qué tendría que pasar al borrar el 30: ¿qué ve el árbol 2-3-4? ¿Fusión o préstamo? ¿Cuántas rotaciones? Hagan el dibujo, sin programarlo.