Semana 12 — Árboles rojinegros
Objetivos
- Explicar un árbol rojinegro como una forma de representar un árbol 2-3-4.
- Enunciar sus propiedades y deducir de ellas el límite de altura.
- Implementar la inserción y comprobar las propiedades en las pruebas.
- Decidir con mediciones entre AVL, rojinegro y la biblioteca.
Teoría — Árboles rojinegros: de los árboles 2-3-4 a la inserción · B-trees como idea · ✂️ Eliminación
Lectura: Apuntes, semana 12.
Apoyo: Open Data Structures, secs. 9.1 (2-4 Trees) y 9.2 (RedBlackTree); usa la variante inclinada a la izquierda, y este curso usa la clásica. CLRS, capítulo Red-Black Trees, y capítulo B-Trees solo para la idea.
Temas:
- Otra forma de balancear: nodos con más de una clave. Árboles 2-3-4: todas las hojas a la misma profundidad.
- Insertar en un árbol 2-3-4: dividir un nodo lleno, y la clave del medio sube al padre.
- La idea de los B-trees: la misma, con nodos enormes, para no leer tanto del disco. Bases de Datos los construye de verdad.
- Representar un nodo de 3 o 4 hijos con nodos binarios: el nodo negro y sus hijos rojos.
- Las propiedades: cada nodo es rojo o negro; la raíz es negra; las hojas nulas son negras; un rojo solo tiene hijos negros; todo camino desde un nodo hasta sus hojas nulas tiene los mismos negros.
- Altura como máximo 2 log₂(n + 1): colapsar los rojos da un árbol 2-3-4.
- Inserción: el nodo nuevo es rojo, y se repara si su padre es rojo. Tío rojo: se recolorea y el problema sube. Tío negro: se rota, a lo sumo dos veces. Cada caso, con su equivalente en 2-3-4.
- AVL frente a rojinegro: con claves ordenadas, AVL es mucho más bajo; con claves al azar, casi empatan. Rojinegro hace menos rotaciones con claves al azar, y su mayor ventaja está en el peor caso del borrado. La profundidad y el tiempo se miden.
std::mapusa un rojinegro en la biblioteca del curso, aunque el estándar no lo exige. - ✂️ Eliminación: la idea y por qué tiene tantos casos. No se implementa.
- Error común: olvidar pintar la raíz de negro al final de la inserción.
Laboratorio — Inserción rojinegra · AVL, rojinegro y std::map, medidos
Sesión 1:
- Escribir las rotaciones de
RedBlackMap<K, V>, igual que en la semana 11.findse da hecho. - Escribir
check_invariants, que comprueba las cinco propiedades y el orden. Antes de usarlo, comprobar que detecta errores en árboles rotos dados. - Escribir
inserty pasar pruebas de inserción al azar contrastd::map.
Sesión 2:
4. Contar rotaciones y recoloreos en series de inserciones, al azar y ordenadas.
5. Medir el tiempo de inserción y de búsqueda de AVL, rojinegro y std::map, con n creciente, y la altura de los dos propios: std::map no la expone.
6. Escribir una conclusión: qué estructura elegirían para muchas lecturas y cuál para muchas escrituras, y cuándo no vale la pena dejar std::map, con los números obtenidos.
Preguntas de repaso
- Dibujen un nodo 2-3-4 con tres claves como un árbol rojinegro.
- Un nodo rojo tiene un hijo rojo. ¿Qué propiedad se rompe? ¿A qué situación corresponde en un árbol 2-3-4?
- ¿Por qué un camino puede tener como máximo el doble de nodos que otro desde el mismo nodo?
- Inserten 10, 20, 30, 15 y 25 en un árbol rojinegro vacío. Dibujen el árbol y digan qué caso se aplicó en cada paso.
- ¿Por qué se pinta de rojo el nodo nuevo, y no de negro?
- ¿Por qué una base de datos prefiere nodos con muchas claves en vez de un árbol binario?
Código de la semana
Compilar y probar dentro del contenedor del curso con make y make test.
Ejemplos (14)Errores (5)Pruebas (4)Laboratorio (8)Compilación (1)
Ejemplos
Los programas que usan los apuntes y la clase.
// Prueba todos los órdenes de inserción de n claves, y anota lo peor que pasó en una inserción.
// También revisa los dos lados de la cota: n >= 2^negros - 1, y altura + 1 <= 2 * negros.
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>
#include "rb_set.h"
int main() {
std::cout << std::setw(3) << "n" << std::setw(8) << "ordenes" << std::setw(7) << "h.min" << std::setw(7) << "h.max"
<< std::setw(6) << "cota" << std::setw(16) << "max.rotaciones" << std::setw(16) << "max.recoloreos"
<< std::setw(9) << "cuentas" << "\n";
for (int n = 1; n <= 9; n++) {
std::vector<int> keys(n);
std::iota(keys.begin(), keys.end(), 1);
long orders = 0;
int min_height = n;
int max_height = -1;
long max_rotations = 0;
long max_recolors = 0;
bool counts_hold = true;
do {
RedBlackSet<int> tree;
for (int key : keys) {
long rotations = tree.rotations();
long recolors = tree.recolors();
tree.insert(key);
max_rotations = std::max(max_rotations, tree.rotations() - rotations);
max_recolors = std::max(max_recolors, tree.recolors() - recolors);
}
int blacks = tree.black_height();
counts_hold = counts_hold && n >= (1 << blacks) - 1 && tree.height() + 1 <= 2 * blacks;
min_height = std::min(min_height, tree.height());
max_height = std::max(max_height, tree.height());
orders++;
} while (std::next_permutation(keys.begin(), keys.end()));
std::cout << std::setw(3) << n << std::setw(8) << orders << std::setw(7) << min_height << std::setw(7) << max_height
<< std::fixed << std::setprecision(2) << std::setw(6) << 2 * std::log2(n + 1.0) - 1
<< std::setw(16) << max_rotations << std::setw(16) << max_recolors
<< std::setw(9) << (counts_hold ? "si" : "NO") << "\n";
}
return 0;
}// Genera TODOS los árboles rojinegros válidos con las claves 1..n, y los colapsa.
// Comprueba que cada árbol 2-3-4 con t nodos de 2 claves viene de exactamente 2^t rojinegros,
// y cuenta cuántos de esos rojinegros se pueden obtener insertando en algún orden.
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <set>
#include <string>
#include <vector>
#include "rb_set.h"
namespace {
struct Shape {
int key = 0;
bool red = false;
std::shared_ptr<const Shape> left;
std::shared_ptr<const Shape> right;
};
using Tree = std::shared_ptr<const Shape>;
bool is_red(const Tree& tree) { return tree != nullptr && tree->red; }
std::string text_of(const Tree& tree) {
if (tree == nullptr) {
return "_";
}
std::string text = std::to_string(tree->key) + (tree->red ? "r" : "");
if (tree->left != nullptr || tree->right != nullptr) {
text += "(" + text_of(tree->left) + "," + text_of(tree->right) + ")";
}
return text;
}
// Devuelve el texto de RedBlackSet::collapsed, y cuenta los nodos de 2 claves.
std::string collapse(const Tree& tree, int& two_keys) {
if (tree == nullptr) {
return "_";
}
std::vector<Tree> keys;
std::vector<Tree> children;
if (is_red(tree->left)) {
keys.push_back(tree->left);
children.push_back(tree->left->left);
children.push_back(tree->left->right);
} else {
children.push_back(tree->left);
}
keys.push_back(tree);
if (is_red(tree->right)) {
keys.push_back(tree->right);
children.push_back(tree->right->left);
children.push_back(tree->right->right);
} else {
children.push_back(tree->right);
}
two_keys += keys.size() == 2 ? 1 : 0;
std::string text = "[";
for (std::size_t i = 0; i < keys.size(); i++) {
text += (i > 0 ? " " : "") + std::to_string(keys[i]->key);
}
text += "]";
if (children[0] != nullptr) {
text += "(";
for (std::size_t i = 0; i < children.size(); i++) {
text += (i > 0 ? "," : "") + collapse(children[i], two_keys);
}
text += ")";
}
return text;
}
int height_of(const Tree& tree) {
return tree == nullptr ? -1 : 1 + std::max(height_of(tree->left), height_of(tree->right));
}
// Todos los árboles válidos con las claves low..high, con esa cantidad de negros hasta las hojas
// nulas, cuya raíz es negra, o cualquiera de los dos colores si may_be_red.
std::vector<Tree> build_all(int low, int high, int blacks, bool may_be_red) {
std::vector<Tree> trees;
if (low > high) {
if (blacks == 0) {
trees.push_back(nullptr);
}
return trees;
}
if (blacks < 0) {
return trees;
}
for (int key = low; key <= high; key++) {
if (blacks >= 1) {
for (const Tree& left : build_all(low, key - 1, blacks - 1, true)) {
for (const Tree& right : build_all(key + 1, high, blacks - 1, true)) {
trees.push_back(std::make_shared<const Shape>(Shape{key, false, left, right}));
}
}
}
if (may_be_red) {
for (const Tree& left : build_all(low, key - 1, blacks, false)) {
for (const Tree& right : build_all(key + 1, high, blacks, false)) {
trees.push_back(std::make_shared<const Shape>(Shape{key, true, left, right}));
}
}
}
}
return trees;
}
} // namespace
int main() {
std::cout << std::setw(3) << "n" << std::setw(11) << "rojinegros" << std::setw(7) << "2-3-4" << std::setw(10) << "suma.2^t"
<< std::setw(13) << "alcanzables" << std::setw(8) << "h.todos" << std::setw(7) << "h.ins" << std::setw(7) << "cota" << "\n";
for (int n = 1; n <= 9; n++) {
std::map<std::string, long> trees_of_group;
std::map<std::string, int> two_keys_of_group;
std::set<std::string> valid;
int max_height = 0;
for (int blacks = 1; (1 << (blacks - 1)) - 1 <= n; blacks++) {
for (const Tree& tree : build_all(1, n, blacks, false)) {
int two_keys = 0;
std::string group = collapse(tree, two_keys);
trees_of_group[group]++;
two_keys_of_group[group] = two_keys;
valid.insert(text_of(tree));
max_height = std::max(max_height, height_of(tree));
}
}
long total = 0;
for (const auto& [group, count] : trees_of_group) {
if (count != 1L << two_keys_of_group[group]) {
std::cout << "no calza 2^t en " << group << "\n";
return 1;
}
total += 1L << two_keys_of_group[group];
}
std::set<std::string> reachable;
int max_inserted = 0;
std::vector<int> keys(n);
std::iota(keys.begin(), keys.end(), 1);
do {
RedBlackSet<int> tree;
for (int key : keys) {
tree.insert(key);
}
reachable.insert(tree.shape());
max_inserted = std::max(max_inserted, tree.height());
} while (std::next_permutation(keys.begin(), keys.end()));
for (const std::string& shape : reachable) {
if (valid.count(shape) == 0) {
std::cout << "insertar dio un arbol no valido: " << shape << "\n";
return 1;
}
}
std::cout << std::setw(3) << n << std::setw(11) << valid.size() << std::setw(7) << trees_of_group.size()
<< std::setw(10) << total << std::setw(13) << reachable.size() << std::setw(8) << max_height
<< std::setw(7) << max_inserted << std::fixed << std::setprecision(2) << std::setw(7)
<< 2 * std::log2(n + 1.0) - 1 << "\n";
}
return 0;
}// Árbol AVL sin valores: el conjunto de claves de los apuntes.
// Es recursivo y no tiene puntero al padre: la vuelta de la recursión es la subida hacia la raíz.
// El laboratorio construye un mapa con puntero al padre, sobre el BstMap de la semana 10.
#ifndef AVL_SET_H
#define AVL_SET_H
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdlib>
#include <sstream>
#include <string>
#include <vector>
// Invariantes:
// - 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.
//
// K solo necesita operator<, y se copia al borrar una clave con dos hijos.
// La recursión es segura aquí: gasta pila proporcional a la altura, y la altura es O(log n).
template <typename K>
class AvlSet {
struct Node {
K key;
Node* left = nullptr;
Node* right = nullptr;
int height = 0;
};
friend struct AvlSetAccess;
public:
// Una reparación: en qué clave estaba el nodo desbalanceado, y qué caso fue.
struct Repair {
K key;
std::string kind;
};
AvlSet() = default;
~AvlSet() { destroy(root_); }
// Este conjunto es para estudiar las operaciones: no se copia ni se mueve.
AvlSet(const AvlSet&) = delete;
AvlSet& operator=(const AvlSet&) = delete;
std::size_t size() const { return size_; }
bool empty() const { return size_ == 0; }
bool contains(const K& key) const {
const Node* node = root_;
while (node != nullptr) {
if (key < node->key) {
node = node->left;
} else if (node->key < key) {
node = node->right;
} else {
return true;
}
}
return false;
}
// Devuelve false si la clave ya estaba.
bool insert(const K& key) {
last_repairs_.clear();
bool added = false;
root_ = insert_at(root_, key, added);
if (added) {
size_++;
}
return added;
}
// Devuelve false si la clave no estaba.
bool erase(const K& key) {
last_repairs_.clear();
bool erased = false;
root_ = erase_at(root_, key, erased);
if (erased) {
size_--;
}
return erased;
}
int height() const { return height_of(root_); }
// Las reparaciones que hizo la última operación, de abajo hacia arriba.
const std::vector<Repair>& last_repairs() const { return last_repairs_; }
// Rotaciones desde que se creó: una reparación doble cuenta como dos.
long rotations() const { return rotations_; }
// La suma de las profundidades de todos los nodos.
long total_depth() const { return depth_sum(root_, 0); }
std::vector<K> in_order() const {
std::vector<K> keys;
walk_in(root_, keys);
return keys;
}
// El árbol en una línea: clave(izquierdo,derecho), con _ si falta un hijo.
std::string shape() const {
std::ostringstream out;
write_shape(root_, out);
return out.str();
}
void check_invariants() const {
assert((root_ == nullptr) == (size_ == 0));
assert(count_checked(root_, nullptr, nullptr) == size_);
}
private:
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); }
// 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;
}
// Sube al hijo izquierdo de x, y devuelve la nueva raíz del subárbol. Solo cambia enlaces.
Node* rotate_right(Node* x) {
Node* y = x->left;
x->left = y->right;
y->right = x;
rotations_++;
return y;
}
// Actualiza la altura de node, lo repara si hace falta, y devuelve la raíz de su subárbol.
// Los dos hijos de node ya tienen su altura correcta.
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;
}
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;
}
Node* repair_right_heavy(Node* x) {
Node* y = x->right;
if (balance_of(y) > 0) {
last_repairs_.push_back({x->key, "derecha-izquierda"});
x->right = rotate_right(y);
update_height(y);
update_height(x->right);
} else {
last_repairs_.push_back({x->key, "derecha-derecha"});
}
Node* top = rotate_left(x);
update_height(x);
update_height(top);
return top;
}
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* erase_at(Node* node, const K& key, bool& erased) {
if (node == nullptr) {
return nullptr;
}
if (key < node->key) {
node->left = erase_at(node->left, key, erased);
} else if (node->key < key) {
node->right = erase_at(node->right, key, erased);
} else {
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);
}
return rebalance(node);
}
static void destroy(Node* node) {
if (node == nullptr) {
return;
}
destroy(node->left);
destroy(node->right);
delete node;
}
static long depth_sum(const Node* node, long depth) {
if (node == nullptr) {
return 0;
}
return depth + depth_sum(node->left, depth + 1) + depth_sum(node->right, depth + 1);
}
static void walk_in(const Node* node, std::vector<K>& keys) {
if (node == nullptr) {
return;
}
walk_in(node->left, keys);
keys.push_back(node->key);
walk_in(node->right, keys);
}
static void write_shape(const Node* node, std::ostringstream& out) {
if (node == nullptr) {
out << "_";
return;
}
out << node->key;
if (node->left != nullptr || node->right != nullptr) {
out << "(";
write_shape(node->left, out);
out << ",";
write_shape(node->right, out);
out << ")";
}
}
// Cuenta los nodos, y comprueba el orden, cada altura guardada y la condición AVL.
static std::size_t count_checked(const Node* node, const K* low, const K* high) {
if (node == nullptr) {
return 0;
}
assert(low == nullptr || *low < node->key);
assert(high == nullptr || node->key < *high);
std::size_t count = 1 + count_checked(node->left, low, &node->key)
+ count_checked(node->right, &node->key, high);
assert(node->height == 1 + std::max(height_of(node->left), height_of(node->right)));
assert(std::abs(balance_of(node)) <= 1);
return count;
}
Node* root_ = nullptr;
std::size_t size_ = 0;
long rotations_ = 0;
std::vector<Repair> last_repairs_;
};
#endif// Medidor de tiempos del curso. Compilar con -O2 y sin sanitizers.
#ifndef BENCH_H
#define BENCH_H
#include <algorithm>
#include <chrono>
#include <vector>
// Corre fn `reps` veces y devuelve la mediana en segundos.
template <typename Fn>
double median_seconds(int reps, Fn fn) {
std::vector<double> times;
times.reserve(reps);
for (int i = 0; i < reps; i++) {
auto start = std::chrono::steady_clock::now();
fn();
auto stop = std::chrono::steady_clock::now();
times.push_back(std::chrono::duration<double>(stop - start).count());
}
std::sort(times.begin(), times.end());
return times[times.size() / 2];
}
// Evita que el compilador borre un cálculo cuyo resultado no se usa.
template <typename T>
void keep(const T& value) {
volatile T sink = value;
(void)sink;
}
#endif// Cuántos niveles necesita un árbol con mil millones de claves, según las claves por nodo.
// Es el mejor caso: todos los nodos llenos. Con m claves por nodo, L niveles guardan (m + 1)^L - 1.
#include <iomanip>
#include <iostream>
int main() {
const long long keys = 1000000000;
std::cout << std::setw(16) << "claves.por.nodo" << std::setw(9) << "niveles" << "\n";
for (long long per_node : {1LL, 3LL, 15LL, 100LL, 500LL, 1000LL}) {
long long room = 0;
int levels = 0;
while (room < keys) {
room = room * (per_node + 1) + per_node;
levels++;
}
std::cout << std::setw(16) << per_node << std::setw(9) << levels << "\n";
}
return 0;
}// Compara un árbol rojinegro colapsado con un árbol 2-3-4 armado con las mismas claves.
// Para cada orden de inserción y cada política de división, compara la forma completa:
// las claves de cada nodo y el orden de sus hijos.
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <string>
#include <vector>
#include "rb_set.h"
#include "tree_234.h"
namespace {
struct Policy {
const char* name;
SplitPolicy value;
std::vector<int> first_difference;
};
// Compara al final, y también revisa las cuentas de la política que debe calzar.
bool same_shape(const std::vector<int>& keys, SplitPolicy policy) {
RedBlackSet<int> red_black;
Tree234<int> tree(policy);
for (int key : keys) {
red_black.insert(key);
tree.insert(key);
}
return red_black.collapsed() == tree.shape();
}
// Tras cada inserción: la misma forma, tantas divisiones como recoloreos, y tantos niveles como negros.
bool matches_step_by_step(const std::vector<int>& keys) {
RedBlackSet<int> red_black;
Tree234<int> tree(SplitPolicy::old_middle);
for (int key : keys) {
red_black.insert(key);
tree.insert(key);
if (red_black.collapsed() != tree.shape() || red_black.recolors() != tree.splits()
|| red_black.black_height() != tree.levels()) {
return false;
}
}
return true;
}
void print_keys(const std::vector<int>& keys) {
for (std::size_t i = 0; i < keys.size(); i++) {
std::cout << (i > 0 ? " " : "") << keys[i];
}
}
} // namespace
int main() {
std::vector<Policy> policies = {
{"al hacer overflow, sube la del medio de las 3", SplitPolicy::old_middle, {}},
{"al hacer overflow, sube siempre la segunda de las 4", SplitPolicy::fixed_second, {}},
{"al bajar, se divide todo nodo lleno", SplitPolicy::top_down, {}},
};
std::cout << std::setw(3) << "n" << std::setw(8) << "ordenes" << std::setw(9) << "medio" << std::setw(9) << "segunda"
<< std::setw(9) << "al.bajar" << "\n";
for (int n = 1; n <= 9; n++) {
std::vector<int> keys(n);
std::iota(keys.begin(), keys.end(), 1);
long orders = 0;
std::vector<long> different(policies.size(), 0);
do {
orders++;
for (std::size_t p = 0; p < policies.size(); p++) {
if (!same_shape(keys, policies[p].value)) {
different[p]++;
if (policies[p].first_difference.empty()) {
policies[p].first_difference = keys;
}
}
}
if (n <= 8 && !matches_step_by_step(keys)) {
std::cout << "no calza paso a paso\n";
return 1;
}
} while (std::next_permutation(keys.begin(), keys.end()));
std::cout << std::setw(3) << n << std::setw(8) << orders;
for (long count : different) {
std::cout << std::setw(9) << count;
}
std::cout << "\n";
}
std::cout << "Primer orden en que no calza\n";
for (const Policy& policy : policies) {
std::cout << " " << policy.name << ": ";
if (policy.first_difference.empty()) {
std::cout << "ninguno\n";
continue;
}
print_keys(policy.first_difference);
std::cout << "\n";
RedBlackSet<int> red_black;
Tree234<int> tree(policy.value);
for (int key : policy.first_difference) {
red_black.insert(key);
tree.insert(key);
}
std::cout << " rojinegro: " << red_black.collapsed() << "\n";
std::cout << " 2-3-4: " << tree.shape() << "\n";
}
std::cout << "Claves al azar, tres semillas, comparando tras cada insercion\n";
for (unsigned seed : {12u, 13u, 14u}) {
std::vector<int> keys(3000);
std::iota(keys.begin(), keys.end(), 0);
std::mt19937 random(seed);
std::shuffle(keys.begin(), keys.end(), random);
std::cout << " semilla " << seed << ": " << (matches_step_by_step(keys) ? "calza" : "no calza") << "\n";
}
return 0;
}// Rotaciones y recoloreos por inserción, en AVL y en rojinegro. Son conteos, con semilla fija.
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <string>
#include <vector>
#include "avl_set.h"
#include "rb_set.h"
namespace {
void print_row(const std::string& name, const std::vector<int>& keys) {
AvlSet<int> avl;
RedBlackSet<int> rb;
long max_rotations = 0;
long max_recolors = 0;
for (int key : keys) {
avl.insert(key);
long rotations = rb.rotations();
long recolors = rb.recolors();
rb.insert(key);
max_rotations = std::max(max_rotations, rb.rotations() - rotations);
max_recolors = std::max(max_recolors, rb.recolors() - recolors);
}
double n = static_cast<double>(keys.size());
std::cout << std::setw(11) << name << std::setw(9) << keys.size() << std::fixed << std::setprecision(3)
<< std::setw(9) << avl.rotations() / n << std::setw(9) << rb.rotations() / n << std::setw(9) << rb.recolors() / n
<< std::setw(9) << max_rotations << std::setw(9) << max_recolors << "\n";
}
} // namespace
int main() {
std::cout << std::setw(11) << "claves" << std::setw(9) << "n" << std::setw(9) << "rot.avl" << std::setw(9) << "rot.rn"
<< std::setw(9) << "recol.rn" << std::setw(9) << "max.rot" << std::setw(9) << "max.rec" << "\n";
for (int n : {1000, 32000, 1024000}) {
std::vector<int> keys(n);
std::iota(keys.begin(), keys.end(), 0);
print_row("crecientes", keys);
std::reverse(keys.begin(), keys.end());
print_row("decrecientes", keys);
std::mt19937 random(12);
std::shuffle(keys.begin(), keys.end(), random);
print_row("azar", keys);
}
return 0;
}// El rojinegro válido con menos nodos para cada altura: qué tan cerca llega de la cota.
// Se calcula el camino más largo color por color; fuera del camino se cuelgan árboles
// todos negros, que son los que menos nodos gastan para una cantidad de negros dada.
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <tuple>
namespace {
const long impossible = std::numeric_limits<long>::max() / 2;
long all_black(int blacks) { return (1L << blacks) - 1; }
// Quedan `nodes` nodos del camino y `blacks` negros por poner. Devuelve los nodos que hacen falta.
long cheapest(int nodes, int blacks, bool after_red, std::map<std::tuple<int, int, bool>, long>& known) {
if (nodes == 0) {
return blacks == 0 ? 0 : impossible;
}
if (blacks < 0 || blacks > nodes) {
return impossible;
}
auto key = std::make_tuple(nodes, blacks, after_red);
auto found = known.find(key);
if (found != known.end()) {
return found->second;
}
long best = impossible;
if (blacks >= 1) {
long below = cheapest(nodes - 1, blacks - 1, false, known);
best = std::min(best, 1 + all_black(blacks - 1) + below);
}
if (!after_red) {
long below = cheapest(nodes - 1, blacks, true, known);
best = std::min(best, 1 + all_black(blacks) + below);
}
known[key] = best;
return best;
}
// La raíz es negra.
long fewest_nodes(int height, int& blacks_used) {
std::map<std::tuple<int, int, bool>, long> known;
long best = impossible;
for (int blacks = 1; blacks <= height + 1; blacks++) {
long total = 1 + all_black(blacks - 1) + cheapest(height, blacks - 1, false, known);
if (total < best) {
best = total;
blacks_used = blacks;
}
}
return best;
}
} // namespace
int main() {
std::cout << std::setw(3) << "h" << std::setw(11) << "min.nodos" << std::setw(7) << "negros" << std::setw(9) << "cota"
<< std::setw(8) << "h/log2n" << "\n";
for (int h : {0, 1, 2, 3, 4, 5, 6, 8, 10, 12, 16, 20, 24, 32, 40}) {
int blacks = 0;
long n = fewest_nodes(h, blacks);
double bound = 2 * std::log2(n + 1.0) - 1;
std::cout << std::setw(3) << h << std::setw(11) << n << std::setw(7) << blacks << std::fixed << std::setprecision(2)
<< std::setw(9) << bound << std::setw(8) << (n > 1 ? h / std::log2(static_cast<double>(n)) : 0.0) << "\n";
}
return 0;
}// La altura de AVL y de rojinegro, con las mismas claves. Son conteos: no dependen de la máquina.
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>
#include "avl_set.h"
#include "rb_set.h"
namespace {
struct Row {
int avl_height = 0;
int rb_height = 0;
int blacks = 0;
double avl_depth = 0;
double rb_depth = 0;
};
Row measure(const std::vector<int>& keys) {
AvlSet<int> avl;
RedBlackSet<int> rb;
for (int key : keys) {
avl.insert(key);
rb.insert(key);
}
double n = static_cast<double>(keys.size());
return {avl.height(), rb.height(), rb.black_height(), avl.total_depth() / n, rb.total_depth() / n};
}
} // namespace
int main() {
std::cout << "Claves ordenadas, de menor a mayor\n";
std::cout << std::setw(9) << "n" << std::setw(7) << "log2n" << std::setw(7) << "cota" << std::setw(6) << "avl" << std::setw(6) << "rn"
<< std::setw(8) << "negros" << std::setw(10) << "prof.avl" << std::setw(9) << "prof.rn" << "\n";
for (int n = 1000; n <= 1024000; n *= 4) {
std::vector<int> keys(n);
std::iota(keys.begin(), keys.end(), 0);
Row row = measure(keys);
std::cout << std::setw(9) << n << std::fixed << std::setprecision(1) << std::setw(7) << std::log2(n)
<< std::setw(7) << 2 * std::log2(n + 1.0) - 1 << std::setw(6) << row.avl_height << std::setw(6) << row.rb_height
<< std::setw(8) << row.blacks << std::setprecision(2) << std::setw(10) << row.avl_depth << std::setw(9) << row.rb_depth << "\n";
}
std::cout << "Claves al azar, tres semillas\n";
std::cout << std::setw(9) << "n" << std::setw(7) << "log2n" << std::setw(7) << "cota" << std::setw(5) << "a1" << std::setw(4) << "a2" << std::setw(4) << "a3"
<< std::setw(5) << "r1" << std::setw(4) << "r2" << std::setw(4) << "r3" << std::setw(10) << "prof.avl" << std::setw(9) << "prof.rn" << "\n";
for (int n = 1000; n <= 1024000; n *= 4) {
std::vector<int> keys(n);
std::iota(keys.begin(), keys.end(), 0);
std::vector<Row> rows;
for (unsigned seed : {12u, 13u, 14u}) {
std::mt19937 random(seed);
std::shuffle(keys.begin(), keys.end(), random);
rows.push_back(measure(keys));
}
std::cout << std::setw(9) << n << std::fixed << std::setprecision(1) << std::setw(7) << std::log2(n)
<< std::setw(7) << 2 * std::log2(n + 1.0) - 1 << std::setw(5) << rows[0].avl_height << std::setw(4) << rows[1].avl_height
<< std::setw(4) << rows[2].avl_height << std::setw(5) << rows[0].rb_height << std::setw(4) << rows[1].rb_height
<< std::setw(4) << rows[2].rb_height << std::setprecision(2)
<< std::setw(10) << (rows[0].avl_depth + rows[1].avl_depth + rows[2].avl_depth) / 3
<< std::setw(9) << (rows[0].rb_depth + rows[1].rb_depth + rows[2].rb_depth) / 3 << "\n";
}
return 0;
}// Árbol rojinegro clásico sin valores: el conjunto de claves de los apuntes.
// Es recursivo y no tiene puntero al padre: se repara desde el abuelo, a la vuelta de la recursión.
// Toma las mismas decisiones que el algoritmo con puntero al padre, que construye el laboratorio.
#ifndef RB_SET_H
#define RB_SET_H
#include <cassert>
#include <cstddef>
#include <sstream>
#include <string>
#include <vector>
// Invariantes, además del orden de un árbol de búsqueda:
// 1. Cada nodo es rojo o negro.
// 2. La raíz es negra.
// 3. Las hojas nulas son negras: aquí un puntero nulo cuenta como negro, sin ocupar memoria.
// 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.
// Además, el árbol tiene exactamente size_ nodos, y root_ es nulo si y solo si size_ == 0.
//
// K solo necesita operator<, y se copia al insertar.
template <typename K>
class RedBlackSet {
enum class Color { red, black };
struct Node {
K key;
Node* left = nullptr;
Node* right = nullptr;
Color color = Color::red;
};
public:
// Un paso de la reparación: en qué clave estaba el abuelo, y qué se hizo.
struct Step {
K key;
std::string kind;
};
RedBlackSet() = default;
~RedBlackSet() { destroy(root_); }
// Este conjunto es para estudiar las operaciones: no se copia ni se mueve.
RedBlackSet(const RedBlackSet&) = delete;
RedBlackSet& operator=(const RedBlackSet&) = delete;
std::size_t size() const { return size_; }
bool contains(const K& key) const {
const Node* node = root_;
while (node != nullptr) {
if (key < node->key) {
node = node->left;
} else if (node->key < key) {
node = node->right;
} else {
return true;
}
}
return false;
}
// Devuelve false si la clave ya estaba.
bool insert(const K& key) {
last_steps_.clear();
bool added = false;
root_ = insert_at(root_, key, added);
if (added) {
size_++;
}
if (root_->color == Color::red) {
last_steps_.push_back({root_->key, "raiz roja: pintar de negro"});
root_->color = Color::black;
}
return added;
}
// Altura: aristas del camino más largo desde la raíz. Vacío: -1. Un solo nodo: 0.
int height() const { return height_of(root_); }
// Cuántos negros hay en un camino desde la raíz hasta una hoja nula. La hoja nula no se cuenta.
int black_height() const {
int blacks = 0;
for (const Node* node = root_; node != nullptr; node = node->left) {
blacks += is_red(node) ? 0 : 1;
}
return blacks;
}
// Lo que hizo la última inserción, de abajo hacia arriba.
const std::vector<Step>& last_steps() const { return last_steps_; }
long rotations() const { return rotations_; }
// Cuántas veces se aplicó el caso del tío rojo. No cuenta los otros cambios de color.
long recolors() const { return recolors_; }
// La suma de las profundidades de todos los nodos.
long total_depth() const { return depth_sum(root_, 0); }
std::vector<K> in_order() const {
std::vector<K> keys;
walk_in(root_, keys);
return keys;
}
// El árbol en una línea: clave(izquierdo,derecho), con _ si falta un hijo y r si el nodo es rojo.
std::string shape() const {
std::ostringstream out;
write_shape(root_, out);
return out.str();
}
// El árbol 2-3-4 que representa: cada negro con sus hijos rojos forma un nodo.
std::string collapsed() const {
std::ostringstream out;
write_group(root_, out);
return out.str();
}
// Cuántos nodos de 2 claves tiene el árbol 2-3-4, según hacia dónde quedó el rojo.
long left_leaning_groups() const { return count_leaning(root_, true); }
long right_leaning_groups() const { return count_leaning(root_, false); }
void check_invariants() const {
assert((root_ == nullptr) == (size_ == 0));
assert(!is_red(root_));
std::size_t count = 0;
check_node(root_, nullptr, nullptr, count);
assert(count == size_);
}
private:
static bool is_red(const Node* node) { return node != nullptr && node->color == Color::red; }
static int height_of(const Node* node) {
if (node == nullptr) {
return -1;
}
int left = height_of(node->left);
int right = height_of(node->right);
return 1 + (left > right ? left : right);
}
// 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;
}
// Sube al hijo izquierdo de x, y devuelve la nueva raíz del subárbol. Solo cambia enlaces.
Node* rotate_right(Node* x) {
Node* y = x->left;
x->left = y->right;
y->right = x;
rotations_++;
return y;
}
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);
}
// Tío rojo: el abuelo pasa a rojo, y el padre y el tío a negro. El problema sube.
void recolor(Node* grandparent) {
last_steps_.push_back({grandparent->key, "tio rojo: recolorear"});
grandparent->color = Color::red;
grandparent->left->color = Color::black;
grandparent->right->color = Color::black;
recolors_++;
}
// Si hay un rojo con hijo rojo debajo de grandparent, lo repara y devuelve la raíz del subárbol.
Node* repair_from_grandparent(Node* grandparent) {
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;
}
if (is_red(right) && (is_red(right->left) || is_red(right->right))) {
if (is_red(left)) {
recolor(grandparent);
return grandparent;
}
if (is_red(right->left)) {
last_steps_.push_back({grandparent->key, "tio negro, zigzag: dos rotaciones"});
grandparent->right = rotate_right(right);
} else {
last_steps_.push_back({grandparent->key, "tio negro, en linea: una rotacion"});
}
Node* top = rotate_left(grandparent);
top->color = Color::black;
grandparent->color = Color::red;
return top;
}
return grandparent;
}
static void destroy(Node* node) {
if (node == nullptr) {
return;
}
destroy(node->left);
destroy(node->right);
delete node;
}
static long depth_sum(const Node* node, long depth) {
if (node == nullptr) {
return 0;
}
return depth + depth_sum(node->left, depth + 1) + depth_sum(node->right, depth + 1);
}
static void walk_in(const Node* node, std::vector<K>& keys) {
if (node == nullptr) {
return;
}
walk_in(node->left, keys);
keys.push_back(node->key);
walk_in(node->right, keys);
}
static void write_shape(const Node* node, std::ostringstream& out) {
if (node == nullptr) {
out << "_";
return;
}
out << node->key;
if (node->color == Color::red) {
out << "r";
}
if (node->left != nullptr || node->right != nullptr) {
out << "(";
write_shape(node->left, out);
out << ",";
write_shape(node->right, out);
out << ")";
}
}
// Escribe el nodo 2-3-4 cuya parte de arriba es node, que es negro: [claves](hijos).
static void write_group(const Node* node, std::ostringstream& out) {
if (node == nullptr) {
out << "_";
return;
}
std::vector<const Node*> keys;
std::vector<const Node*> children;
if (is_red(node->left)) {
keys.push_back(node->left);
children.push_back(node->left->left);
children.push_back(node->left->right);
} else {
children.push_back(node->left);
}
keys.push_back(node);
if (is_red(node->right)) {
keys.push_back(node->right);
children.push_back(node->right->left);
children.push_back(node->right->right);
} else {
children.push_back(node->right);
}
out << "[";
for (std::size_t i = 0; i < keys.size(); i++) {
out << (i > 0 ? " " : "") << keys[i]->key;
}
out << "]";
bool is_leaf = true;
for (const Node* child : children) {
is_leaf = is_leaf && child == nullptr;
}
if (!is_leaf) {
out << "(";
for (std::size_t i = 0; i < children.size(); i++) {
out << (i > 0 ? "," : "");
write_group(children[i], out);
}
out << ")";
}
}
static long count_leaning(const Node* node, bool to_left) {
if (node == nullptr) {
return 0;
}
long own = 0;
if (!is_red(node) && is_red(node->left) != is_red(node->right) && is_red(node->left) == to_left) {
own = 1;
}
return own + count_leaning(node->left, to_left) + count_leaning(node->right, to_left);
}
// Comprueba todo el subárbol y devuelve sus negros hasta una hoja nula.
static int check_node(const Node* node, const K* low, const K* high, std::size_t& count) {
if (node == nullptr) {
return 0;
}
count++;
assert(low == nullptr || *low < node->key);
assert(high == nullptr || node->key < *high);
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);
}
Node* root_ = nullptr;
std::size_t size_ = 0;
long rotations_ = 0;
long recolors_ = 0;
std::vector<Step> last_steps_;
};
#endif// Sigue un árbol rojinegro inserción por inserción, con el árbol 2-3-4 que representa.
// Cada argumento es una clave: rb_trace 10 20 30 15 25
#include <cstdlib>
#include <iostream>
#include "rb_set.h"
int main(int argc, char** argv) {
RedBlackSet<int> tree;
for (int i = 1; i < argc; i++) {
int key = std::atoi(argv[i]);
tree.insert(key);
tree.check_invariants();
std::cout << "insertar " << key << ": " << tree.shape() << "\n";
for (const auto& step : tree.last_steps()) {
std::cout << " en " << step.key << ": " << step.kind << "\n";
}
std::cout << " 2-3-4: " << tree.collapsed() << "\n";
}
std::cout << "altura " << tree.height() << ", negros " << tree.black_height() << ", rotaciones "
<< tree.rotations() << ", recoloreos " << tree.recolors() << "\n";
return 0;
}// El árbol de los apuntes frente a std::set, con claves crecientes.
// Los tiempos dependen de la máquina. -O2, sin sanitizers, mediana de 3.
#include <iomanip>
#include <iostream>
#include <set>
#include "bench.h"
#include "rb_set.h"
namespace {
template <typename Tree>
double time_inserts(int n) {
return median_seconds(3, [&] {
Tree tree;
for (int key = 0; key < n; key++) {
tree.insert(key);
}
keep(tree.size());
});
}
} // namespace
int main() {
const int n = 1024000;
std::cout << std::fixed << std::setprecision(4);
std::cout << "RedBlackSet: " << time_inserts<RedBlackSet<int>>(n) << " s\n";
std::cout << "std::set: " << time_inserts<std::set<int>>(n) << " s\n";
return 0;
}// Sigue un árbol 2-3-4 inserción por inserción. Cada argumento es una clave: tree_234_trace 10 20 30 5
#include <cstdlib>
#include <iostream>
#include "tree_234.h"
int main(int argc, char** argv) {
Tree234<int> tree;
for (int i = 1; i < argc; i++) {
int key = std::atoi(argv[i]);
tree.insert(key);
tree.check_invariants();
std::cout << "insertar " << key << ": " << tree.shape() << "\n";
for (const std::string& node : tree.last_splits()) {
std::cout << " se divide " << node << "\n";
}
}
std::cout << "niveles " << tree.levels() << ", divisiones " << tree.splits() << "\n";
return 0;
}// Árbol 2-3-4: cada nodo tiene de 1 a 3 claves, y todas las hojas están a la misma profundidad.
// Sirve para comparar con el árbol rojinegro. Se elige cuándo y cómo se divide un nodo.
#ifndef TREE_234_H
#define TREE_234_H
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <sstream>
#include <string>
#include <vector>
enum class SplitPolicy {
// Se divide solo si llega una clave a un nodo lleno. Sube la del medio de las 3 que tenía.
old_middle,
// También solo al hacer overflow, pero con las 4 claves juntas sube siempre la segunda.
fixed_second,
// Al bajar, se divide todo nodo lleno que se encuentre, haga falta o no.
top_down,
};
// Invariantes: cada nodo tiene de 1 a 3 claves ordenadas; un nodo interno tiene un hijo más que
// claves; las claves de cada hijo caen entre las de su padre; todas las hojas a la misma profundidad.
template <typename K>
class Tree234 {
struct Node {
std::vector<K> keys;
std::vector<Node*> children;
bool is_leaf() const { return children.empty(); }
};
// Lo que un nodo dividido le entrega a su padre.
struct Split {
bool happened = false;
K up{};
Node* right = nullptr;
};
public:
explicit Tree234(SplitPolicy policy = SplitPolicy::old_middle) : policy_(policy) {}
~Tree234() { destroy(root_); }
// Este árbol es para estudiar las operaciones: no se copia ni se mueve.
Tree234(const Tree234&) = delete;
Tree234& operator=(const Tree234&) = delete;
std::size_t size() const { return size_; }
long splits() const { return splits_; }
// Los nodos que se dividieron en la última inserción, de abajo hacia arriba.
const std::vector<std::string>& last_splits() const { return last_splits_; }
bool contains(const K& key) const {
const Node* node = root_;
while (node != nullptr) {
std::size_t i = position(node, key);
if (i < node->keys.size() && !(key < node->keys[i])) {
return true;
}
node = node->is_leaf() ? nullptr : node->children[i];
}
return false;
}
// Devuelve false si la clave ya estaba.
bool insert(const K& key) {
last_splits_.clear();
if (contains(key)) {
return false;
}
size_++;
if (root_ == nullptr) {
root_ = new Node{{key}, {}};
} else if (policy_ == SplitPolicy::top_down) {
insert_top_down(key);
} else {
Split split = insert_at(root_, key);
if (split.happened) {
grow_root(split);
}
}
return true;
}
// Cuántos niveles de nodos tiene. Vacío: 0.
int levels() const {
int count = 0;
for (const Node* node = root_; node != nullptr; node = node->is_leaf() ? nullptr : node->children[0]) {
count++;
}
return count;
}
// El árbol en una línea: [claves](hijos).
std::string shape() const {
std::ostringstream out;
write_shape(root_, out);
return out.str();
}
void check_invariants() const {
std::size_t count = 0;
check_node(root_, nullptr, nullptr, 1, levels(), count);
assert(count == size_);
}
private:
// El primer lugar cuya clave no es menor que key.
static std::size_t position(const Node* node, const K& key) {
std::size_t i = 0;
while (i < node->keys.size() && node->keys[i] < key) {
i++;
}
return i;
}
void grow_root(const Split& split) {
root_ = new Node{{split.up}, {root_, split.right}};
}
// Baja hasta una hoja, y a la vuelta recibe lo que suba de cada división.
Split insert_at(Node* node, const K& key) {
if (node->is_leaf()) {
return add(node, key, nullptr);
}
Split below = insert_at(node->children[position(node, key)], key);
return below.happened ? add(node, below.up, below.right) : Split{};
}
// Agrega a node una clave, con el hijo que va a su derecha. Si no cabe, lo divide.
Split add(Node* node, const K& key, Node* right_child) {
if (node->keys.size() < 3) {
put(node, key, right_child);
return {};
}
splits_++;
last_splits_.push_back(text_of(node));
if (policy_ == SplitPolicy::old_middle) {
Split split = split_full(node);
put(key < split.up ? node : split.right, key, right_child);
return split;
}
// Con las 4 claves juntas: a la izquierda 1, sube la segunda, y a la derecha 2.
put(node, key, right_child);
Split split;
split.happened = true;
split.up = node->keys[1];
split.right = new Node{{node->keys[2], node->keys[3]}, {}};
if (!node->is_leaf()) {
split.right->children.assign(node->children.begin() + 2, node->children.end());
node->children.resize(2);
}
node->keys.resize(1);
return split;
}
// Divide un nodo con 3 claves: se queda con la primera, y la segunda sube.
static Split split_full(Node* node) {
Split split;
split.happened = true;
split.up = node->keys[1];
split.right = new Node{{node->keys[2]}, {}};
if (!node->is_leaf()) {
split.right->children.assign(node->children.begin() + 2, node->children.end());
node->children.resize(2);
}
node->keys.resize(1);
return split;
}
static void put(Node* node, const K& key, Node* right_child) {
std::size_t i = position(node, key);
node->keys.insert(node->keys.begin() + static_cast<std::ptrdiff_t>(i), key);
if (right_child != nullptr) {
node->children.insert(node->children.begin() + static_cast<std::ptrdiff_t>(i) + 1, right_child);
}
}
void insert_top_down(const K& key) {
if (root_->keys.size() == 3) {
splits_++;
last_splits_.push_back(text_of(root_));
grow_root(split_full(root_));
}
Node* node = root_;
while (!node->is_leaf()) {
std::size_t i = position(node, key);
Node* child = node->children[i];
if (child->keys.size() == 3) {
splits_++;
last_splits_.push_back(text_of(child));
Split split = split_full(child);
put(node, split.up, split.right);
child = key < split.up ? child : split.right;
}
node = child;
}
put(node, key, nullptr);
}
static std::string text_of(const Node* node) {
std::ostringstream out;
write_keys(node, out);
return out.str();
}
static void write_keys(const Node* node, std::ostringstream& out) {
out << "[";
for (std::size_t i = 0; i < node->keys.size(); i++) {
out << (i > 0 ? " " : "") << node->keys[i];
}
out << "]";
}
static void write_shape(const Node* node, std::ostringstream& out) {
if (node == nullptr) {
out << "_";
return;
}
write_keys(node, out);
if (!node->is_leaf()) {
out << "(";
for (std::size_t i = 0; i < node->children.size(); i++) {
out << (i > 0 ? "," : "");
write_shape(node->children[i], out);
}
out << ")";
}
}
static void check_node(const Node* node, const K* low, const K* high, int level, int levels, std::size_t& count) {
if (node == nullptr) {
return;
}
assert(node->keys.size() >= 1 && node->keys.size() <= 3);
assert(node->is_leaf() ? level == levels : node->children.size() == node->keys.size() + 1);
count += node->keys.size();
for (std::size_t i = 0; i < node->keys.size(); i++) {
assert((i == 0 ? low : &node->keys[i - 1]) == nullptr || *(i == 0 ? low : &node->keys[i - 1]) < node->keys[i]);
}
assert(high == nullptr || node->keys.back() < *high);
for (std::size_t i = 0; i < node->children.size(); i++) {
const K* child_low = i == 0 ? low : &node->keys[i - 1];
const K* child_high = i < node->keys.size() ? &node->keys[i] : high;
check_node(node->children[i], child_low, child_high, level + 1, levels, count);
}
}
static void destroy(Node* node) {
if (node == nullptr) {
return;
}
for (Node* child : node->children) {
destroy(child);
}
delete node;
}
SplitPolicy policy_;
Node* root_ = nullptr;
std::size_t size_ = 0;
long splits_ = 0;
std::vector<std::string> last_splits_;
};
#endifErrores
Ejemplos con errores a propósito: no compilan, fallan o dan un resultado incorrecto. Los apuntes explican cada uno.
// Copia de RedBlackSet con un error a elección, para los programas de esta carpeta.
#ifndef BROKEN_RB_H
#define BROKEN_RB_H
#include <cassert>
#include <cstddef>
#include <sstream>
#include <string>
enum class Bug { no_root_paint, new_node_black, single_on_zigzag, no_repaint_after_rotation };
template <Bug bug>
class BrokenRb {
enum class Color { red, black };
struct Node {
int key;
Node* left = nullptr;
Node* right = nullptr;
Color color = Color::red;
};
public:
BrokenRb() = default;
~BrokenRb() { destroy(root_); }
BrokenRb(const BrokenRb&) = delete;
BrokenRb& operator=(const BrokenRb&) = delete;
void insert(int key) {
bool added = false;
root_ = insert_at(root_, key, added);
if (added) {
size_++;
}
if (bug != Bug::no_root_paint) {
root_->color = Color::black;
}
}
bool contains(int key) const {
const Node* node = root_;
while (node != nullptr) {
if (key == node->key) {
return true;
}
node = key < node->key ? node->left : node->right;
}
return false;
}
std::string shape() const {
std::ostringstream out;
write_shape(root_, out);
return out.str();
}
void check_invariants() const {
assert(!is_red(root_));
std::size_t count = 0;
check_node(root_, nullptr, nullptr, count);
assert(count == size_);
}
private:
static bool is_red(const Node* node) { return node != nullptr && node->color == Color::red; }
static Node* rotate_left(Node* x) {
Node* y = x->right;
x->right = y->left;
y->left = x;
return y;
}
static Node* rotate_right(Node* x) {
Node* y = x->left;
x->left = y->right;
y->right = x;
return y;
}
Node* insert_at(Node* node, int key, bool& added) {
if (node == nullptr) {
added = true;
Node* fresh = new Node{key};
if (bug == Bug::new_node_black) {
fresh->color = Color::black;
}
return fresh;
}
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);
}
static void recolor(Node* grandparent) {
grandparent->color = Color::red;
grandparent->left->color = Color::black;
grandparent->right->color = Color::black;
}
static Node* paint_top(Node* top, Node* grandparent) {
if (bug != Bug::no_repaint_after_rotation) {
top->color = Color::black;
grandparent->color = Color::red;
}
return top;
}
static Node* repair_from_grandparent(Node* grandparent) {
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) && bug != Bug::single_on_zigzag) {
grandparent->left = rotate_left(left);
}
return paint_top(rotate_right(grandparent), grandparent);
}
if (is_red(right) && (is_red(right->left) || is_red(right->right))) {
if (is_red(left)) {
recolor(grandparent);
return grandparent;
}
if (is_red(right->left) && bug != Bug::single_on_zigzag) {
grandparent->right = rotate_right(right);
}
return paint_top(rotate_left(grandparent), grandparent);
}
return grandparent;
}
static void destroy(Node* node) {
if (node != nullptr) {
destroy(node->left);
destroy(node->right);
delete node;
}
}
static void write_shape(const Node* node, std::ostringstream& out) {
if (node == nullptr) {
out << "_";
return;
}
out << node->key;
if (node->color == Color::red) {
out << "r";
}
if (node->left != nullptr || node->right != nullptr) {
out << "(";
write_shape(node->left, out);
out << ",";
write_shape(node->right, out);
out << ")";
}
}
static int check_node(const Node* node, const int* low, const int* high, std::size_t& count) {
if (node == nullptr) {
return 0;
}
count++;
assert(low == nullptr || *low < node->key);
assert(high == nullptr || node->key < *high);
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);
}
Node* root_ = nullptr;
std::size_t size_ = 0;
};
#endif// Error a propósito: el nodo nuevo se pinta de negro.
#include <iostream>
#include "broken_rb.h"
int main() {
std::cout << std::unitbuf;
BrokenRb<Bug::new_node_black> tree;
for (int key : {10, 20}) {
tree.insert(key);
std::cout << "insertar " << key << ": " << tree.shape() << "\n";
}
tree.check_invariants();
std::cout << "check_invariants no vio nada\n";
return 0;
}// Error a propósito: se rota, y no se intercambian los colores.
#include <iostream>
#include "broken_rb.h"
int main() {
std::cout << std::unitbuf;
BrokenRb<Bug::no_repaint_after_rotation> tree;
for (int key : {10, 20, 30}) {
tree.insert(key);
std::cout << "insertar " << key << ": " << tree.shape() << "\n";
}
tree.check_invariants();
std::cout << "check_invariants no vio nada\n";
return 0;
}// Error a propósito: al terminar la inserción no se pinta la raíz de negro.
#include <iostream>
#include "broken_rb.h"
int main() {
std::cout << std::unitbuf;
BrokenRb<Bug::no_root_paint> tree;
for (int key : {10, 20, 30, 40, 50}) {
tree.insert(key);
std::cout << "insertar " << key << ": " << tree.shape() << "\n";
}
std::cout << "encuentra el 40: " << (tree.contains(40) ? "si" : "no") << "\n";
tree.check_invariants();
std::cout << "check_invariants no vio nada\n";
return 0;
}// Error a propósito: en el zigzag se hace solo la rotación del abuelo.
#include <iostream>
#include "broken_rb.h"
int main() {
std::cout << std::unitbuf;
BrokenRb<Bug::single_on_zigzag> tree;
for (int key : {30, 10, 20}) {
tree.insert(key);
std::cout << "insertar " << key << ": " << tree.shape() << "\n";
}
tree.check_invariants();
std::cout << "check_invariants no vio nada\n";
return 0;
}Pruebas
Comprueban lo que afirman los apuntes; se ejecutan con make test.
"""Corre los ejemplos de la semana y comprueba lo que se puede contar: nunca tiempos."""
import math
import pathlib
import re
import subprocess
import unittest
HERE = pathlib.Path(__file__).parent
SAN = ["g++", "-Wall", "-Wextra", "-std=c++20", "-g", "-fsanitize=address,undefined"]
def run(*command):
return subprocess.run(
list(command), cwd=HERE, text=True, encoding="utf-8", errors="replace", stdin=subprocess.DEVNULL,
stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=300,
)
def bound(n):
return 2 * math.log2(n + 1) - 1
class Examples(unittest.TestCase):
def test_structure_tests_pass(self):
done = run("build/test_structures")
self.assertEqual(done.returncode, 0, done.stdout)
self.assertIn("ok", done.stdout)
def test_programs_exit_cleanly(self):
for command in [["build/rb_trace", "1", "2", "3"], ["build/tree_234_trace", "1", "2", "3", "4"], ["build/height_bound"], ["build/btree_levels"]]:
with self.subTest(program=command[0]):
done = run(*command)
self.assertEqual(done.returncode, 0, done.stdout)
def test_review_question(self):
"""La pregunta 4 de la guía: 10, 20, 30, 15 y 25."""
lines = run("build/rb_trace", "10", "20", "30", "15", "25").stdout.splitlines()
self.assertIn("insertar 30: 20(10r,30r)", lines)
self.assertIn(" en 10: tio negro, en linea: una rotacion", lines)
self.assertIn("insertar 15: 20(10(_,15r),30)", lines)
self.assertIn(" en 20: tio rojo: recolorear", lines)
self.assertIn(" en 20: raiz roja: pintar de negro", lines)
self.assertEqual(lines[-3:-1], ["insertar 25: 20(10(_,15r),30(25r,_))", " 2-3-4: [20]([10 15],[25 30])"])
self.assertEqual(lines[-1], "altura 2, negros 2, rotaciones 1, recoloreos 1")
def test_every_order_rotates_at_most_twice(self):
rows = run("build/all_orders").stdout.splitlines()[1:]
self.assertEqual(len(rows), 9)
for row in rows:
fields = row.split()
n, max_height, rotations = int(fields[0]), int(fields[3]), int(fields[5])
self.assertLessEqual(rotations, 2)
if n >= 3:
self.assertEqual(rotations, 2)
self.assertLessEqual(max_height, bound(n))
self.assertEqual(fields[7], "si")
def test_collapse_matches_only_with_the_same_split_policy(self):
lines = run("build/collapse_check").stdout.splitlines()
rows = [line.split() for line in lines[1:10]]
self.assertEqual([int(row[0]) for row in rows], list(range(1, 10)))
for row in rows:
self.assertEqual(row[2], "0")
self.assertGreater(int(rows[3][3]), 0)
self.assertEqual(rows[7][4], "0")
self.assertGreater(int(rows[8][4]), 0)
self.assertIn(" al hacer overflow, sube la del medio de las 3: ninguno", lines)
self.assertIn(" al hacer overflow, sube siempre la segunda de las 4: 1 3 4 2", lines)
self.assertIn(" al bajar, se divide todo nodo lleno: 1 2 3 4 5 6 7 8 9", lines)
for seed in [12, 13, 14]:
self.assertIn(f" semilla {seed}: calza", lines)
def test_each_234_tree_has_two_to_the_t_shapes(self):
done = run("build/all_shapes")
self.assertEqual(done.returncode, 0, done.stdout)
for row in done.stdout.splitlines()[1:]:
n, trees, groups, total, reachable, height, inserted, _ = row.split()
self.assertEqual(trees, total)
self.assertLessEqual(int(groups), int(trees))
self.assertLessEqual(int(reachable), int(trees))
self.assertLessEqual(int(inserted), int(height))
self.assertLessEqual(int(height), bound(int(n)))
def test_tallest_tree_agrees_with_generating_them_all(self):
fewest = {}
for row in run("build/height_bound").stdout.splitlines()[1:]:
h, nodes, _, printed, _ = row.split()
fewest[int(h)] = int(nodes)
self.assertLessEqual(int(h), bound(int(nodes)))
self.assertLess(bound(int(nodes)) - int(h), 2.2)
self.assertAlmostEqual(float(printed), bound(int(nodes)), places=2)
for row in run("build/all_shapes").stdout.splitlines()[1:]:
fields = row.split()
n, tallest = int(fields[0]), int(fields[5])
self.assertLessEqual(fewest[tallest], n)
if tallest + 1 in fewest:
self.assertGreater(fewest[tallest + 1], n)
def test_counts_table(self):
rows = run("build/count_table").stdout.splitlines()[1:]
self.assertEqual(len(rows), 9)
for row in rows:
name, n, avl, rb, recolors, max_rotations, max_recolors = row.split()
self.assertLessEqual(int(max_rotations), 2)
if name == "azar":
self.assertLess(float(rb), 0.86 * float(avl))
else:
self.assertEqual(int(max_rotations), 1)
self.assertLessEqual(abs(float(rb) - float(avl)), 0.01)
def test_height_table(self):
lines = run("build/height_table").stdout.splitlines()
split = lines.index("Claves al azar, tres semillas")
for row in lines[2:split]:
fields = row.split()
n, avl, rb = int(fields[0]), int(fields[3]), int(fields[4])
self.assertEqual(avl, math.floor(math.log2(n)))
self.assertLess(rb, bound(n))
self.assertGreater(rb, 1.6 * avl)
for row in lines[split + 2:]:
fields = row.split()
n = int(fields[0])
avl = [int(field) for field in fields[3:6]]
rb = [int(field) for field in fields[6:9]]
self.assertLessEqual(max(rb), max(avl) + 1)
self.assertLessEqual(max(avl), max(rb))
self.assertLess(max(rb), bound(n))
self.assertLess(float(fields[10]) / float(fields[9]), 1.02)
def test_btree_levels(self):
rows = [line.split() for line in run("build/btree_levels").stdout.splitlines()[1:]]
self.assertEqual(dict((int(a), int(b)) for a, b in rows), {1: 30, 3: 15, 15: 8, 100: 5, 500: 4, 1000: 3})
class SameRotations(unittest.TestCase):
"""Las rotaciones del rojinegro son las de la semana 11, sin cambiar nada."""
def body(self, path, name):
text = (HERE / path).read_text(encoding="utf-8")
match = re.search(r"Node\* %s\(Node\* x\) \{.*?\n \}\n" % name, text, re.S)
self.assertIsNotNone(match, f"falta {name} en {path}")
return match.group(0)
@unittest.skipUnless((HERE / "solution").is_dir(), "no está la solución")
def test_rotations_are_copied_verbatim(self):
for name in ["rotate_left", "rotate_right"]:
self.assertEqual(self.body("solution/red_black_map.h", name), self.body("lab/avl_map.h", name))
def test_no_erase_is_offered(self):
for path in ["lab/red_black_map.h", "rb_set.h"]:
self.assertNotIn("erase", (HERE / path).read_text(encoding="utf-8"))
class DeliberateErrors(unittest.TestCase):
def build(self, name):
binary = f"build/{name}"
done = run(*SAN, f"errors/{name}.cpp", "-o", binary)
self.assertEqual(done.returncode, 0, done.stdout)
return binary
def test_no_root_paint(self):
done = run(self.build("no_root_paint"))
self.assertNotEqual(done.returncode, 0)
self.assertIn("encuentra el 40: si", done.stdout)
self.assertIn("Assertion `!is_red(root_)'", done.stdout)
def test_new_node_black(self):
done = run(self.build("new_node_black"))
self.assertNotEqual(done.returncode, 0)
self.assertIn("Assertion `left == right'", done.stdout)
def test_single_on_zigzag(self):
done = run(self.build("single_on_zigzag"))
self.assertNotEqual(done.returncode, 0)
self.assertIn("insertar 20: 10(_,30r(20r,_))", done.stdout)
def test_no_repaint_after_rotation(self):
done = run(self.build("no_repaint_after_rotation"))
self.assertNotEqual(done.returncode, 0)
self.assertIn("insertar 30: 20(10,30r)", done.stdout)
if __name__ == "__main__":
unittest.main()"""Pruebas del laboratorio. LAB_DIR dice dónde está el mapa: lab o solution.
Cada prueba corre en su propio proceso, con sanitizers: una fuga o un acceso inválido
la hace fallar aunque el resultado parezca correcto.
"""
import os
import pathlib
import re
import subprocess
import unittest
HERE = pathlib.Path(__file__).parent
LAB_DIR = os.environ.get("LAB_DIR", "solution")
BINARY = HERE / "build" / LAB_DIR / "map_tests"
BASE = [
"new_is_empty", "insert_and_find", "insert_does_not_overwrite", "subscript_operator", "strings_as_keys",
"only_needs_less_than", "no_objects_left_behind", "copy_is_independent", "self_assignment",
"move_leaves_empty_and_usable", "random_against_map_links", "queries_still_work",
]
ROTATIONS = [
"rotate_right_at_root", "rotate_left_at_root", "rotate_under_left_link", "rotate_under_right_link",
"rotate_moves_middle_subtree", "rotate_without_middle_subtree", "rotate_leaves_colors_alone",
"rotate_keeps_nodes_in_place", "rotate_counts_rotations", "rotate_random_nodes",
]
BROKEN = [
"broken_invalid_color", "broken_red_root_alone", "broken_red_root_with_children", "broken_red_red_left",
"broken_red_red_right", "broken_red_red_deep", "broken_blacks_at_root", "broken_blacks_missing_child",
"broken_blacks_inner_left", "broken_blacks_inner_right", "broken_blacks_inner_deep", "broken_order_child",
"broken_order_deep_left", "broken_order_deep_right", "broken_parent_of_child", "broken_parent_of_root", "broken_size",
]
INSERT = [
"first_key_is_black", "parent_black_needs_nothing", "uncle_red_recolors", "line_rotates_once",
"zigzag_rotates_twice", "review_question", "recolor_then_rotate_above", "root_stays_black", "subscript_repairs",
"subscript_reference_after_rotation", "repeated_key_changes_nothing", "at_most_two_rotations_in_every_order",
"same_as_notes_tree_in_every_order", "same_as_notes_tree_with_many_keys", "sorted_keys_in_both_directions",
"pointers_survive_rotations", "iterate_after_rotations", "copy_keeps_colors", "random_inserts_against_map",
"random_strings",
]
MEASURE = ["time_inserts_builds_a_new_map_each_time", "time_finds_looks_up_every_key", "measure_works_with_the_real_maps"]
def short_report(text):
"""Deja lo útil de un informe: el tipo de error y las líneas de sus archivos."""
if "ERROR:" not in text and "runtime error" not in text and "Assertion" not in text:
return text.strip()
useful = [line.strip() for line in text.splitlines()
if "ERROR:" in line or "SUMMARY:" in line or "runtime error" in line or "Assertion" in line
or "sin implementar" in line or re.search(r"(red_black_map\.h|map_tests\.cpp|measure\.h):\d+", line)]
return "\n".join(useful[:12])
def build(target):
done = subprocess.run(
["make", "--no-print-directory", f"LAB_DIR={LAB_DIR}", f"build/{LAB_DIR}/{target}"],
cwd=HERE, text=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT,
)
return done.returncode, done.stdout
def run_case(name):
return subprocess.run(
[str(BINARY), name], cwd=HERE, text=True,
stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=120,
)
def add_cases(cls, names):
for name in names:
def case(self, name=name):
done = run_case(name)
self.assertEqual(done.returncode, 0, short_report(done.stdout))
setattr(cls, f"test_{name}", case)
return cls
def add_broken(cls, names):
for name in names:
def case(self, name=name):
done = run_case(name)
self.assertIn("sano", done.stdout, "check_invariants falló en un árbol sano\n" + short_report(done.stdout))
self.assertNotEqual(done.returncode, 0, "check_invariants no notó el daño")
self.assertIn("Assertion", done.stdout, "falló por otra razón, y no un assert\n" + short_report(done.stdout))
self.assertNotIn("sin implementar", done.stdout)
setattr(cls, f"test_{name}", case)
class LabCase(unittest.TestCase):
@classmethod
def setUpClass(cls):
code, output = build("map_tests")
if code != 0:
raise AssertionError(output)
@unittest.skipUnless((HERE / LAB_DIR).is_dir(), f"no existe la carpeta {LAB_DIR}")
class Builds(unittest.TestCase):
def test_builds_without_warnings(self):
for target in ["map_tests", "bench_counts", "bench_times", "bench_words"]:
(HERE / "build" / LAB_DIR / target).unlink(missing_ok=True)
code, output = build(target)
self.assertEqual(code, 0, output)
self.assertNotIn("warning", output)
@unittest.skipUnless((HERE / LAB_DIR).is_dir(), f"no existe la carpeta {LAB_DIR}")
class TestBase(LabCase):
"""El mapa de partida: pasa desde el inicio, y debe seguir pasando al final."""
@unittest.skipUnless((HERE / LAB_DIR).is_dir(), f"no existe la carpeta {LAB_DIR}")
class TestRotations(LabCase):
"""Paso 1: rotate_left y rotate_right, las de la semana 11."""
@unittest.skipUnless((HERE / LAB_DIR).is_dir(), f"no existe la carpeta {LAB_DIR}")
class TestCheck(LabCase):
"""Paso 2: check_invariants acepta árboles sanos y detecta los rotos."""
@unittest.skipUnless((HERE / LAB_DIR).is_dir(), f"no existe la carpeta {LAB_DIR}")
class TestInsert(LabCase):
"""Paso 3: la inserción, contra std::map y contra las formas exactas."""
@unittest.skipUnless((HERE / LAB_DIR).is_dir(), f"no existe la carpeta {LAB_DIR}")
class TestMeasure(LabCase):
"""Paso 5: time_inserts y time_finds hacen el trabajo que dicen."""
add_cases(TestBase, BASE)
add_cases(TestRotations, ROTATIONS)
add_cases(TestCheck, ["check_accepts_healthy_trees"])
add_broken(TestCheck, BROKEN)
add_cases(TestInsert, INSERT)
add_cases(TestMeasure, MEASURE)
if __name__ == "__main__":
unittest.main()"""Vuelve a correr los comandos que aparecen en los apuntes y en las diapositivas
y comprueba que el código citado existe de verdad en esta carpeta."""
import os
import pathlib
import platform
import re
import subprocess
import unittest
try:
import pty
except ImportError:
pty = None
HERE = pathlib.Path(__file__).parent
ROOT = HERE.parent.parent
NOTES = ROOT / "notes" / "week-12.md"
SLIDES = ROOT / "slides" / "week-12.tex"
# Antes de un bloque cuya salida cambia con el sistema. Se corre, pero no se compara.
SYSTEM_DEPENDENT = "<!-- depende del sistema -->"
# Antes de un bloque que corre la solución del laboratorio, que ustedes no tienen. Tampoco se compara.
USES_SOLUTION = "<!-- usa la solucion, depende del sistema -->"
# Antes de un informe de ASan. Puede omitir líneas, pero no cambiarlas ni reordenarlas.
# Las direcciones y los números de proceso no se comparan.
REPORT = "<!-- informe recortado -->"
# Los informes se capturaron en esta arquitectura: en otra cambian líneas de las bibliotecas.
REPORT_MACHINE = "aarch64"
def normalize(text):
# Según el idioma del entorno, gcc usa comillas tipográficas o rectas.
return text.replace("‘", "'").replace("’", "'")
def run_shell(command):
done = subprocess.run(
["bash", "-c", command], cwd=HERE, text=True, encoding="utf-8",
stdin=subprocess.DEVNULL, stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=120,
)
return normalize(done.stdout)
def run_in_terminal(command):
"""Corre el comando en una terminal de verdad: así se intercala la salida del programa
con el informe, igual que cuando ustedes lo corren."""
master, slave = pty.openpty()
process = subprocess.Popen(
["bash", "-c", command], cwd=HERE, stdin=subprocess.DEVNULL, stdout=slave, stderr=slave,
)
os.close(slave)
data = b""
while True:
try:
chunk = os.read(master, 4096)
except OSError:
break
if not chunk:
break
data += chunk
os.close(master)
process.wait(timeout=120)
text = data.decode("utf-8", errors="replace").replace("\r", "")
return normalize(re.sub(r"\x1b\[[0-9;]*[mK]", "", text))
def clean_lines(text):
return [line.rstrip() for line in text.splitlines()]
def stable(line):
"""Quita de una línea de informe lo que cambia en cada corrida."""
line = re.sub(r"0x[0-9a-f]+", "ADDR", line.strip())
return re.sub(r"==\d+==", "==N==", line)
def split_commands(lines):
"""Parte un bloque de terminal en pares (comando, líneas de salida)."""
pairs = []
for line in lines:
if line.startswith("$ "):
pairs.append((line[2:], []))
elif pairs:
pairs[-1][1].append(normalize(line.rstrip()))
return pairs
def note_blocks(language):
"""Devuelve (líneas, marca) de cada bloque de los apuntes."""
blocks, current, mark, previous = [], None, "", ""
for raw in NOTES.read_text(encoding="utf-8").splitlines():
line = re.sub(r"^> ?", "", raw)
if current is None:
if line.strip() == "```" + language:
current, mark = [], previous.strip()
elif line.strip():
previous = line
elif line.strip() == "```":
blocks.append((current, mark))
current = None
else:
current.append(line)
return blocks
def slide_blocks(environments):
text = SLIDES.read_text(encoding="utf-8")
pattern = r"\\begin\{(?:%s)\}[^\n]*\n(.*?)\\end\{(?:%s)\}" % (environments, environments)
return [match.group(1).splitlines() for match in re.finditer(pattern, text, re.S)]
def known_code_lines():
lines = set()
sources = list(HERE.glob("*.cpp")) + list(HERE.glob("*.h")) + list((HERE / "errors").glob("*.cpp"))
sources += list((HERE / "errors").glob("*.h")) + list((HERE / "lab").glob("*.h"))
sources += [path for path in (HERE / "lab" / "tests").glob("*") if path.is_file()]
for source in sources:
lines.update(line.strip() for line in source.read_text(encoding="utf-8").splitlines())
return lines
class ReportCheck(unittest.TestCase):
def assert_in_order(self, command, expected, actual):
"""Las líneas esperadas aparecen en la salida real, en orden. '...' marca un recorte."""
wanted = [stable(line) for line in expected if line.strip() and line.strip() != "..."]
real = [stable(line) for line in actual]
position = 0
for line in wanted:
with self.subTest(command=command, line=line):
found = [i for i in range(position, len(real)) if real[i] == line]
self.assertTrue(found, f"no aparece en la salida real: {line}")
if found:
position = found[0] + 1
class NotesAreTrue(ReportCheck):
@unittest.skipUnless(NOTES.exists(), "faltan los apuntes")
def test_terminal_blocks_in_notes(self):
checked = 0
for lines, mark in note_blocks("text"):
if not lines or not lines[0].startswith("$ ") or mark == REPORT:
continue
if mark == USES_SOLUTION and not (HERE / "solution").is_dir():
continue
for command, expected in split_commands(lines):
actual = clean_lines(run_shell(command))
checked += 1
if mark not in (SYSTEM_DEPENDENT, USES_SOLUTION):
with self.subTest(command=command):
self.assertEqual(actual, expected)
self.assertGreater(checked, 5)
@unittest.skipUnless(NOTES.exists(), "faltan los apuntes")
@unittest.skipUnless(pty and platform.machine() == REPORT_MACHINE, "los informes son de aarch64")
def test_reports_in_notes(self):
checked = 0
for lines, mark in note_blocks("text"):
if mark != REPORT:
continue
for command, expected in split_commands(lines):
actual = clean_lines(run_in_terminal(command))
self.assert_in_order(command, expected, actual)
checked += 1
self.assertGreater(checked, 1)
@unittest.skipUnless(NOTES.exists(), "faltan los apuntes")
def test_code_blocks_in_notes_exist(self):
known = known_code_lines()
for lines, _ in note_blocks("cpp"):
for line in lines:
if line.strip() and line.strip() != "...":
with self.subTest(line=line):
self.assertIn(line.strip(), known)
class SlidesAreTrue(ReportCheck):
@unittest.skipUnless(SLIDES.exists(), "faltan las diapositivas")
def test_program_output_in_slides(self):
for block in slide_blocks("terminal|salida"):
for command, expected in split_commands(block):
self.assert_in_order(command, expected, clean_lines(run_shell(command)))
# Algunos informes usan programas que compiló la prueba de los apuntes, que corre antes.
@unittest.skipUnless(SLIDES.exists(), "faltan las diapositivas")
@unittest.skipUnless(pty and platform.machine() == REPORT_MACHINE, "los informes son de aarch64")
def test_reports_in_slides(self):
for block in slide_blocks("informe"):
for command, expected in split_commands(block):
self.assert_in_order(command, expected, clean_lines(run_in_terminal(command)))
@unittest.skipUnless(NOTES.exists() and SLIDES.exists(), "faltan los apuntes o las diapositivas")
def test_measurements_in_slides_come_from_notes(self):
"""Los tiempos dependen de la máquina: las diapositivas copian los de los apuntes."""
notes = NOTES.read_text(encoding="utf-8").splitlines()
blocks = slide_blocks("medicion")
self.assertGreaterEqual(len(blocks), 1)
for block in blocks:
for line in block:
with self.subTest(line=line):
self.assertIn(line, notes)
@unittest.skipUnless(SLIDES.exists(), "faltan las diapositivas")
def test_code_blocks_in_slides_exist(self):
known = known_code_lines()
for block in slide_blocks("codigo|codigochico|codigomini"):
for line in block:
if line.strip() and line.strip() != "...":
with self.subTest(line=line):
self.assertIn(line.strip(), known)
if __name__ == "__main__":
unittest.main()// Pruebas de RedBlackSet y de Tree234: casos dirigidos, todos los órdenes y al azar.
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <numeric>
#include <random>
#include <set>
#include <string>
#include <vector>
#include "rb_set.h"
#include "tree_234.h"
namespace {
std::string shape_after(const std::vector<int>& keys) {
RedBlackSet<int> tree;
for (int key : keys) {
tree.insert(key);
tree.check_invariants();
}
return tree.shape();
}
void test_directed_shapes() {
assert(shape_after({10}) == "10");
assert(shape_after({10, 5}) == "10(5r,_)");
assert(shape_after({10, 20}) == "10(_,20r)");
assert(shape_after({30, 20, 10}) == "20(10r,30r)");
assert(shape_after({10, 20, 30}) == "20(10r,30r)");
assert(shape_after({30, 10, 20}) == "20(10r,30r)");
assert(shape_after({10, 30, 20}) == "20(10r,30r)");
assert(shape_after({10, 20, 30, 15, 25}) == "20(10(_,15r),30(25r,_))");
assert(shape_after({11, 2, 14, 1, 7, 15, 5, 8, 4}) == "7(2r(1,5(4r,_)),11r(8,14(_,15r)))");
}
void test_repeated_key_changes_nothing() {
RedBlackSet<int> tree;
for (int key : {5, 3, 8}) {
assert(tree.insert(key));
}
std::string before = tree.shape();
assert(!tree.insert(3));
assert(tree.shape() == before);
assert(tree.size() == 3);
}
void test_review_question_steps() {
RedBlackSet<int> tree;
tree.insert(10);
assert(tree.last_steps().size() == 1);
tree.insert(20);
assert(tree.last_steps().empty());
tree.insert(30);
assert(tree.last_steps().size() == 1);
assert(tree.last_steps()[0].kind == "tio negro, en linea: una rotacion");
tree.insert(15);
assert(tree.last_steps().size() == 2);
assert(tree.last_steps()[0].kind == "tio rojo: recolorear");
assert(tree.last_steps()[1].kind == "raiz roja: pintar de negro");
tree.insert(25);
assert(tree.last_steps().empty());
assert(tree.collapsed() == "[20]([10 15],[25 30])");
assert(tree.left_leaning_groups() == 1);
assert(tree.right_leaning_groups() == 1);
}
// Todos los órdenes: invariantes, cotas, y como máximo 2 rotaciones por inserción.
void test_every_order() {
for (int n = 1; n <= 8; n++) {
std::vector<int> keys(n);
std::iota(keys.begin(), keys.end(), 1);
do {
RedBlackSet<int> tree;
Tree234<int> model;
for (int key : keys) {
long before = tree.rotations();
tree.insert(key);
model.insert(key);
tree.check_invariants();
model.check_invariants();
assert(tree.rotations() - before <= 2);
assert(tree.collapsed() == model.shape());
assert(tree.recolors() == model.splits());
assert(tree.black_height() == model.levels());
}
assert(tree.height() + 1 <= 2 * tree.black_height());
assert(static_cast<long>(tree.size()) >= (1L << tree.black_height()) - 1);
assert(tree.height() <= 2 * std::log2(n + 1.0) - 1);
} while (std::next_permutation(keys.begin(), keys.end()));
}
}
void test_tree_234_policies_keep_their_invariants() {
std::mt19937 random(121);
std::vector<int> keys(3000);
std::iota(keys.begin(), keys.end(), 0);
std::shuffle(keys.begin(), keys.end(), random);
for (SplitPolicy policy : {SplitPolicy::old_middle, SplitPolicy::fixed_second, SplitPolicy::top_down}) {
Tree234<int> tree(policy);
std::set<int> model;
for (int key : keys) {
assert(tree.insert(key));
assert(!tree.insert(key));
model.insert(key);
if (key % 100 == 0) {
tree.check_invariants();
}
}
tree.check_invariants();
assert(tree.size() == model.size());
for (int key : keys) {
assert(tree.contains(key));
}
assert(!tree.contains(-1));
}
}
void test_random_against_std_set() {
std::mt19937 random(122);
RedBlackSet<int> tree;
std::set<int> model;
for (int step = 0; step < 20000; step++) {
int key = static_cast<int>(random() % 5000);
if (step % 3 != 2) {
assert(tree.insert(key) == model.insert(key).second);
} else {
assert(tree.contains(key) == (model.count(key) == 1));
}
assert(tree.size() == model.size());
if (step % 10 == 0) {
tree.check_invariants();
}
}
std::vector<int> expected(model.begin(), model.end());
assert(tree.in_order() == expected);
}
void test_strings_only_need_less_than() {
RedBlackSet<std::string> tree;
for (const char* word : {"pera", "ananá", "zapote", "ñame", "kiwi"}) {
tree.insert(word);
tree.check_invariants();
}
assert((tree.in_order() == std::vector<std::string>{"ananá", "kiwi", "pera", "zapote", "ñame"}));
}
// Crecientes y decrecientes son espejos: la misma altura y las mismas cuentas.
void test_sorted_orders_are_mirrors() {
for (int n : {1, 2, 3, 10, 100, 5000}) {
RedBlackSet<int> up;
RedBlackSet<int> down;
for (int key = 0; key < n; key++) {
up.insert(key);
down.insert(n - key);
}
up.check_invariants();
down.check_invariants();
assert(up.height() == down.height());
assert(up.rotations() == down.rotations());
assert(up.recolors() == down.recolors());
assert(up.total_depth() == down.total_depth());
}
}
} // namespace
int main() {
test_directed_shapes();
test_repeated_key_changes_nothing();
test_review_question_steps();
test_every_order();
test_tree_234_policies_keep_their_invariants();
test_random_against_std_set();
test_strings_only_need_less_than();
test_sorted_orders_are_mirrors();
std::cout << "ok\n";
return 0;
}Laboratorio
Archivos de partida del laboratorio de la semana.
// Lo que se usa para medir AvlMap, RedBlackMap y std::map con el mismo código.
// Paso 5: completen time_inserts y time_finds. Compilar con -O2 y sin sanitizers.
#ifndef MEASURE_H
#define MEASURE_H
#include <map>
#include <vector>
#include "bench.h"
#include "not_implemented.h"
// put y has dejan usar los tres mapas igual: std::map tiene otra interfaz.
template <typename Map>
void put(Map& map, int key) {
map.insert(key, key);
}
inline void put(std::map<int, int>& map, int key) {
map.insert({key, key});
}
template <typename Map>
bool has(const Map& map, int key) {
return map.find(key) != nullptr;
}
inline bool has(const std::map<int, int>& map, int key) {
return map.find(key) != map.end();
}
// Mediana de reps repeticiones, en segundos. En cada una, crea un mapa vacío e inserta todas las claves.
template <typename Map>
double time_inserts(const std::vector<int>&, int) {
not_implemented("time_inserts");
}
// Mediana de reps repeticiones, en segundos. En cada una, busca todas las claves de lookups en map,
// que ya está armado. Usen keep con lo que encontraron, para que el compilador no borre el ciclo.
template <typename Map>
double time_finds(const Map&, const std::vector<int>&, int) {
not_implemented("time_finds");
}
#endif// Para los métodos que todavía no escriben: detiene el programa y dice cuál falta.
#ifndef NOT_IMPLEMENTED_H
#define NOT_IMPLEMENTED_H
#include <cstdio>
#include <cstdlib>
[[noreturn]] inline void not_implemented(const char* name) {
std::fprintf(stderr, "sin implementar: %s\n", name);
std::abort();
}
#endif// Mapa ordenado sobre un árbol rojinegro clásico, con puntero al padre.
// El mapa de búsqueda ya viene completo y funcionando, con un campo color en cada nodo.
// Ustedes completan lo marcado con Paso.
#ifndef RED_BLACK_MAP_H
#define RED_BLACK_MAP_H
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>
#include "not_implemented.h"
// Invariantes:
// - En cada nodo, todas las claves del subárbol izquierdo son menores que la suya, y todas las
// del derecho son mayores. No hay claves repetidas.
// - Si x tiene hijo h, entonces h->parent == x. La raíz tiene padre nulo.
// - El árbol tiene exactamente size_ nodos, y root_ es nulo si y solo si size_ == 0.
// Y las cinco propiedades de un árbol rojinegro:
// 1. Cada nodo es rojo o negro.
// 2. La raíz es negra.
// 3. Las hojas nulas son negras: un puntero nulo cuenta como negro, sin ocupar memoria.
// 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.
//
// K solo necesita operator<, y K y V se copian y se asignan. operator[] además pide V{}.
//
// Ownership: el mapa es owner de todos sus nodos. Los punteros de find, floor, ceiling, min_key y
// max_key, y los iteradores, siguen válidos al insertar: una rotación cambia enlaces y no mueve
// el contenido de ningún nodo. Este mapa no ofrece borrar.
template <typename K, typename V>
class RedBlackMap {
enum class Color { red, black };
struct Node {
K key;
V value;
Node* parent = nullptr;
Node* left = nullptr;
Node* right = nullptr;
Color color = Color::red;
};
friend struct RedBlackMapTestAccess;
public:
// Lo que entrega un iterador. W es V, o const V si el mapa es const.
template <typename W>
struct Entry {
const K& key;
W& value;
};
template <typename W>
class Iter {
public:
Entry<W> operator*() const { return {node_->key, node_->value}; }
Iter& operator++() {
node_ = successor(node_);
return *this;
}
bool operator==(const Iter& other) const { return node_ == other.node_; }
bool operator!=(const Iter& other) const { return node_ != other.node_; }
private:
friend class RedBlackMap;
explicit Iter(Node* node) : node_(node) {}
Node* node_;
};
using iterator = Iter<V>;
using const_iterator = Iter<const V>;
RedBlackMap() = default;
// Postorden sin recursión ni memoria extra: el puntero al padre permite volver.
~RedBlackMap() {
Node* node = root_;
while (node != nullptr) {
if (node->left != nullptr) {
node = node->left;
} else if (node->right != nullptr) {
node = node->right;
} else {
Node* parent = node->parent;
if (parent != nullptr) {
if (parent->left == node) {
parent->left = nullptr;
} else {
parent->right = nullptr;
}
}
delete node;
node = parent;
}
}
}
// Delega en el constructor por defecto: si una copia lanza una excepción, el objeto ya
// existe, así que corre el destructor y libera lo copiado hasta ahí.
RedBlackMap(const RedBlackMap& other) : RedBlackMap() {
copy_nodes_from(other);
}
RedBlackMap& operator=(const RedBlackMap& other) {
RedBlackMap copy(other);
swap(copy);
return *this;
}
RedBlackMap(RedBlackMap&& other) noexcept
: root_(std::exchange(other.root_, nullptr)),
size_(std::exchange(other.size_, 0)),
rotations_(std::exchange(other.rotations_, 0)),
recolors_(std::exchange(other.recolors_, 0)) {}
RedBlackMap& operator=(RedBlackMap&& other) noexcept {
RedBlackMap moved(std::move(other));
swap(moved);
return *this;
}
void swap(RedBlackMap& other) noexcept {
std::swap(root_, other.root_);
std::swap(size_, other.size_);
std::swap(rotations_, other.rotations_);
std::swap(recolors_, other.recolors_);
}
std::size_t size() const { return size_; }
bool empty() const { return size_ == 0; }
// Rotaciones que hizo este mapa, y cuántas veces aplicó el caso del tío rojo.
// Una copia empieza en cero, y un movimiento se las lleva.
long rotations() const { return rotations_; }
long recolors() const { return recolors_; }
// Como std::map::insert: si la clave ya estaba, no cambia su valor y devuelve false.
bool insert(const K& key, const V& value) {
return insert_node(key, value).second;
}
// Como en std::map: si la clave no está, la inserta con V{}.
V& operator[](const K& key) {
return insert_node(key, V{}).first->value;
}
V* find(const K& key) {
Node* node = find_node(key);
return node != nullptr ? &node->value : nullptr;
}
const V* find(const K& key) const {
const Node* node = find_node(key);
return node != nullptr ? &node->value : nullptr;
}
const K* min_key() const {
return root_ != nullptr ? &min_node(root_)->key : nullptr;
}
const K* max_key() const {
if (root_ == nullptr) {
return nullptr;
}
const Node* node = root_;
while (node->right != nullptr) {
node = node->right;
}
return &node->key;
}
// Puntero a la mayor clave <= key; nulo si no hay.
const K* floor(const K& key) const {
const Node* node = root_;
const K* candidate = nullptr;
while (node != nullptr) {
if (key < node->key) {
node = node->left;
} else if (node->key < key) {
candidate = &node->key;
node = node->right;
} else {
return &node->key;
}
}
return candidate;
}
// Puntero a la menor clave >= key; nulo si no hay.
const K* ceiling(const K& key) const {
const Node* node = ceiling_node(key);
return node != nullptr ? &node->key : nullptr;
}
// Los pares con clave en [low, high), en orden. Cuesta O(altura + cantidad de pares).
std::vector<std::pair<K, V>> range(const K& low, const K& high) const {
std::vector<std::pair<K, V>> pairs;
for (Node* node = ceiling_node(low); node != nullptr && node->key < high; node = successor(node)) {
pairs.emplace_back(node->key, node->value);
}
return pairs;
}
iterator begin() { return iterator(root_ != nullptr ? min_node(root_) : nullptr); }
iterator end() { return iterator(nullptr); }
const_iterator begin() const { return const_iterator(root_ != nullptr ? min_node(root_) : nullptr); }
const_iterator end() const { return const_iterator(nullptr); }
// Las claves en orden.
std::vector<K> in_order_keys() const {
std::vector<K> keys;
keys.reserve(size_);
if (root_ != nullptr) {
for (Node* node = min_node(root_); node != nullptr; node = successor(node)) {
keys.push_back(node->key);
}
}
return keys;
}
// Las claves en preorden, que fijan la forma del árbol. Con pila propia, sin recursión.
std::vector<K> pre_order_keys() const {
std::vector<K> keys;
keys.reserve(size_);
std::vector<const Node*> pending;
if (root_ != nullptr) {
pending.push_back(root_);
}
while (!pending.empty()) {
const Node* node = pending.back();
pending.pop_back();
keys.push_back(node->key);
if (node->right != nullptr) {
pending.push_back(node->right);
}
if (node->left != nullptr) {
pending.push_back(node->left);
}
}
return keys;
}
// Altura: aristas del camino más largo desde la raíz. Vacío: -1. Un solo nodo: 0.
int height() const {
int levels = 0;
std::vector<const Node*> level;
if (root_ != nullptr) {
level.push_back(root_);
}
while (!level.empty()) {
std::vector<const Node*> next;
for (const Node* node : level) {
if (node->left != nullptr) {
next.push_back(node->left);
}
if (node->right != nullptr) {
next.push_back(node->right);
}
}
level = std::move(next);
levels++;
}
return levels - 1;
}
// Cuántos negros hay en un camino desde la raíz hasta una hoja nula. La hoja nula no se cuenta.
int black_height() const {
int blacks = 0;
for (const Node* node = root_; node != nullptr; node = node->left) {
blacks += is_red(node) ? 0 : 1;
}
return blacks;
}
// Paso 2. Comprueba con assert las cinco propiedades, el orden de todo el árbol, los padres y el
// tamaño. Recursiva, con una función auxiliar privada: se usa en las pruebas, no en el mapa.
void check_invariants() const { not_implemented("check_invariants"); }
private:
static Node* min_node(Node* node) {
while (node->left != nullptr) {
node = node->left;
}
return node;
}
// El nodo que sigue en el orden de las claves; nulo si es el último.
static Node* successor(Node* node) {
if (node->right != nullptr) {
return min_node(node->right);
}
Node* parent = node->parent;
while (parent != nullptr && parent->right == node) {
node = parent;
parent = parent->parent;
}
return parent;
}
Node* find_node(const K& key) const {
Node* node = root_;
while (node != nullptr) {
if (key < node->key) {
node = node->left;
} else if (node->key < key) {
node = node->right;
} else {
return node;
}
}
return nullptr;
}
// El nodo con la menor clave >= key; nulo si no hay.
Node* ceiling_node(const K& key) const {
Node* node = root_;
Node* candidate = nullptr;
while (node != nullptr) {
if (node->key < key) {
node = node->right;
} else if (key < node->key) {
candidate = node;
node = node->left;
} else {
return node;
}
}
return candidate;
}
// El nodo con esa clave, y si se acaba de crear.
std::pair<Node*, bool> insert_node(const K& key, const V& value) {
Node* parent = nullptr;
Node* node = root_;
bool go_left = false;
while (node != nullptr) {
parent = node;
if (key < node->key) {
go_left = true;
node = node->left;
} else if (node->key < key) {
go_left = false;
node = node->right;
} else {
return {node, false};
}
}
Node* fresh = new Node{key, value, parent};
if (parent == nullptr) {
root_ = fresh;
} else if (go_left) {
parent->left = fresh;
} else {
parent->right = fresh;
}
size_++;
// Paso 3: aquí, y no en insert, para que operator[] también repare.
return {fresh, true};
}
// En el lugar de old_child, que es hijo de parent (o la raíz), pone a child, que puede ser nulo.
void replace_child(Node* parent, Node* old_child, Node* child) {
if (parent == nullptr) {
root_ = child;
} else if (parent->left == old_child) {
parent->left = child;
} else {
parent->right = child;
}
if (child != nullptr) {
child->parent = parent;
}
}
// ---- Lo propio del árbol rojinegro ----
static bool is_red(const Node* node) { return node != nullptr && node->color == Color::red; }
// Paso 1. Copien sus rotate_left y rotate_right de la semana 11, sin cambiar nada.
// Suben al hijo que corresponde, y lo devuelven. Arreglan los enlaces, los padres y root_
// (replace_child ayuda), y suman 1 a rotations_. No tocan los colores.
Node* rotate_left(Node*) { not_implemented("rotate_left"); }
Node* rotate_right(Node*) { not_implemented("rotate_right"); }
// Paso 3. Repara desde z, que es rojo: pseudocódigo reparar_insercion de los apuntes. Al terminar,
// pinta la raíz de negro. Un tío nulo cuenta como negro, y is_red ya lo resuelve. Cada vez que
// aplique el caso del tío rojo, suma 1 a recolors_.
void fix_insert(Node*) { not_implemented("fix_insert"); }
// ---- Lo que viene de la semana 10 ----
// Copia el nodo con todos sus campos, también color, sin sus enlaces.
static Node* clone_node(const Node* from, Node* parent) {
Node* copy = new Node(*from);
copy->parent = parent;
copy->left = nullptr;
copy->right = nullptr;
return copy;
}
// Copia la forma de other en preorden, sin recursión: baja por los hijos que faltan y
// vuelve con el puntero al padre. El árbol a medias queda siempre colgado de root_.
void copy_nodes_from(const RedBlackMap& other) {
if (other.root_ == nullptr) {
return;
}
const Node* from = other.root_;
root_ = clone_node(from, nullptr);
Node* to = root_;
while (true) {
if (from->left != nullptr && to->left == nullptr) {
from = from->left;
to->left = clone_node(from, to);
to = to->left;
} else if (from->right != nullptr && to->right == nullptr) {
from = from->right;
to->right = clone_node(from, to);
to = to->right;
} else if (to->parent != nullptr) {
from = from->parent;
to = to->parent;
} else {
break;
}
}
size_ = other.size_;
}
Node* root_ = nullptr;
std::size_t size_ = 0;
long rotations_ = 0;
long recolors_ = 0;
};
#endif# Informe del laboratorio
Peguen aquí la salida de `make bench-counts` y `make bench-times`, y respondan con sus propios números. Unas pocas líneas por
pregunta.
## Cómo midieron
Máquina, cómo compilaron, cuántas repeticiones y cuántas corridas. Corran `make bench-times` al menos 3 veces. Solo pueden
concluir lo que se repita en las 3.
## Tablas
## Rotaciones y recoloreos
¿Cuántas rotaciones por inserción hace cada árbol con claves crecientes, y cuántas con claves al azar? ¿Cuántos recoloreos? ¿En
cuál de los dos órdenes se nota la ventaja del rojinegro, y de cuánto es?
## Altura
¿Cuánto mide cada árbol con claves crecientes, y con claves al azar? Compárenlo con log₂ n y con 2 log₂(n + 1) − 1. ¿Con qué orden
de llegada se alejan más uno de otro?
## Tiempos
¿Quién inserta más rápido con claves al azar, y por cuánto? ¿Y con claves crecientes? ¿Quién busca más rápido? ¿Cuáles de esas
diferencias se repiten en sus 3 corridas, y cuáles no?
## Conclusión
¿Qué estructura elegirían para muchas lecturas, y cuál para muchas escrituras? ¿Cuándo no vale la pena dejar `std::map`? Justifiquen
cada respuesta con sus números. Si sus números no alcanzan para decidir, díganlo.// Paso 4: cuenta rotaciones y recoloreos de su mapa, frente a las rotaciones del AVL.
// Son conteos: no dependen de la máquina. Compilar con -O2 y sin sanitizers.
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <string>
#include <vector>
#include "avl_map.h"
#include "red_black_map.h"
namespace {
void print_row(const std::string& name, const std::vector<int>& keys) {
AvlMap<int, int> avl;
RedBlackMap<int, int> red_black;
for (int key : keys) {
avl.insert(key, key);
red_black.insert(key, key);
}
double n = static_cast<double>(keys.size());
std::cout << std::setw(13) << name << std::setw(9) << keys.size() << std::fixed << std::setprecision(3)
<< std::setw(9) << avl.rotations() / n << std::setw(9) << red_black.rotations() / n
<< std::setw(10) << red_black.recolors() / n << std::setw(7) << avl.height() << std::setw(7) << red_black.height()
<< std::setw(8) << red_black.black_height() << "\n";
}
} // namespace
int main() {
std::cout << std::setw(13) << "claves" << std::setw(9) << "n" << std::setw(9) << "rot.avl" << std::setw(9) << "rot.rn"
<< std::setw(10) << "recol.rn" << std::setw(7) << "h.avl" << std::setw(7) << "h.rn" << std::setw(8) << "negros" << "\n";
for (int n : {1000, 16000, 256000, 1024000}) {
std::vector<int> keys(n);
std::iota(keys.begin(), keys.end(), 0);
print_row("crecientes", keys);
std::reverse(keys.begin(), keys.end());
print_row("decrecientes", keys);
std::mt19937 random(12);
std::shuffle(keys.begin(), keys.end(), random);
print_row("azar", keys);
}
return 0;
}// Paso 5: el tiempo de insertar y de buscar en un mapa. Se elige cuál con un argumento: avl, rn o std.
// Cada mapa y cada n corren en su propio proceso, porque lo que corrió antes en el mismo proceso cambia los tiempos.
// Los tiempos dependen de la máquina. Compilar con -O2 y sin sanitizers.
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <random>
#include <string>
#include <vector>
#include "avl_map.h"
#include "measure.h"
#include "red_black_map.h"
namespace {
// Las primeras repeticiones de un proceso cuestan más: piden memoria nueva. Con 7, la mediana ya no las toca.
const int repetitions = 7;
// Busca todas las claves, en un orden distinto del de inserción.
template <typename Map>
void print_row(int n, std::mt19937& random) {
std::vector<int> ordered(n);
std::iota(ordered.begin(), ordered.end(), 0);
std::vector<int> lookups = ordered;
std::shuffle(lookups.begin(), lookups.end(), random);
std::vector<int> shuffled = ordered;
std::shuffle(shuffled.begin(), shuffled.end(), random);
std::cout << std::setw(9) << n << std::fixed << std::setprecision(4);
for (const std::vector<int>& keys : {ordered, shuffled}) {
std::cout << std::setw(10) << time_inserts<Map>(keys, repetitions);
Map map;
for (int key : keys) {
put(map, key);
}
std::cout << std::setw(10) << time_finds(map, lookups, repetitions) << std::flush;
}
std::cout << "\n";
}
} // namespace
int main(int argc, char** argv) {
std::string which = argc == 3 ? argv[1] : "";
int n = argc == 3 ? std::stoi(argv[2]) : 0;
std::mt19937 random(12);
if (which == "avl") {
print_row<AvlMap<int, int>>(n, random);
} else if (which == "rn") {
print_row<RedBlackMap<int, int>>(n, random);
} else if (which == "std") {
print_row<std::map<int, int>>(n, random);
} else {
std::cerr << "uso: bench_times avl|rn|std n\n";
return 2;
}
return 0;
}// palabras.txt, otra vez: viene ordenado. Se inserta tal como viene y barajado.
// Se elige el mapa con un argumento, para que cada uno corra en su propio proceso.
// Los tiempos dependen de la máquina. Compilar con -O2 y sin sanitizers.
#include <algorithm>
#include <fstream>
#include <iostream>
#include <map>
#include <random>
#include <string>
#include <vector>
#include "avl_map.h"
#include "bench.h"
#include "red_black_map.h"
namespace {
template <typename Map>
void report(const char* name, const std::vector<std::string>& keys) {
int height = 0;
long rotations = 0;
double seconds = median_seconds(3, [&] {
Map map;
for (const std::string& key : keys) {
map.insert(key, 1);
}
height = map.height();
rotations = map.rotations();
});
std::cout << name << ": altura " << height << ", rotaciones " << rotations << ", " << seconds << " s\n";
}
void report_standard(const char* name, const std::vector<std::string>& keys) {
double seconds = median_seconds(3, [&] {
std::map<std::string, int> map;
for (const std::string& key : keys) {
map.insert({key, 1});
}
keep(map.size());
});
std::cout << name << ": " << seconds << " s\n";
}
} // namespace
int main(int argc, char** argv) {
std::string which = argc == 3 ? argv[2] : "";
if (which != "avl" && which != "rn" && which != "std") {
std::cerr << "uso: bench_words palabras.txt avl|rn|std\n";
return 2;
}
std::ifstream file(argv[1]);
std::vector<std::string> words;
std::string word;
while (std::getline(file, word)) {
words.push_back(word);
}
if (words.empty()) {
std::cerr << "no pude leer " << argv[1] << "\n";
return 1;
}
std::vector<std::string> shuffled = words;
std::mt19937 random(11);
std::shuffle(shuffled.begin(), shuffled.end(), random);
if (which == "avl") {
report<AvlMap<std::string, int>>("AVL, tal como vienen", words);
report<AvlMap<std::string, int>>("AVL, barajadas", shuffled);
} else if (which == "rn") {
report<RedBlackMap<std::string, int>>("rojinegro, tal como vienen", words);
report<RedBlackMap<std::string, int>>("rojinegro, barajadas", shuffled);
} else {
report_standard("std::map, tal como vienen", words);
report_standard("std::map, barajadas", shuffled);
}
return 0;
}// Pruebas públicas del laboratorio. Se corre una por proceso: map_tests nombre.
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <random>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
#include "measure.h"
#include "rb_set.h"
#include "red_black_map.h"
// Deja a las pruebas ver el árbol por dentro, armarlo a mano, rotar y dañarlo.
struct RedBlackMapTestAccess {
template <typename Map>
static auto* root(Map& map) { return map.root_; }
template <typename Map>
static const auto* root(const Map& map) { return map.root_; }
template <typename Map>
static void add_to_size(Map& map) { map.size_++; }
template <typename Map, typename K>
static auto* node(Map& map, const K& key) { return map.find_node(key); }
template <typename Map, typename Node>
static auto* rotate_left(Map& map, Node* node) { return map.rotate_left(node); }
template <typename Map, typename Node>
static auto* rotate_right(Map& map, Node* node) { return map.rotate_right(node); }
// Lee un árbol en una línea: clave(izquierdo,derecho), con _ si falta un hijo y r si es rojo.
template <typename K, typename V>
static void build(RedBlackMap<K, V>& map, const std::string& text) {
std::size_t position = 0;
map.root_ = parse<K, V>(map, text, position, nullptr);
assert(position == text.size());
}
template <typename K, typename V>
static std::string shape(const RedBlackMap<K, V>& map) {
std::ostringstream out;
write<K, V>(map.root_, out);
return out.str();
}
template <typename K, typename V, typename Node>
static void paint_red(Node* node) { node->color = RedBlackMap<K, V>::Color::red; }
template <typename K, typename V, typename Node>
static void paint_black(Node* node) { node->color = RedBlackMap<K, V>::Color::black; }
// Un color que no es ninguno de los dos.
template <typename K, typename V, typename Node>
static void paint_invalid(Node* node) { node->color = static_cast<typename RedBlackMap<K, V>::Color>(2); }
template <typename K, typename V, typename Node>
static bool is_red(const Node* node) { return node != nullptr && node->color == RedBlackMap<K, V>::Color::red; }
private:
template <typename K, typename V>
static typename RedBlackMap<K, V>::Node* parse(RedBlackMap<K, V>& map, const std::string& text, std::size_t& position,
typename RedBlackMap<K, V>::Node* parent) {
if (text[position] == '_') {
position++;
return nullptr;
}
int key = 0;
while (position < text.size() && text[position] >= '0' && text[position] <= '9') {
key = key * 10 + (text[position] - '0');
position++;
}
using Map = RedBlackMap<K, V>;
auto* node = new typename Map::Node{key, key * 10, parent};
node->color = Map::Color::black;
if (position < text.size() && text[position] == 'r') {
node->color = Map::Color::red;
position++;
}
map.size_++;
if (position < text.size() && text[position] == '(') {
position++;
node->left = parse<K, V>(map, text, position, node);
assert(text[position] == ',');
position++;
node->right = parse<K, V>(map, text, position, node);
assert(text[position] == ')');
position++;
}
return node;
}
template <typename K, typename V>
static void write(const typename RedBlackMap<K, V>::Node* node, std::ostringstream& out) {
if (node == nullptr) {
out << "_";
return;
}
out << node->key;
if (node->color == RedBlackMap<K, V>::Color::red) {
out << "r";
}
if (node->left != nullptr || node->right != nullptr) {
out << "(";
write<K, V>(node->left, out);
out << ",";
write<K, V>(node->right, out);
out << ")";
}
}
};
using Access = RedBlackMapTestAccess;
namespace {
using IntMap = RedBlackMap<int, int>;
using Keys = std::vector<int>;
// Clave que solo se puede comparar con <.
struct LessOnly {
int value = 0;
bool operator<(const LessOnly& other) const { return value < other.value; }
};
// Valor que cuenta cuántos objetos viven: una copia olvidada se nota aquí.
struct Live {
int value = 0;
inline static long count = 0;
Live() { count++; }
explicit Live(int v) : value(v) { count++; }
Live(const Live& other) : value(other.value) { count++; }
Live& operator=(const Live& other) = default;
~Live() { count--; }
};
IntMap make_map(const Keys& keys) {
IntMap map;
for (int key : keys) {
map.insert(key, key * 10);
}
return map;
}
// Un árbol armado a mano, con esa forma y esos colores. No pasa por insert.
IntMap tree_of(const std::string& text) {
IntMap map;
Access::build(map, text);
return map;
}
std::string shape_of(const IntMap& map) { return Access::shape(map); }
// Revisa el árbol por su cuenta, sin usar check_invariants. Devuelve los negros hasta una hoja nula.
template <typename K, typename V, typename Node>
int verify_node(const Node* node, const K* low, const K* high, std::size_t& count) {
if (node == nullptr) {
return 0;
}
count++;
assert(low == nullptr || *low < node->key);
assert(high == nullptr || node->key < *high);
assert(node->left == nullptr || node->left->parent == node);
assert(node->right == nullptr || node->right->parent == node);
bool red = Access::is_red<K, V>(node);
if (red) {
assert((!Access::is_red<K, V>(node->left)));
assert((!Access::is_red<K, V>(node->right)));
}
int left = verify_node<K, V>(node->left, low, &node->key, count);
int right = verify_node<K, V>(node->right, &node->key, high, count);
assert(left == right);
return left + (red ? 0 : 1);
}
// Solo orden, padres, raíz y tamaño: para el mapa de partida, cuyos colores no significan nada.
template <typename K, typename V, typename Node>
void verify_links_node(const Node* node, const K* low, const K* high, std::size_t& count) {
if (node == nullptr) {
return;
}
count++;
assert(low == nullptr || *low < node->key);
assert(high == nullptr || node->key < *high);
assert(node->left == nullptr || node->left->parent == node);
assert(node->right == nullptr || node->right->parent == node);
verify_links_node<K, V>(node->left, low, &node->key, count);
verify_links_node<K, V>(node->right, &node->key, high, count);
}
template <typename K, typename V>
void verify_links(const RedBlackMap<K, V>& map) {
const auto* root = Access::root(map);
assert(root == nullptr || root->parent == nullptr);
assert((root == nullptr) == (map.size() == 0));
std::size_t count = 0;
verify_links_node<K, V>(root, static_cast<const K*>(nullptr), static_cast<const K*>(nullptr), count);
assert(count == map.size());
}
// Las cinco propiedades, el orden, los padres, y que la altura respete la cota.
template <typename K, typename V>
void verify_rb(const RedBlackMap<K, V>& map) {
const auto* root = Access::root(map);
assert(root == nullptr || root->parent == nullptr);
assert((root == nullptr) == (map.size() == 0));
assert((!Access::is_red<K, V>(root)));
std::size_t count = 0;
int blacks = verify_node<K, V>(root, static_cast<const K*>(nullptr), static_cast<const K*>(nullptr), count);
assert(count == map.size());
assert(blacks == map.black_height());
assert(map.height() + 1 <= 2 * blacks);
assert(blacks >= 31 || (std::size_t{1} << blacks) - 1 <= map.size());
}
template <typename K, typename V>
void assert_same_as_model(const RedBlackMap<K, V>& mine, const std::map<K, V>& model) {
assert(mine.size() == model.size());
std::vector<K> keys;
for (const auto& [key, value] : model) {
keys.push_back(key);
const V* found = mine.find(key);
assert(found != nullptr);
assert(*found == value);
}
assert(mine.in_order_keys() == keys);
}
void expect_shapes(const Keys& keys, const std::string& shape, long rotations, long recolors) {
IntMap map = make_map(keys);
verify_rb(map);
map.check_invariants();
assert(shape_of(map) == shape);
assert(map.rotations() == rotations);
assert(map.recolors() == recolors);
}
// ---- El mapa de partida: pasan desde el inicio, y deben seguir pasando al final ----
void test_new_is_empty() {
IntMap map;
verify_links(map);
assert(map.empty());
assert(map.height() == -1);
assert(map.black_height() == 0);
assert(map.find(1) == nullptr);
assert(map.in_order_keys().empty());
assert(map.rotations() == 0);
assert(map.recolors() == 0);
}
void test_insert_and_find() {
IntMap map = make_map({5, 3, 8, 1, 4, 7});
verify_links(map);
assert(map.size() == 6);
for (int key : {1, 3, 4, 5, 7, 8}) {
assert(map.find(key) != nullptr);
assert(*map.find(key) == key * 10);
}
for (int key : {0, 2, 6, 9}) {
assert(map.find(key) == nullptr);
}
}
void test_insert_does_not_overwrite() {
IntMap map;
assert(map.insert(1, 100));
assert(!map.insert(1, 200));
assert(*map.find(1) == 100);
assert(map.size() == 1);
}
void test_subscript_operator() {
IntMap map;
map[4] = 40;
map[2]++;
map[2]++;
assert(map.size() == 2);
assert(map[4] == 40);
assert(map[2] == 2);
assert(map.size() == 2);
verify_links(map);
}
void test_strings_as_keys() {
RedBlackMap<std::string, int> map;
map.insert("pera", 1);
map.insert("ananá", 2);
map.insert("zapote", 3);
map["ñame"] = 4;
// Orden de bytes: la ñ, que empieza con 0xC3, va después de la z.
assert((map.in_order_keys() == std::vector<std::string>{"ananá", "pera", "zapote", "ñame"}));
verify_links(map);
}
void test_only_needs_less_than() {
RedBlackMap<LessOnly, std::string> map;
map.insert(LessOnly{2}, "dos");
map.insert(LessOnly{1}, "uno");
assert(!map.insert(LessOnly{2}, "otro"));
assert(*map.find(LessOnly{2}) == "dos");
assert(map.size() == 2);
verify_links(map);
}
void test_no_objects_left_behind() {
{
RedBlackMap<int, Live> map;
for (int i = 0; i < 100; i++) {
map.insert((i * 37) % 101, Live(i));
}
assert(Live::count == 100);
}
assert(Live::count == 0);
}
void test_copy_is_independent() {
IntMap original = make_map({5, 3, 8, 1, 4, 7});
IntMap copy(original);
verify_links(copy);
assert(shape_of(copy) == shape_of(original));
copy.insert(9, 90);
*copy.find(5) = 0;
assert(original.find(9) == nullptr);
assert(*original.find(5) == 50);
IntMap assigned;
assigned.insert(100, 100);
assigned = original;
verify_links(assigned);
assert(assigned.find(100) == nullptr);
assert(shape_of(assigned) == shape_of(original));
}
void test_self_assignment() {
IntMap map = make_map({2, 1, 3});
IntMap& alias = map;
map = alias;
verify_links(map);
assert(map.size() == 3);
map = std::move(alias);
verify_links(map);
assert(map.size() == 3);
}
void test_move_leaves_empty_and_usable() {
IntMap source = make_map({2, 1, 3});
IntMap target(std::move(source));
assert(target.size() == 3);
verify_links(target);
verify_links(source);
assert(source.empty());
source.insert(1, 1);
assert(source.size() == 1);
IntMap other;
other = std::move(target);
assert(other.size() == 3);
verify_links(other);
}
void test_random_against_map_links() {
std::mt19937 random(20261117);
IntMap mine;
std::map<int, int> model;
for (int step = 0; step < 4000; step++) {
int key = static_cast<int>(random() % 500);
if (random() % 10 < 7) {
assert(mine.insert(key, step) == model.insert({key, step}).second);
} else {
const int* found = mine.find(key);
auto position = model.find(key);
assert((found != nullptr) == (position != model.end()));
assert(found == nullptr || *found == position->second);
}
assert(mine.size() == model.size());
}
verify_links(mine);
assert_same_as_model(mine, model);
}
void test_queries_still_work() {
IntMap map = make_map({20, 10, 30, 5, 15, 25, 35});
assert(*map.min_key() == 5);
assert(*map.max_key() == 35);
assert(map.floor(4) == nullptr);
assert(*map.floor(14) == 10);
assert(*map.ceiling(16) == 20);
assert(map.ceiling(36) == nullptr);
auto pairs = map.range(10, 25);
assert((pairs == std::vector<std::pair<int, int>>{{10, 100}, {15, 150}, {20, 200}}));
Keys keys;
for (auto [key, value] : map) {
assert(value == key * 10);
keys.push_back(key);
}
assert((keys == Keys{5, 10, 15, 20, 25, 30, 35}));
}
// ---- Paso 1: las rotaciones de la semana 11. Los árboles se arman a mano ----
void test_rotate_right_at_root() {
IntMap map = tree_of("40(20(10,30),60)");
auto* node = Access::node(map, 40);
auto* top = Access::rotate_right(map, node);
assert(top->key == 20);
assert(Access::root(map) == top);
assert(top->parent == nullptr);
assert(shape_of(map) == "20(10,40(30,60))");
verify_links(map);
}
void test_rotate_left_at_root() {
IntMap map = tree_of("20(10,40(30,60))");
auto* top = Access::rotate_left(map, Access::node(map, 20));
assert(top->key == 40);
assert(Access::root(map) == top);
assert(top->parent == nullptr);
assert(shape_of(map) == "40(20(10,30),60)");
verify_links(map);
}
void test_rotate_under_left_link() {
IntMap map = tree_of("50(30(20,40),70)");
auto* top = Access::rotate_right(map, Access::node(map, 30));
assert(top->key == 20);
assert(shape_of(map) == "50(20(_,30(_,40)),70)");
assert(Access::node(map, 50)->left == top);
verify_links(map);
}
void test_rotate_under_right_link() {
IntMap map = tree_of("50(30,70(60,80))");
auto* top = Access::rotate_left(map, Access::node(map, 70));
assert(top->key == 80);
assert(shape_of(map) == "50(30,80(70(60,_),_))");
assert(Access::node(map, 50)->right == top);
verify_links(map);
}
// El subárbol del medio se muda: su padre tiene que cambiar.
void test_rotate_moves_middle_subtree() {
IntMap map = tree_of("40(20(10,30),60)");
auto* middle = Access::node(map, 30);
auto* x = Access::node(map, 40);
Access::rotate_right(map, x);
assert(middle->parent == x);
assert(x->left == middle);
Access::rotate_left(map, Access::node(map, 20));
assert(middle->parent == Access::node(map, 20));
}
void test_rotate_without_middle_subtree() {
IntMap map = tree_of("3(2(1,_),_)");
Access::rotate_right(map, Access::node(map, 3));
assert(shape_of(map) == "2(1,3)");
verify_links(map);
IntMap other = tree_of("1(_,2(_,3))");
Access::rotate_left(other, Access::node(other, 1));
assert(shape_of(other) == "2(1,3)");
verify_links(other);
}
// Las rotaciones no tocan los colores: cada nodo se queda con el suyo.
void test_rotate_leaves_colors_alone() {
IntMap map = tree_of("40(20r(10,30),60)");
Access::rotate_right(map, Access::node(map, 40));
assert(shape_of(map) == "20r(10,40(30,60))");
Access::rotate_left(map, Access::node(map, 20));
assert(shape_of(map) == "40(20r(10,30),60)");
assert(map.recolors() == 0);
}
void test_rotate_keeps_nodes_in_place() {
IntMap map = tree_of("40(20(10,30),60)");
auto* x = Access::node(map, 40);
auto* y = Access::node(map, 20);
const int* value = map.find(20);
Access::rotate_right(map, x);
assert(x->key == 40);
assert(y->key == 20);
assert(Access::node(map, 40) == x);
assert(map.find(20) == value);
}
void test_rotate_counts_rotations() {
IntMap map = tree_of("40(20(10,30),60)");
Access::rotate_right(map, Access::node(map, 40));
assert(map.rotations() == 1);
Access::rotate_left(map, Access::node(map, 20));
assert(map.rotations() == 2);
}
void test_rotate_random_nodes() {
std::mt19937 random(20261118);
IntMap map = tree_of("8(4(2(1,3),6(5,7)),12(10(9,11),14(13,15)))");
Keys order = map.in_order_keys();
long done = 0;
for (int step = 0; step < 3000; step++) {
auto* node = Access::node(map, static_cast<int>(1 + random() % 15));
if (random() % 2 == 0 && node->right != nullptr) {
Access::rotate_left(map, node);
done++;
} else if (node->left != nullptr) {
Access::rotate_right(map, node);
done++;
}
verify_links(map);
assert(map.in_order_keys() == order);
}
assert(map.rotations() == done);
}
// ---- Paso 2: check_invariants, con árboles armados a mano ----
void test_check_accepts_healthy_trees() {
for (const char* text : {"10", "10(5r,_)", "10(_,20r)", "10(5r,20r)", "10(5,20)", "20(10(_,15r),30(25r,_))",
"20(10(5r,15r),30)", "8(4r(2(1r,3r),6(5r,7r)),12(10r,14r))",
"7(2r(1,5(4r,_)),11r(8,14(_,15r)))"}) {
IntMap map = tree_of(text);
map.check_invariants();
}
IntMap empty;
empty.check_invariants();
}
// Los árboles que hay que detectar. Antes se revisa uno sano, para que un check_invariants
// que siempre falle no pase estas pruebas.
void expect_rejected(const std::string& text) {
IntMap healthy = tree_of("20(10(_,15r),30(25r,_))");
healthy.check_invariants();
std::cout << "sano" << std::endl;
IntMap broken = tree_of(text);
broken.check_invariants();
}
// Propiedad 1: ni rojo ni negro.
void test_broken_invalid_color() {
IntMap healthy = tree_of("20(10,30)");
healthy.check_invariants();
std::cout << "sano" << std::endl;
Access::paint_invalid<int, int>(Access::node(healthy, 10));
healthy.check_invariants();
}
// Propiedad 2: raíz roja, y nada más está mal.
void test_broken_red_root_alone() { expect_rejected("5r"); }
void test_broken_red_root_with_children() { expect_rejected("5r(3,8)"); }
// Propiedad 4: un rojo con hijo rojo. La cantidad de negros es igual en todos los caminos.
void test_broken_red_red_left() { expect_rejected("10(5r(3r,_),15r)"); }
void test_broken_red_red_right() { expect_rejected("10(5r(_,7r),15r)"); }
void test_broken_red_red_deep() { expect_rejected("20(10(5r,15r(12r,_)),30(25r,35r))"); }
// Propiedad 5: distinta cantidad de negros, sin ningún rojo con hijo rojo.
void test_broken_blacks_at_root() { expect_rejected("10(5,15r)"); }
void test_broken_blacks_missing_child() { expect_rejected("10(5,_)"); }
// El camino de más a la izquierda y el de más a la derecha cuentan lo mismo: la diferencia
// está adentro, y solo se ve revisando cada nodo.
void test_broken_blacks_inner_left() { expect_rejected("20(10(5,15r),30(25,35))"); }
void test_broken_blacks_inner_right() { expect_rejected("20(10(5,15),30(25r,35))"); }
void test_broken_blacks_inner_deep() { expect_rejected("40(20(10(5,15),30(25,35)),60(50(45,55r),70(65,75)))"); }
// El orden.
void test_broken_order_child() { expect_rejected("10(15,5)"); }
void test_broken_order_deep_left() { expect_rejected("20(10(5,25),30(22,35))"); }
void test_broken_order_deep_right() { expect_rejected("20(10(5,15),30(18,35))"); }
// Los enlaces y el tamaño.
void test_broken_parent_of_child() {
IntMap map = tree_of("20(10(5,15),30(25,35))");
map.check_invariants();
std::cout << "sano" << std::endl;
auto* node = Access::node(map, 15);
auto* parent = node->parent;
node->parent = Access::node(map, 30);
map.check_invariants();
// Si no lo notó: se repara el enlace, para que el destructor no sea quien falle.
node->parent = parent;
}
void test_broken_parent_of_root() {
IntMap map = tree_of("20(10,30)");
map.check_invariants();
std::cout << "sano" << std::endl;
Access::root(map)->parent = Access::node(map, 10);
map.check_invariants();
// Si no lo notó: se repara el enlace, para que el destructor no sea quien falle.
Access::root(map)->parent = nullptr;
}
void test_broken_size() {
IntMap map = tree_of("20(10,30)");
map.check_invariants();
std::cout << "sano" << std::endl;
Access::add_to_size(map);
map.check_invariants();
}
// ---- Paso 3: la inserción ----
void test_first_key_is_black() { expect_shapes({10}, "10", 0, 0); }
void test_parent_black_needs_nothing() {
expect_shapes({10, 5}, "10(5r,_)", 0, 0);
expect_shapes({10, 20}, "10(_,20r)", 0, 0);
expect_shapes({10, 5, 20}, "10(5r,20r)", 0, 0);
}
void test_uncle_red_recolors() {
expect_shapes({20, 10, 30, 5}, "20(10(5r,_),30)", 0, 1);
expect_shapes({20, 10, 30, 15}, "20(10(_,15r),30)", 0, 1);
expect_shapes({20, 10, 30, 25}, "20(10,30(25r,_))", 0, 1);
expect_shapes({20, 10, 30, 35}, "20(10,30(_,35r))", 0, 1);
}
// Tío nulo: cuenta como negro.
void test_line_rotates_once() {
expect_shapes({30, 20, 10}, "20(10r,30r)", 1, 0);
expect_shapes({10, 20, 30}, "20(10r,30r)", 1, 0);
}
void test_zigzag_rotates_twice() {
expect_shapes({30, 10, 20}, "20(10r,30r)", 2, 0);
expect_shapes({10, 30, 20}, "20(10r,30r)", 2, 0);
}
void test_review_question() {
expect_shapes({10, 20, 30}, "20(10r,30r)", 1, 0);
expect_shapes({10, 20, 30, 15}, "20(10(_,15r),30)", 1, 1);
expect_shapes({10, 20, 30, 15, 25}, "20(10(_,15r),30(25r,_))", 1, 1);
}
// El problema sube, y arriba encuentra un tío negro de verdad, que no es nulo.
void test_recolor_then_rotate_above() {
expect_shapes({11, 2, 14, 1, 7, 15, 5, 8}, "11(2r(1,7(5r,8r)),14(_,15r))", 0, 2);
expect_shapes({11, 2, 14, 1, 7, 15, 5, 8, 4}, "7(2r(1,5(4r,_)),11r(8,14(_,15r)))", 2, 3);
}
void test_root_stays_black() {
IntMap map;
for (int key = 0; key < 200; key++) {
map.insert(key, key);
assert((!Access::is_red<int, int>(Access::root(map))));
}
verify_rb(map);
}
void test_subscript_repairs() {
IntMap map;
for (int key = 0; key < 200; key++) {
map[key] = key;
verify_rb(map);
}
assert(map.rotations() > 0);
assert(map.height() <= 13);
}
void test_subscript_reference_after_rotation() {
IntMap map;
map[1] = 1;
map[2] = 2;
int& value = map[3];
value = 33;
assert(*map.find(3) == 33);
verify_rb(map);
}
void test_repeated_key_changes_nothing() {
IntMap map = make_map({20, 10, 30, 5});
std::string before = shape_of(map);
long rotations = map.rotations();
long recolors = map.recolors();
for (int key : {20, 10, 30, 5}) {
assert(!map.insert(key, 0));
map[key];
}
assert(shape_of(map) == before);
assert(map.rotations() == rotations);
assert(map.recolors() == recolors);
assert(*map.find(5) == 50);
}
void test_at_most_two_rotations_in_every_order() {
for (int n = 1; n <= 7; n++) {
Keys keys(n);
std::iota(keys.begin(), keys.end(), 1);
do {
IntMap map;
for (int key : keys) {
long before = map.rotations();
map.insert(key, key);
assert(map.rotations() - before <= 2);
}
verify_rb(map);
} while (std::next_permutation(keys.begin(), keys.end()));
}
}
// Todos los órdenes de hasta 7 claves dan la forma y las cuentas del árbol de los apuntes.
void test_same_as_notes_tree_in_every_order() {
for (int n = 1; n <= 7; n++) {
Keys keys(n);
std::iota(keys.begin(), keys.end(), 1);
do {
IntMap map;
RedBlackSet<int> notes;
for (int key : keys) {
map.insert(key, key);
notes.insert(key);
}
assert(shape_of(map) == notes.shape());
assert(map.rotations() == notes.rotations());
assert(map.recolors() == notes.recolors());
} while (std::next_permutation(keys.begin(), keys.end()));
}
}
void test_same_as_notes_tree_with_many_keys() {
Keys keys(4000);
std::iota(keys.begin(), keys.end(), 0);
std::mt19937 random(20261119);
std::shuffle(keys.begin(), keys.end(), random);
IntMap map;
RedBlackSet<int> notes;
for (std::size_t i = 0; i < keys.size(); i++) {
map.insert(keys[i], keys[i]);
notes.insert(keys[i]);
if (i % 100 == 0) {
assert(shape_of(map) == notes.shape());
}
}
assert(shape_of(map) == notes.shape());
assert(map.rotations() == notes.rotations());
assert(map.recolors() == notes.recolors());
assert(map.height() == notes.height());
}
void test_sorted_keys_in_both_directions() {
for (int n : {1000, 4000}) {
IntMap up;
IntMap down;
for (int key = 0; key < n; key++) {
up.insert(key, key);
down.insert(n - key, key);
}
verify_rb(up);
verify_rb(down);
assert(up.height() == down.height());
assert(up.rotations() == down.rotations());
assert(up.recolors() == down.recolors());
}
assert(make_map({1, 2, 3, 4, 5, 6, 7, 8}).height() == 3);
}
void test_pointers_survive_rotations() {
IntMap map;
std::vector<const int*> values;
for (int key = 0; key < 500; key++) {
map.insert(key, key * 10);
values.push_back(map.find(key));
}
assert(map.rotations() > 400);
for (int key = 0; key < 500; key++) {
assert(map.find(key) == values[key]);
assert(*values[key] == key * 10);
}
}
void test_iterate_after_rotations() {
IntMap map;
for (int key = 99; key >= 0; key--) {
map.insert(key, key);
}
int next = 0;
for (auto [key, value] : map) {
assert(key == next);
assert(value == next);
next++;
}
assert(next == 100);
}
void test_copy_keeps_colors() {
IntMap original = make_map({10, 20, 30, 15, 25});
IntMap copy(original);
assert(shape_of(copy) == "20(10(_,15r),30(25r,_))");
verify_rb(copy);
copy.insert(26, 0);
verify_rb(copy);
assert(shape_of(original) == "20(10(_,15r),30(25r,_))");
verify_rb(original);
}
void test_random_inserts_against_map() {
std::mt19937 random(20261120);
IntMap mine;
std::map<int, int> model;
for (int step = 0; step < 5000; step++) {
int key = static_cast<int>(random() % 3000);
int action = static_cast<int>(random() % 10);
if (action < 6) {
assert(mine.insert(key, step) == model.insert({key, step}).second);
} else if (action < 8) {
mine[key] = step;
model[key] = step;
} else {
const int* found = mine.find(key);
auto position = model.find(key);
assert((found != nullptr) == (position != model.end()));
assert(found == nullptr || *found == position->second);
}
assert(mine.size() == model.size());
mine.check_invariants();
verify_rb(mine);
}
assert_same_as_model(mine, model);
}
void test_random_strings() {
std::mt19937 random(20261121);
RedBlackMap<std::string, int> mine;
std::map<std::string, int> model;
for (int step = 0; step < 2000; step++) {
std::string key = "clave" + std::to_string(random() % 800);
assert(mine.insert(key, step) == model.insert({key, step}).second);
if (step % 10 == 0) {
mine.check_invariants();
verify_rb(mine);
}
}
assert_same_as_model(mine, model);
}
// ---- Paso 5: lo que mide ----
// Mapa falso: cuenta lo que le piden, sin tiempos.
struct CountingMap {
inline static long created = 0;
inline static long inserted = 0;
inline static long looked_up = 0;
CountingMap() { created++; }
bool insert(int, int) {
inserted++;
return true;
}
const int* find(int key) const {
looked_up++;
static const int value = 1;
return key % 2 == 0 ? &value : nullptr;
}
std::size_t size() const { return 0; }
};
void test_time_inserts_builds_a_new_map_each_time() {
Keys keys(100);
std::iota(keys.begin(), keys.end(), 0);
double seconds = time_inserts<CountingMap>(keys, 3);
assert(seconds >= 0);
assert(CountingMap::created == 3);
assert(CountingMap::inserted == 300);
assert(CountingMap::looked_up == 0);
}
void test_time_finds_looks_up_every_key() {
Keys keys(100);
std::iota(keys.begin(), keys.end(), 0);
CountingMap map;
double seconds = time_finds(map, keys, 5);
assert(seconds >= 0);
assert(CountingMap::created == 1);
assert(CountingMap::inserted == 0);
assert(CountingMap::looked_up == 500);
}
void test_measure_works_with_the_real_maps() {
Keys keys(1000);
std::iota(keys.begin(), keys.end(), 0);
assert((time_inserts<std::map<int, int>>(keys, 1) >= 0));
assert(time_inserts<IntMap>(keys, 1) >= 0);
std::map<int, int> standard;
IntMap mine;
for (int key : keys) {
put(standard, key);
put(mine, key);
}
assert(has(standard, 5) && !has(standard, 5000));
assert(has(mine, 5) && !has(mine, 5000));
assert(time_finds(standard, keys, 1) >= 0);
assert(time_finds(mine, keys, 1) >= 0);
}
struct Test {
const char* name;
void (*run)();
};
#define TEST(name) {#name, test_##name}
const Test tests[] = {
TEST(new_is_empty), TEST(insert_and_find), TEST(insert_does_not_overwrite), TEST(subscript_operator),
TEST(strings_as_keys), TEST(only_needs_less_than), TEST(no_objects_left_behind), TEST(copy_is_independent),
TEST(self_assignment), TEST(move_leaves_empty_and_usable), TEST(random_against_map_links), TEST(queries_still_work),
TEST(rotate_right_at_root), TEST(rotate_left_at_root), TEST(rotate_under_left_link), TEST(rotate_under_right_link),
TEST(rotate_moves_middle_subtree), TEST(rotate_without_middle_subtree), TEST(rotate_leaves_colors_alone),
TEST(rotate_keeps_nodes_in_place), TEST(rotate_counts_rotations), TEST(rotate_random_nodes),
TEST(check_accepts_healthy_trees), TEST(broken_invalid_color), TEST(broken_red_root_alone),
TEST(broken_red_root_with_children), TEST(broken_red_red_left), TEST(broken_red_red_right), TEST(broken_red_red_deep),
TEST(broken_blacks_at_root), TEST(broken_blacks_missing_child), TEST(broken_blacks_inner_left),
TEST(broken_blacks_inner_right), TEST(broken_blacks_inner_deep), TEST(broken_order_child), TEST(broken_order_deep_left),
TEST(broken_order_deep_right), TEST(broken_parent_of_child), TEST(broken_parent_of_root), TEST(broken_size),
TEST(first_key_is_black), TEST(parent_black_needs_nothing), TEST(uncle_red_recolors), TEST(line_rotates_once),
TEST(zigzag_rotates_twice), TEST(review_question), TEST(recolor_then_rotate_above), TEST(root_stays_black),
TEST(subscript_repairs), TEST(subscript_reference_after_rotation), TEST(repeated_key_changes_nothing),
TEST(at_most_two_rotations_in_every_order), TEST(same_as_notes_tree_in_every_order),
TEST(same_as_notes_tree_with_many_keys), TEST(sorted_keys_in_both_directions), TEST(pointers_survive_rotations),
TEST(iterate_after_rotations), TEST(copy_keeps_colors), TEST(random_inserts_against_map), TEST(random_strings),
TEST(time_inserts_builds_a_new_map_each_time), TEST(time_finds_looks_up_every_key),
TEST(measure_works_with_the_real_maps),
};
} // namespace
int main(int argc, char** argv) {
if (argc != 2) {
std::cerr << "uso: map_tests nombre\n";
return 2;
}
for (const Test& test : tests) {
if (std::strcmp(test.name, argv[1]) == 0) {
test.run();
return 0;
}
}
std::cerr << "no existe la prueba " << argv[1] << "\n";
return 2;
}Compilación
Cómo se compilan y ejecutan los ejemplos.
# Semana 12: árboles rojinegros. Se usa dentro del entorno del curso.
#
# make compila los programas de la clase en build/
# make lab compila el laboratorio en build/lab/
# make test corre las pruebas de los ejemplos y de los apuntes
# make test-base comprueba el mapa de partida, que no depende de los colores
# make test-rotations prueba las rotaciones de la semana 11 (paso 1)
# make test-check prueba check_invariants con árboles sanos y rotos (paso 2)
# make test-insert prueba la inserción, contra std::map (paso 3)
# make test-measure prueba time_inserts y time_finds (paso 5)
# make test-lab prueba todo su laboratorio; falla hasta que lo terminen
# make bench-counts cuenta rotaciones y recoloreos, con -O2 y sin sanitizers (paso 4)
# make bench-times mide AVL, rojinegro y std::map, con -O2 y sin sanitizers (paso 5)
# make bench-words lo mismo con palabras.txt, en su orden y barajado (paso 5)
# make clean borra lo generado
#
# Los programas de errors/ tienen errores a propósito. No se compilan con make:
# los compilan las pruebas, y ustedes, con los comandos de los apuntes.
CXX = g++
CXXFLAGS = -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined
BENCHFLAGS = -Wall -Wextra -std=c++20 -O2
DATA ?= ../../data
LAB_DIR ?= lab
BUILD = build
PROGRAMS = rb_trace tree_234_trace btree_levels height_bound test_structures
BENCHES = all_orders all_shapes collapse_check height_table count_table recursive_cost
COMMON_HEADERS = rb_set.h tree_234.h avl_set.h bench.h
LAB_HEADERS = $(LAB_DIR)/red_black_map.h $(LAB_DIR)/measure.h lab/not_implemented.h rb_set.h
.PHONY: all lab test test-base test-rotations test-check test-insert test-measure test-lab bench-counts bench-times bench-words clean
all: $(PROGRAMS:%=$(BUILD)/%) $(BENCHES:%=$(BUILD)/%)
$(PROGRAMS:%=$(BUILD)/%): $(BUILD)/%: %.cpp $(COMMON_HEADERS) | $(BUILD)
$(CXX) $(CXXFLAGS) $< -o $@
# Las mediciones y las búsquedas exhaustivas van con -O2 y sin sanitizers.
$(BENCHES:%=$(BUILD)/%): $(BUILD)/%: %.cpp $(COMMON_HEADERS) | $(BUILD)
$(CXX) $(BENCHFLAGS) $< -o $@
# LAB_DIR va primero: así las pruebas toman el mapa de esa carpeta.
$(BUILD)/$(LAB_DIR)/map_tests: lab/tests/map_tests.cpp $(LAB_HEADERS) | $(BUILD)/$(LAB_DIR)
$(CXX) $(CXXFLAGS) -I$(LAB_DIR) -Ilab -I. $< -o $@
$(BUILD)/$(LAB_DIR)/bench_counts: lab/tests/bench_counts.cpp $(LAB_HEADERS) lab/avl_map.h | $(BUILD)/$(LAB_DIR)
$(CXX) $(BENCHFLAGS) -I$(LAB_DIR) -Ilab -I. $< -o $@
$(BUILD)/$(LAB_DIR)/bench_times: lab/tests/bench_times.cpp $(LAB_HEADERS) lab/avl_map.h bench.h | $(BUILD)/$(LAB_DIR)
$(CXX) $(BENCHFLAGS) -I$(LAB_DIR) -Ilab -I. $< -o $@
$(BUILD)/$(LAB_DIR)/bench_words: lab/tests/bench_words.cpp $(LAB_HEADERS) lab/avl_map.h bench.h | $(BUILD)/$(LAB_DIR)
$(CXX) $(BENCHFLAGS) -I$(LAB_DIR) -Ilab -I. $< -o $@
$(BUILD) $(BUILD)/$(LAB_DIR):
mkdir -p $@
lab/avl_map.h:
@echo "Falta lab/avl_map.h: copien aquí el avl_map.h que terminaron en la semana 11."
@exit 1
lab: $(BUILD)/$(LAB_DIR)/map_tests $(BUILD)/$(LAB_DIR)/bench_counts $(BUILD)/$(LAB_DIR)/bench_times $(BUILD)/$(LAB_DIR)/bench_words
# Si existe solution/, también se comprueba la solución del laboratorio.
test: all
@if [ -d solution ]; then $(MAKE) --no-print-directory LAB_DIR=solution lab; fi
DATA=$(DATA) python3 -m unittest discover -p 'test_*.py'
test-base: all lab
LAB_DIR=$(LAB_DIR) python3 -m unittest -v test_lab.TestBase
test-rotations: all lab
LAB_DIR=$(LAB_DIR) python3 -m unittest -v test_lab.TestRotations
test-check: all lab
LAB_DIR=$(LAB_DIR) python3 -m unittest -v test_lab.TestCheck
test-insert: all lab
LAB_DIR=$(LAB_DIR) python3 -m unittest -v test_lab.TestInsert
test-measure: all lab
LAB_DIR=$(LAB_DIR) python3 -m unittest -v test_lab.TestMeasure
test-lab: all lab
LAB_DIR=$(LAB_DIR) python3 -m unittest -v test_lab
bench-counts: $(BUILD)/$(LAB_DIR)/bench_counts
$<
bench-times: $(BUILD)/$(LAB_DIR)/bench_times
@for map in avl rn std; do \
echo $$map; \
printf '%9s%10s%10s%10s%10s\n' n ins.orden bus.orden ins.azar bus.azar; \
for n in 16000 64000 256000 1024000; do $< $$map $$n || exit 1; done; \
done
bench-words: $(BUILD)/$(LAB_DIR)/bench_words
@for map in avl rn std; do $< $(DATA)/palabras.txt $$map || exit 1; done
clean:
rm -rf $(BUILD) __pycache__