Semana 11 — Árboles AVL
Objetivos
- Explicar por qué la condición de balance de AVL limita la altura.
- Aplicar rotaciones simples y dobles a mano.
- Mantener balanceado un árbol de búsqueda al insertar y al borrar.
Teoría — Árboles AVL: rotaciones y altura
Lectura: Apuntes, semana 11.
Apoyo: Open Data Structures, sec. 9.4 (Discussion and Exercises), que menciona los árboles AVL y los propone como ejercicio. Sobre AVL los apuntes son el texto principal.
Temas:
- El problema de la semana pasada: una altura de n. La idea: reparar un poco en cada operación.
- La condición AVL: en cada nodo, las alturas de sus dos subárboles difieren en 1 como máximo.
- Por qué la altura es O(log n): el AVL con menos nodos para una altura h cumple N(h) = N(h−1) + N(h−2) + 1, que crece como Fibonacci, así que la altura es, como máximo, de unos 1.44 log₂ n.
- Rotación: cambia la forma y conserva el orden en que se recorren las claves.
- Los cuatro casos: izquierda-izquierda, derecha-derecha, izquierda-derecha y derecha-izquierda. Rotación simple y doble.
- Insertar: subir desde el nodo nuevo, actualizar alturas y reparar. Basta una reparación, simple o doble.
- Borrar: la misma idea, pero puede requerir una reparación por cada dos niveles, O(log n) en total.
- Guardar la altura en cada nodo, y la invariante que hay que revisar en las pruebas.
- Error común: rotar y no actualizar las alturas, o actualizar la del padre antes que la del hijo.
Laboratorio — Balancear el mapa con AVL
Esta semana una sesión es para la Práctica 3.
Sesión 1:
- Partir del mapa de la semana 10, que se da con la altura en cada nodo; quien quiera puede poner sus propios métodos. Escribir las rotaciones, con pruebas directas sobre árboles pequeños.
- Escribir la inserción con balance y ampliar
check_invariantscon la condición AVL. - Escribir el borrado con balance. Pasar las pruebas al azar contra
std::map. - Medir la altura insertando claves ordenadas y al azar, y compararla con la del árbol sin balance y con 1.44 log₂ n. Para ver el peor caso, usar los árboles de Fibonacci que arma el programa dado.
Sesión 2: Práctica 3.
Entregas
- Práctica 3: Tablas hash y árboles binarios de búsqueda. Ver
practicas/README.md.
Preguntas de repaso
- Inserten 1, 2, 3, 4, 5, 6 y 7 en un AVL vacío. Dibujen el árbol después de cada rotación.
- Inserten 30, 10 y 20 en un AVL vacío. ¿Qué caso se presenta? Dibujen las rotaciones.
- ¿Por qué una rotación no rompe el orden del árbol? Muéstrenlo con el recorrido en orden.
- ¿Cuál es la menor cantidad de nodos de un AVL de altura 4, si un solo nodo tiene altura 0?
- ¿Cuántas reparaciones puede necesitar una inserción? ¿Y un borrado?
Código de la semana
Compilar y probar dentro del contenedor del curso con make y make test.
Ejemplos (12)Errores (5)Pruebas (4)Laboratorio (4)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.
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <vector>
#include "avl_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(18) << "max.reparaciones" << std::setw(16) << "max.rotaciones" << "\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;
std::size_t max_repairs = 0;
long max_rotations = 0;
do {
AvlSet<int> tree;
for (int key : keys) {
long before = tree.rotations();
tree.insert(key);
max_repairs = std::max(max_repairs, tree.last_repairs().size());
max_rotations = std::max(max_rotations, tree.rotations() - before);
}
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::setw(18) << max_repairs << std::setw(16) << max_rotations << "\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// Tiempo de insertar y de buscar n enteros, con y sin balance. -O2 y mediana de 3.
// Los tiempos dependen de la máquina: lo que importa es la razón entre columnas.
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>
#include "avl_set.h"
#include "bench.h"
#include "plain_tree.h"
namespace {
template <typename Tree>
double insert_time(const std::vector<int>& keys) {
return median_seconds(3, [&] {
Tree tree;
for (int key : keys) {
tree.insert(key);
}
keep(tree.size());
});
}
template <typename Tree>
double search_time(const std::vector<int>& keys, const std::vector<int>& queries) {
Tree tree;
for (int key : keys) {
tree.insert(key);
}
return median_seconds(3, [&] {
long found = 0;
for (int key : queries) {
found += tree.contains(key) ? 1 : 0;
}
keep(found);
});
}
} // namespace
int main() {
std::cout << "Claves ordenadas: insertar (s)\n";
std::cout << std::setw(9) << "n" << std::setw(10) << "avl" << std::setw(10) << "sin.bal" << std::setw(9) << "x" << "\n";
for (int n = 1000; n <= 16000; n *= 2) {
std::vector<int> keys(n);
std::iota(keys.begin(), keys.end(), 0);
double plain = insert_time<PlainTree<int>>(keys);
double avl = insert_time<AvlSet<int>>(keys);
std::cout << std::setw(9) << n << std::fixed << std::setprecision(5) << std::setw(10) << avl
<< std::setw(10) << plain << std::setprecision(1) << std::setw(9) << plain / avl << std::endl;
}
std::cout << "Claves al azar: insertar y buscar todas (s)\n";
std::cout << std::setw(9) << "n" << std::setw(10) << "ins.avl" << std::setw(10) << "ins.sin" << std::setw(9) << "avl/sin"
<< std::setw(10) << "bus.avl" << std::setw(10) << "bus.sin" << std::setw(9) << "sin/avl" << "\n";
std::mt19937 random(11);
for (int n : {16000, 128000, 512000}) {
std::vector<int> keys(n);
std::iota(keys.begin(), keys.end(), 0);
std::shuffle(keys.begin(), keys.end(), random);
std::vector<int> queries = keys;
std::shuffle(queries.begin(), queries.end(), random);
double insert_plain = insert_time<PlainTree<int>>(keys);
double insert_avl = insert_time<AvlSet<int>>(keys);
double search_plain = search_time<PlainTree<int>>(keys, queries);
double search_avl = search_time<AvlSet<int>>(keys, queries);
std::cout << std::setw(9) << n << std::fixed << std::setprecision(5)
<< std::setw(10) << insert_avl << std::setw(10) << insert_plain << std::setprecision(2) << std::setw(9) << insert_avl / insert_plain
<< std::setprecision(5) << std::setw(10) << search_avl << std::setw(10) << search_plain << std::setprecision(2) << std::setw(9) << search_plain / search_avl << std::endl;
}
return 0;
}// Sigue un AVL operación por operación. Cada argumento es una clave que se inserta,
// o una clave con signo menos que se borra: avl_trace 30 10 20 -10
#include <cstdlib>
#include <iostream>
#include "avl_set.h"
int main(int argc, char** argv) {
AvlSet<int> tree;
for (int i = 1; i < argc; i++) {
int key = std::atoi(argv[i]);
bool insert = key >= 0;
if (insert) {
tree.insert(key);
} else {
tree.erase(-key);
}
tree.check_invariants();
std::cout << (insert ? "insertar " : "borrar ") << std::abs(key) << ": " << tree.shape() << "\n";
for (const auto& repair : tree.last_repairs()) {
std::cout << " reparo en " << repair.key << ": " << repair.kind << "\n";
}
}
std::cout << "altura " << tree.height() << ", rotaciones " << tree.rotations() << "\n";
return 0;
}// 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// El caso de la semana 10: palabras.txt viene ordenado. Con AVL ya no importa.
// Los tiempos dependen de la máquina. -O2, mediana de 3.
#include <algorithm>
#include <fstream>
#include <iostream>
#include <random>
#include <set>
#include <string>
#include <vector>
#include "avl_set.h"
#include "bench.h"
#include "plain_tree.h"
int main(int argc, char** argv) {
if (argc != 2) {
std::cerr << "uso: dictionary_avl palabras.txt\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::cout << "orden de bytes: " << (std::is_sorted(words.begin(), words.end()) ? "si" : "no") << "\n";
std::vector<std::string> shuffled = words;
std::mt19937 random(11);
std::shuffle(shuffled.begin(), shuffled.end(), random);
auto report_avl = [](const char* name, const std::vector<std::string>& keys) {
int height = 0;
long rotations = 0;
double seconds = median_seconds(3, [&] {
AvlSet<std::string> tree;
for (const std::string& key : keys) {
tree.insert(key);
}
height = tree.height();
rotations = tree.rotations();
});
std::cout << name << ": " << keys.size() << " palabras, altura " << height << ", rotaciones " << rotations
<< ", " << seconds << " s\n";
};
auto report_set = [](const char* name, const std::vector<std::string>& keys) {
double seconds = median_seconds(3, [&] {
std::set<std::string> tree(std::less<std::string>{});
for (const std::string& key : keys) {
tree.insert(key);
}
keep(tree.size());
});
std::cout << name << ": " << keys.size() << " palabras, " << seconds << " s\n";
};
report_avl("AVL, tal como vienen", words);
report_set("std::set, tal como vienen", words);
report_avl("AVL, barajadas", shuffled);
report_set("std::set, barajadas", shuffled);
int plain_height = 0;
double plain_seconds = median_seconds(3, [&] {
PlainTree<std::string> tree;
for (const std::string& key : shuffled) {
tree.insert(key);
}
plain_height = tree.height();
});
std::cout << "sin balance, barajadas: " << shuffled.size() << " palabras, altura " << plain_height << ", "
<< plain_seconds << " s\n";
return 0;
}// Árboles de Fibonacci: los AVL con menos nodos para cada altura.
// Un árbol de altura h tiene a la izquierda uno de altura h - 1, y a la derecha uno de altura h - 2.
#ifndef FIBONACCI_TREE_H
#define FIBONACCI_TREE_H
#include <cstddef>
#include <utility>
#include <vector>
// Cantidad mínima de nodos de un AVL de altura h.
inline long min_avl_nodes(int h) {
long before = 0; // la altura -1 no tiene nodos
long current = 1; // la altura 0 tiene uno
for (int i = 0; i < h; i++) {
long next = current + before + 1;
before = current;
current = next;
}
return current;
}
namespace fibonacci_detail {
struct Shape {
int left = -1;
int right = -1;
int key = 0;
};
// Arma la forma de altura h y numera las claves en orden, desde next_key.
inline int build(int h, std::vector<Shape>& nodes, int& next_key) {
if (h < 0) {
return -1;
}
int left = build(h - 1, nodes, next_key);
int key = next_key++;
int right = build(h - 2, nodes, next_key);
nodes.push_back({left, right, key});
return static_cast<int>(nodes.size()) - 1;
}
} // namespace fibonacci_detail
// Las claves 1, 2, ..., n de un árbol de Fibonacci de altura h, por niveles desde la raíz. Si se
// insertan en este orden en un AVL, cae cada una en su lugar y no hace falta ninguna rotación:
// cada árbol parcial es ese mismo árbol cortado en un nivel, y sigue balanceado.
inline std::vector<int> fibonacci_keys(int h) {
std::vector<fibonacci_detail::Shape> nodes;
int next_key = 1;
int root = fibonacci_detail::build(h, nodes, next_key);
std::vector<int> keys;
keys.reserve(nodes.size());
std::vector<int> level;
if (root >= 0) {
level.push_back(root);
}
while (!level.empty()) {
std::vector<int> next;
for (int index : level) {
keys.push_back(nodes[index].key);
if (nodes[index].left >= 0) {
next.push_back(nodes[index].left);
}
if (nodes[index].right >= 0) {
next.push_back(nodes[index].right);
}
}
level = std::move(next);
}
return keys;
}
#endif// La altura con y sin balance: conteos, no tiempos. Semillas fijas.
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>
#include "avl_set.h"
#include "plain_tree.h"
namespace {
std::vector<int> ascending(int n) {
std::vector<int> keys(n);
std::iota(keys.begin(), keys.end(), 0);
return keys;
}
int avl_height(const std::vector<int>& keys, double* mean_depth = nullptr) {
AvlSet<int> tree;
for (int key : keys) {
tree.insert(key);
}
if (mean_depth != nullptr) {
*mean_depth = static_cast<double>(tree.total_depth()) / keys.size();
}
return tree.height();
}
} // namespace
int main() {
std::cout << "Claves ordenadas\n";
std::cout << std::setw(9) << "n" << std::setw(7) << "log2n" << std::setw(8) << "1.44log"
<< std::setw(6) << "avl" << std::setw(9) << "sin.bal" << "\n";
for (int n = 1000; n <= 1024000; n *= 4) {
std::vector<int> keys = ascending(n);
double log_n = std::log2(n);
std::cout << std::setw(9) << n << std::fixed << std::setprecision(1) << std::setw(7) << log_n
<< std::setw(8) << 1.44 * log_n << std::setw(6) << avl_height(keys);
if (n <= 16000) {
PlainTree<int> plain;
for (int key : keys) {
plain.insert(key);
}
std::cout << std::setw(9) << plain.height();
} else {
std::cout << std::setw(9) << "-";
}
std::cout << "\n";
}
std::cout << "Claves al azar, tres semillas\n";
std::cout << std::setw(9) << "n" << std::setw(7) << "log2n" << std::setw(8) << "1.44log"
<< std::setw(5) << "a1" << std::setw(5) << "a2" << std::setw(5) << "a3" << std::setw(9) << "prof.avl"
<< std::setw(5) << "s1" << std::setw(5) << "s2" << std::setw(5) << "s3" << std::setw(9) << "prof.sin" << "\n";
for (int n = 1000; n <= 1024000; n *= 4) {
double log_n = std::log2(n);
std::cout << std::setw(9) << n << std::fixed << std::setprecision(1) << std::setw(7) << log_n
<< std::setw(8) << 1.44 * log_n;
int avl_heights[3];
int plain_heights[3];
double avl_depth = 0;
double plain_depth = 0;
for (int seed = 0; seed < 3; seed++) {
std::vector<int> keys = ascending(n);
std::mt19937 random(11 + seed);
std::shuffle(keys.begin(), keys.end(), random);
double depth = 0;
avl_heights[seed] = avl_height(keys, &depth);
avl_depth += depth / 3;
PlainTree<int> plain;
for (int key : keys) {
plain.insert(key);
}
auto [height, sum] = plain.height_and_depth();
plain_heights[seed] = height;
plain_depth += static_cast<double>(sum) / n / 3;
}
for (int height : avl_heights) {
std::cout << std::setw(5) << height;
}
std::cout << std::setprecision(2) << std::setw(9) << avl_depth;
for (int height : plain_heights) {
std::cout << std::setw(5) << height;
}
std::cout << std::setw(9) << plain_depth << "\n";
}
return 0;
}// El AVL con menos nodos para cada altura: la recurrencia, Fibonacci, y el árbol de verdad.
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include "avl_set.h"
#include "fibonacci_tree.h"
int main() {
const double log_phi = std::log((1 + std::sqrt(5.0)) / 2);
std::cout << std::setw(3) << "h" << std::setw(8) << "N(h)" << std::setw(9) << "F(h+3)-1"
<< std::setw(7) << "medida" << std::setw(5) << "rot" << std::setw(7) << "log2n"
<< std::setw(8) << "1.44log" << std::setw(8) << "cota" << "\n";
long fib_a = 1; // F(1)
long fib_b = 1; // F(2)
long fib_c = 2; // F(3), la que corresponde a h = 0
for (int h = 0; h <= 24; h++) {
long n = min_avl_nodes(h);
AvlSet<int> tree;
for (int key : fibonacci_keys(h)) {
tree.insert(key);
}
tree.check_invariants();
assert(static_cast<long>(tree.size()) == n);
double log_n = std::log2(static_cast<double>(n));
// La cota exacta, contando aristas: h < log_phi(n + 2) + log_phi(raíz de 5) - 3,
// es decir, h < 1.4405 log2(n + 2) - 1.3277.
double bound = std::log(static_cast<double>(n + 2)) / log_phi + std::log(std::sqrt(5.0)) / log_phi - 3;
if (h <= 12 || h % 4 == 0) {
std::cout << std::setw(3) << h << std::setw(8) << n << std::setw(9) << fib_c - 1
<< std::setw(7) << tree.height() << std::setw(5) << tree.rotations()
<< std::fixed << std::setprecision(2) << std::setw(7) << log_n
<< std::setw(8) << 1.44 * log_n << std::setw(8) << bound << "\n";
}
fib_a = fib_b;
fib_b = fib_c;
fib_c = fib_a + fib_b;
}
return 0;
}// Árbol binario de búsqueda sin ningún balance, para comparar. Solo inserta y mide.
// Es el BstSet de la semana 10, reducido a lo que usan las mediciones.
#ifndef PLAIN_TREE_H
#define PLAIN_TREE_H
#include <cstddef>
#include <utility>
#include <vector>
template <typename K>
class PlainTree {
struct Node {
K key;
Node* left = nullptr;
Node* right = nullptr;
};
public:
PlainTree() = default;
// Sin recursión: un árbol sin balance puede ser una cadena.
~PlainTree() {
std::vector<Node*> pending;
if (root_ != nullptr) {
pending.push_back(root_);
}
while (!pending.empty()) {
Node* node = pending.back();
pending.pop_back();
if (node->left != nullptr) {
pending.push_back(node->left);
}
if (node->right != nullptr) {
pending.push_back(node->right);
}
delete node;
}
}
PlainTree(const PlainTree&) = delete;
PlainTree& operator=(const PlainTree&) = delete;
bool insert(const K& key) {
Node** link = &root_;
while (*link != nullptr) {
if (key < (*link)->key) {
link = &(*link)->left;
} else if ((*link)->key < key) {
link = &(*link)->right;
} else {
return false;
}
}
*link = new Node{key};
size_++;
return true;
}
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;
}
std::size_t size() const { return size_; }
// Altura nivel por nivel, y la suma de las profundidades de todos los nodos: sin recursión.
std::pair<int, long> height_and_depth() const {
int levels = 0;
long depth_sum = 0;
std::vector<const Node*> level;
if (root_ != nullptr) {
level.push_back(root_);
}
while (!level.empty()) {
depth_sum += levels * static_cast<long>(level.size());
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, depth_sum};
}
int height() const { return height_and_depth().first; }
private:
Node* root_ = nullptr;
std::size_t size_ = 0;
};
#endif// Cuántas reparaciones y rotaciones hace cada operación: conteos, no tiempos. Semilla fija.
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>
#include "avl_set.h"
#include "fibonacci_tree.h"
namespace {
struct Totals {
long operations = 0;
long repairs = 0;
long rotations = 0;
std::size_t max_repairs = 0;
};
void print_row(const char* name, int n, const Totals& totals, int bound) {
std::cout << std::setw(14) << name << std::setw(9) << n << std::fixed << std::setprecision(3)
<< std::setw(10) << static_cast<double>(totals.repairs) / totals.operations
<< std::setw(10) << static_cast<double>(totals.rotations) / totals.operations
<< std::setw(6) << totals.max_repairs << std::setw(7) << bound << "\n";
}
void insert_all(AvlSet<int>& tree, const std::vector<int>& keys, Totals& totals) {
for (int key : keys) {
long before = tree.rotations();
tree.insert(key);
totals.operations++;
totals.repairs += static_cast<long>(tree.last_repairs().size());
totals.rotations += tree.rotations() - before;
totals.max_repairs = std::max(totals.max_repairs, tree.last_repairs().size());
}
}
// Borra todas las claves, y anota la mayor cantidad de reparaciones permitida por h / 2.
void erase_all(AvlSet<int>& tree, const std::vector<int>& keys, Totals& totals, int& worst_bound) {
worst_bound = tree.height() / 2;
for (int key : keys) {
int height_before = tree.height();
long before = tree.rotations();
tree.erase(key);
totals.operations++;
totals.repairs += static_cast<long>(tree.last_repairs().size());
totals.rotations += tree.rotations() - before;
totals.max_repairs = std::max(totals.max_repairs, tree.last_repairs().size());
if (static_cast<int>(tree.last_repairs().size()) > height_before / 2) {
std::cout << "se paso de h / 2\n";
}
}
}
} // namespace
int main() {
std::cout << std::setw(14) << "operacion" << std::setw(9) << "n" << std::setw(10) << "rep/op"
<< std::setw(10) << "rot/op" << std::setw(6) << "max" << std::setw(7) << "h/2" << "\n";
std::mt19937 random(2026);
for (int n : {1000, 32000, 1024000}) {
std::vector<int> sorted(n);
std::iota(sorted.begin(), sorted.end(), 0);
std::vector<int> shuffled = sorted;
std::shuffle(shuffled.begin(), shuffled.end(), random);
std::vector<int> erase_order = sorted;
std::shuffle(erase_order.begin(), erase_order.end(), random);
{
AvlSet<int> tree;
Totals insert_totals;
insert_all(tree, sorted, insert_totals);
print_row("insertar orden", n, insert_totals, tree.height() / 2);
}
AvlSet<int> tree;
Totals insert_totals;
insert_all(tree, shuffled, insert_totals);
print_row("insertar azar", n, insert_totals, tree.height() / 2);
Totals erase_totals;
int bound = 0;
erase_all(tree, erase_order, erase_totals, bound);
print_row("borrar azar", n, erase_totals, bound);
}
std::cout << "Borrar la clave mayor de un arbol de Fibonacci\n";
std::cout << std::setw(3) << "h" << std::setw(9) << "n" << std::setw(13) << "reparaciones"
<< std::setw(11) << "rotaciones" << std::setw(7) << "h/2" << std::setw(11) << "h despues" << "\n";
for (int h = 2; h <= 26; h += (h < 10 ? 1 : 4)) {
std::vector<int> keys = fibonacci_keys(h);
AvlSet<int> tree;
for (int key : keys) {
tree.insert(key);
}
long before = tree.rotations();
tree.erase(static_cast<int>(keys.size()));
tree.check_invariants();
std::cout << std::setw(3) << h << std::setw(9) << keys.size() << std::setw(13) << tree.last_repairs().size()
<< std::setw(11) << tree.rotations() - before << std::setw(7) << h / 2 << std::setw(11) << tree.height() << "\n";
}
return 0;
}// Una rotación cambia la forma y conserva el recorrido en orden.
#include <iostream>
#include <vector>
#include "avl_set.h"
// Deja a este programa rotar a mano, sin el resto de la reparación.
struct AvlSetAccess {
static void rotate_root_right(AvlSet<int>& tree) { tree.root_ = tree.rotate_right(tree.root_); }
static void rotate_root_left(AvlSet<int>& tree) { tree.root_ = tree.rotate_left(tree.root_); }
};
void show(const char* title, const AvlSet<int>& tree) {
std::cout << title << ": " << tree.shape() << "\n en orden:";
for (int key : tree.in_order()) {
std::cout << " " << key;
}
std::cout << "\n";
}
int main() {
AvlSet<int> tree;
for (int key : {40, 20, 60, 10, 30}) {
tree.insert(key);
}
show("inicio", tree);
AvlSetAccess::rotate_root_right(tree);
show("rotar a la derecha en 40", tree);
AvlSetAccess::rotate_root_left(tree);
show("rotar a la izquierda en 20", tree);
return 0;
}Errores
Ejemplos con errores a propósito: no compilan, fallan o dan un resultado incorrecto. Los apuntes explican cada uno.
// Un AVL de enteros con un error a propósito, elegido por el parámetro del template.
// Compárenlo con ../avl_set.h: cada error está marcado con su nombre.
#ifndef BROKEN_AVL_H
#define BROKEN_AVL_H
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <sstream>
#include <string>
enum class Bug { no_height_update, parent_before_child, single_on_zigzag, stop_after_first_repair };
template <Bug bug>
class BrokenAvl {
struct Node {
int key;
Node* left = nullptr;
Node* right = nullptr;
int height = 0;
};
public:
BrokenAvl() = default;
~BrokenAvl() { destroy(root_); }
BrokenAvl(const BrokenAvl&) = delete;
BrokenAvl& operator=(const BrokenAvl&) = delete;
void insert(int key) {
repaired_ = false;
root_ = insert_at(root_, key);
}
void erase(int key) {
repaired_ = false;
root_ = erase_at(root_, key);
}
// La altura de verdad, y no la guardada: baja por todo el árbol.
int real_height() const { return real_height_of(root_); }
int stored_height() const { return height_of(root_); }
std::string shape() const {
std::ostringstream out;
write_shape(root_, out);
return out.str();
}
void check_invariants() const { check(root_); }
private:
static int height_of(const Node* node) { return node != nullptr ? node->height : -1; }
static int balance_of(const Node* node) { return height_of(node->left) - height_of(node->right); }
static void update_height(Node* node) {
node->height = 1 + std::max(height_of(node->left), height_of(node->right));
}
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;
}
// Actualiza las alturas de los dos nodos de una rotación: el que bajó y el que subió.
static void after_rotation(Node* lowered, Node* raised) {
if constexpr (bug == Bug::no_height_update) {
// Error: se rota y no se actualiza ninguna altura.
(void)lowered;
(void)raised;
} else if constexpr (bug == Bug::parent_before_child) {
// Error: el que subió es ahora el padre, y se calcula con la altura vieja de su hijo.
update_height(raised);
update_height(lowered);
} else {
update_height(lowered);
update_height(raised);
}
}
Node* rebalance(Node* x) {
update_height(x);
int balance = balance_of(x);
if (std::abs(balance) <= 1) {
return x;
}
if constexpr (bug == Bug::stop_after_first_repair) {
// Error: "basta una reparación" vale al insertar, y no al borrar.
if (repaired_) {
return x;
}
}
repaired_ = true;
if (balance > 1) {
if constexpr (bug != Bug::single_on_zigzag) {
if (balance_of(x->left) < 0) {
Node* y = x->left;
x->left = rotate_left(y);
after_rotation(y, x->left);
}
}
Node* top = rotate_right(x);
after_rotation(x, top);
return top;
}
if constexpr (bug != Bug::single_on_zigzag) {
if (balance_of(x->right) > 0) {
Node* y = x->right;
x->right = rotate_right(y);
after_rotation(y, x->right);
}
}
Node* top = rotate_left(x);
after_rotation(x, top);
return top;
}
Node* insert_at(Node* node, int key) {
if (node == nullptr) {
return new Node{key};
}
if (key < node->key) {
node->left = insert_at(node->left, key);
} else if (node->key < key) {
node->right = insert_at(node->right, key);
} else {
return node;
}
return rebalance(node);
}
Node* erase_at(Node* node, int key) {
if (node == nullptr) {
return nullptr;
}
if (key < node->key) {
node->left = erase_at(node->left, key);
} else if (node->key < key) {
node->right = erase_at(node->right, key);
} else {
if (node->left == nullptr || node->right == nullptr) {
Node* child = node->left != nullptr ? node->left : node->right;
delete node;
return child;
}
const Node* next = node->right;
while (next->left != nullptr) {
next = next->left;
}
node->key = next->key;
node->right = erase_at(node->right, node->key);
}
return rebalance(node);
}
static int real_height_of(const Node* node) {
if (node == nullptr) {
return -1;
}
return 1 + std::max(real_height_of(node->left), real_height_of(node->right));
}
static void destroy(Node* node) {
if (node == nullptr) {
return;
}
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->left != nullptr || node->right != nullptr) {
out << "(";
write_shape(node->left, out);
out << ",";
write_shape(node->right, out);
out << ")";
}
}
// Vuelve a calcular cada altura desde los hijos, y la compara con la guardada.
static int check(const Node* node) {
if (node == nullptr) {
return -1;
}
int left = check(node->left);
int right = check(node->right);
assert(node->height == 1 + std::max(left, right));
assert(std::abs(left - right) <= 1);
return node->height;
}
Node* root_ = nullptr;
bool repaired_ = false;
};
#endif// Error a propósito: se rota y no se actualizan las alturas.
#include <iostream>
#include "broken_avl.h"
int main() {
std::cout << std::unitbuf;
BrokenAvl<Bug::no_height_update> small;
for (int key : {1, 2, 3}) {
small.insert(key);
}
std::cout << "con 1, 2, 3: " << small.shape() << ", altura guardada " << small.stored_height() << "\n";
BrokenAvl<Bug::no_height_update> tree;
for (int key = 1; key <= 1000; key++) {
tree.insert(key);
}
std::cout << "con 1000 claves ordenadas: altura real " << tree.real_height()
<< ", altura guardada " << tree.stored_height() << "\n";
tree.check_invariants();
std::cout << "check_invariants no vio nada\n";
return 0;
}// Error a propósito: tras rotar, se actualiza primero el nodo que subió, que ahora es el padre.
#include <iostream>
#include "broken_avl.h"
int main() {
std::cout << std::unitbuf;
BrokenAvl<Bug::parent_before_child> small;
for (int key : {1, 2, 3}) {
small.insert(key);
}
std::cout << "con 1, 2, 3: " << small.shape() << ", altura real " << small.real_height()
<< ", altura guardada " << small.stored_height() << "\n";
BrokenAvl<Bug::parent_before_child> tree;
for (int key = 1; key <= 1000; key++) {
tree.insert(key);
}
std::cout << "con 1000 claves ordenadas: altura real " << tree.real_height()
<< ", altura guardada " << tree.stored_height() << "\n";
tree.check_invariants();
std::cout << "check_invariants no vio nada\n";
return 0;
}// Error a propósito: en el caso izquierda-derecha se hace solo la rotación simple.
#include <iostream>
#include "broken_avl.h"
int main() {
std::cout << std::unitbuf;
BrokenAvl<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;
}// Error a propósito: tras la primera reparación ya no se repara más arriba.
// Al insertar nunca hace falta otra, así que el error solo aparece al borrar.
#include <iostream>
#include <random>
#include "../fibonacci_tree.h"
#include "broken_avl.h"
int main() {
std::cout << std::unitbuf;
BrokenAvl<Bug::stop_after_first_repair> random_tree;
std::mt19937 random(2026);
std::uniform_int_distribution<int> key_of(0, 100000);
for (int i = 0; i < 5000; i++) {
random_tree.insert(key_of(random));
random_tree.check_invariants();
}
std::cout << "5000 inserciones al azar: todas pasan check_invariants\n";
BrokenAvl<Bug::stop_after_first_repair> tree;
for (int key : fibonacci_keys(4)) {
tree.insert(key);
}
tree.check_invariants();
std::cout << "antes de borrar 12: " << tree.shape() << "\n";
tree.erase(12);
std::cout << "despues de borrar 12: " << 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 os
import pathlib
import subprocess
import unittest
HERE = pathlib.Path(__file__).parent
DATA = os.environ.get("DATA", "../../data")
WORDS = f"{DATA}/palabras.txt"
SAN = ["g++", "-Wall", "-Wextra", "-std=c++20", "-g", "-fsanitize=address,undefined"]
PHI = (1 + math.sqrt(5)) / 2
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 min_nodes(limit):
"""N(h) para h = 0..limit, con enteros de Python: no hay overflow."""
values = [1, 2]
while len(values) <= limit:
values.append(values[-1] + values[-2] + 1)
return values
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/avl_trace", "1", "2", "3", "-1"], ["build/rotation_demo"], ["build/min_nodes"], ["build/all_orders"]]:
with self.subTest(program=command[0]):
done = run(*command)
self.assertEqual(done.returncode, 0, done.stdout)
def test_every_order_needs_at_most_one_repair(self):
rows = run("build/all_orders").stdout.splitlines()[1:]
self.assertEqual(len(rows), 9)
for row in rows:
n, _, _, _, repairs, rotations = (int(field) for field in row.split())
self.assertLessEqual(repairs, 1)
self.assertLessEqual(rotations, 2)
if n >= 3:
self.assertEqual((repairs, rotations), (1, 2))
def test_repairs_and_heights_table(self):
lines = run("build/repair_counts").stdout.splitlines()
self.assertNotIn("se paso de h / 2", lines)
split = lines.index("Borrar la clave mayor de un arbol de Fibonacci")
for row in lines[1:split]:
fields = row.rsplit(None, 4)
maximum, bound = int(fields[3]), int(fields[4])
if row.lstrip().startswith("insertar"):
self.assertEqual(maximum, 1)
else:
self.assertLessEqual(maximum, bound)
for row in lines[split + 2:]:
h, _, repairs, rotations, half, after = (int(field) for field in row.split())
self.assertEqual(repairs, h // 2)
self.assertEqual(half, h // 2)
self.assertEqual(rotations, repairs)
self.assertEqual(after, h - 1)
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 = int(fields[0]), int(fields[3])
self.assertEqual(avl, math.floor(math.log2(n)))
if fields[4] != "-":
self.assertEqual(int(fields[4]), n - 1)
for row in lines[split + 2:]:
fields = row.split()
limit = float(fields[2])
for avl in fields[3:6]:
self.assertLess(int(avl), limit)
for plain in fields[7:10]:
self.assertGreater(int(plain), limit)
def test_dictionary_shape_is_counted(self):
lines = run("build/dictionary_avl", WORDS).stdout.splitlines()
self.assertEqual(lines[0], "orden de bytes: si")
self.assertIn("1045757 palabras, altura 19, rotaciones 1045737,", lines[1])
self.assertIn("1045757 palabras, altura 23,", lines[3])
self.assertIn("1045757 palabras, altura 49,", lines[5])
class HeightBound(unittest.TestCase):
"""Con enteros exactos, la cota que dicen los apuntes para los AVL más flacos."""
def test_min_nodes_is_fibonacci_minus_one(self):
nodes = min_nodes(400)
fib = [0, 1]
while len(fib) < 410:
fib.append(fib[-1] + fib[-2])
for h, n in enumerate(nodes):
self.assertEqual(n, fib[h + 3] - 1)
self.assertEqual(nodes[4], 12)
def test_exact_bound_holds_and_is_tight(self):
constant = 1 / math.log2(PHI)
shift = math.log(math.sqrt(5), PHI) - 3
self.assertAlmostEqual(constant, 1.4404, places=4)
self.assertAlmostEqual(shift, -1.3277, places=4)
for h, n in enumerate(min_nodes(1400)):
bound = constant * math.log2(n + 2) + shift
self.assertLess(h, bound + 1e-9)
if h >= 20:
self.assertLess(bound - h, 0.01)
def test_printed_constants_are_a_true_bound(self):
"""Los números tal como salen en los apuntes. Con 1.4404, redondeado hacia abajo, ya no vale."""
nodes = min_nodes(1400)
for h, n in enumerate(nodes):
self.assertLess(h, 1.4405 * math.log2(n + 2) - 1.3277)
self.assertGreater(18, 1.4404 * math.log2(nodes[18] + 2) - 1.3277)
def test_simple_bound_with_two(self):
for h, n in enumerate(min_nodes(1400)):
self.assertLess(h, 2 * math.log2(n + 1))
def test_rounded_constant_fails_only_for_huge_n(self):
"""1.44 es menor que la constante de verdad: h <= 1.44 log2 n termina fallando, muy lejos."""
nodes = min_nodes(5000)
failures = [h for h, n in enumerate(nodes) if h > 1.44 * math.log2(n)]
self.assertTrue(failures)
first = failures[0]
self.assertGreater(first, 4000)
digits = len(str(nodes[first]))
self.assertGreater(digits, 900)
# Desde ahí ya no vuelve a valer.
self.assertEqual(failures, list(range(first, len(nodes))))
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_height_update(self):
done = run(self.build("no_height_update"))
self.assertNotEqual(done.returncode, 0)
self.assertIn("Assertion", done.stdout)
self.assertNotIn("no vio nada", done.stdout)
def test_parent_before_child(self):
done = run(self.build("parent_before_child"))
self.assertNotEqual(done.returncode, 0)
self.assertIn("altura real 1, altura guardada 3", 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(_,30(20,_))", done.stdout)
def test_stop_after_first_repair(self):
done = run(self.build("stop_after_first_repair"))
self.assertNotEqual(done.returncode, 0)
self.assertIn("todas pasan check_invariants", done.stdout)
self.assertIn("Assertion", 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", "in_order_is_sorted",
"strings_as_keys", "only_needs_less_than", "no_objects_left_behind", "copy_is_independent", "self_assignment",
"move_leaves_empty_and_usable", "erase_absent", "random_against_map_links", "queries_still_work",
]
ROTATIONS = [
"update_height_from_children", "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_keeps_in_order", "rotate_leaves_heights_alone", "rotate_keeps_nodes_in_place",
"rotate_counts_rotations", "rotate_random_nodes",
]
INSERT = [
"check_accepts_healthy_trees", "case_left_left", "case_right_right", "case_left_right", "case_right_left",
"one_to_seven", "double_rotation_moves_subtrees", "repair_below_the_root", "sorted_height_is_floor_log2",
"subscript_balances", "subscript_reference_after_rotation", "repeated_key_changes_nothing",
"one_repair_per_insert", "fibonacci_needs_no_rotation", "pointers_survive_rotations",
"iterate_after_rotations", "comparisons_follow_height", "random_inserts_against_map",
]
BROKEN = [
"broken_deep_order", "broken_parent", "broken_size", "broken_stale_leaf_height",
"broken_stale_inner_height", "broken_root_height", "broken_real_imbalance",
]
ERASE = [
"erase_needs_single_rotation", "erase_needs_double_rotation", "erase_heavy_child_with_zero_balance",
"erase_zero_balance_uneven_grandchildren", "erase_two_children_repairs_from_successor", "erase_until_empty",
"erase_can_repair_many_levels", "erase_repairs_are_bounded", "random_against_map_with_balance",
"random_strings_with_balance", "copy_keeps_heights", "exact_shape_after_script",
]
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"(avl_map\.h|map_tests\.cpp):\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.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_avl"]:
(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: update_height, rotate_left y rotate_right."""
@unittest.skipUnless((HERE / LAB_DIR).is_dir(), f"no existe la carpeta {LAB_DIR}")
class TestInsert(LabCase):
"""Paso 2: la inserción con balance, y check_invariants con la condición AVL."""
@unittest.skipUnless((HERE / LAB_DIR).is_dir(), f"no existe la carpeta {LAB_DIR}")
class TestErase(LabCase):
"""Paso 3: el borrado con balance, contra std::map."""
add_cases(TestBase, BASE)
add_cases(TestRotations, ROTATIONS)
add_cases(TestInsert, INSERT)
add_broken(TestInsert, BROKEN)
add_cases(TestErase, ERASE)
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-11.md"
SLIDES = ROOT / "slides" / "week-11.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 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
for command, expected in split_commands(lines):
actual = clean_lines(run_shell(command))
checked += 1
if mark != SYSTEM_DEPENDENT:
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), 2)
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 AvlSet y de los árboles de Fibonacci: dirigidas, exhaustivas y al azar, contra std::set.
#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <random>
#include <set>
#include <string>
#include <vector>
#include "avl_set.h"
#include "fibonacci_tree.h"
#include "plain_tree.h"
namespace {
int floor_log2(long n) {
int result = 0;
while (n > 1) {
n /= 2;
result++;
}
return result;
}
AvlSet<int>* build(AvlSet<int>& tree, const std::vector<int>& keys) {
for (int key : keys) {
tree.insert(key);
tree.check_invariants();
}
return &tree;
}
void test_four_cases() {
struct Case {
std::vector<int> keys;
const char* kind;
long rotations;
};
const Case cases[] = {
{{30, 20, 10}, "izquierda-izquierda", 1},
{{10, 20, 30}, "derecha-derecha", 1},
{{30, 10, 20}, "izquierda-derecha", 2},
{{10, 30, 20}, "derecha-izquierda", 2},
};
for (const Case& one : cases) {
AvlSet<int> tree;
build(tree, one.keys);
assert(tree.shape() == "20(10,30)");
assert(tree.rotations() == one.rotations);
assert(tree.last_repairs().size() == 1);
assert(tree.last_repairs()[0].kind == one.kind);
}
}
void test_one_to_seven_is_perfect() {
AvlSet<int> tree;
build(tree, {1, 2, 3, 4, 5, 6, 7});
assert(tree.shape() == "4(2(1,3),6(5,7))");
assert(tree.rotations() == 4);
}
// La recurrencia, contra Fibonacci y contra el árbol de verdad.
void test_fibonacci_trees() {
long a = 1;
long b = 2;
for (int h = 0; h <= 20; h++) {
assert(min_avl_nodes(h) == b - 1);
long next = a + b;
a = b;
b = next;
std::vector<int> keys = fibonacci_keys(h);
assert(static_cast<long>(keys.size()) == min_avl_nodes(h));
AvlSet<int> tree;
for (int key : keys) {
tree.insert(key);
}
tree.check_invariants();
assert(tree.rotations() == 0);
assert(tree.height() == h);
}
assert(min_avl_nodes(4) == 12);
}
// Con claves ordenadas: altura exacta y rotaciones exactas, para muchos n.
void test_sorted_insertions_are_exact() {
AvlSet<int> up;
AvlSet<int> down;
for (int n = 1; n <= 5000; n++) {
up.insert(n);
down.insert(-n);
assert(up.height() == floor_log2(n));
assert(down.height() == floor_log2(n));
assert(up.rotations() == n - floor_log2(n) - 1);
assert(down.rotations() == n - floor_log2(n) - 1);
}
up.check_invariants();
down.check_invariants();
}
// Todos los órdenes de 8 claves: una reparación por inserción, y todos los borrados posibles.
void test_every_order_of_eight_keys() {
std::vector<int> keys(8);
std::iota(keys.begin(), keys.end(), 1);
do {
AvlSet<int> tree;
for (int key : keys) {
long before = tree.rotations();
tree.insert(key);
assert(tree.last_repairs().size() <= 1);
assert(tree.rotations() - before <= 2);
}
assert(tree.height() <= 3);
std::vector<int> sorted = tree.in_order();
assert(std::is_sorted(sorted.begin(), sorted.end()));
} while (std::next_permutation(keys.begin(), keys.end()));
}
void test_erase_cases() {
{
AvlSet<int> tree;
build(tree, {4, 2, 5, 1, 3});
tree.erase(5);
tree.check_invariants();
assert(tree.shape() == "2(1,4(3,_))");
assert(tree.last_repairs().size() == 1);
assert(tree.last_repairs()[0].kind == "izquierda-izquierda");
assert(tree.rotations() == 1);
}
{
AvlSet<int> tree;
build(tree, {5, 2, 10, 1, 8, 12, 7, 13});
assert(tree.rotations() == 0);
tree.erase(1);
tree.check_invariants();
assert(tree.shape() == "10(5(2,8(7,_)),12(_,13))");
}
{
AvlSet<int> tree;
build(tree, {5, 3, 8, 2, 4, 9, 1});
tree.erase(5);
tree.check_invariants();
assert(tree.shape() == "3(2(1,_),8(4,9))");
}
{
AvlSet<int> tree;
build(tree, {2, 1});
assert(!tree.erase(9));
assert(tree.erase(2));
assert(tree.erase(1));
tree.check_invariants();
assert(tree.empty());
assert(tree.height() == -1);
}
}
// La cascada: en un árbol de Fibonacci, borrar la clave mayor repara h / 2 veces.
void test_erase_cascade() {
for (int h = 1; h <= 20; h++) {
std::vector<int> keys = fibonacci_keys(h);
AvlSet<int> tree;
for (int key : keys) {
tree.insert(key);
}
tree.erase(static_cast<int>(keys.size()));
tree.check_invariants();
assert(static_cast<int>(tree.last_repairs().size()) == h / 2);
assert(tree.height() == h - 1);
}
}
void test_random_against_std_set() {
std::mt19937 random(20261111);
AvlSet<int> mine;
std::set<int> model;
for (int step = 0; step < 20000; step++) {
int key = static_cast<int>(random() % 500);
int height = mine.height();
if (random() % 2 == 0) {
assert(mine.insert(key) == model.insert(key).second);
assert(mine.last_repairs().size() <= 1);
} else {
assert(mine.erase(key) == (model.erase(key) == 1));
assert(static_cast<int>(mine.last_repairs().size()) <= height / 2);
}
mine.check_invariants();
assert(mine.size() == model.size());
assert(mine.contains(key) == (model.count(key) == 1));
}
std::vector<int> expected(model.begin(), model.end());
assert(mine.in_order() == expected);
}
void test_strings() {
std::mt19937 random(3);
AvlSet<std::string> mine;
std::set<std::string> model;
for (int step = 0; step < 3000; step++) {
std::string key;
for (int i = 0; i < 3; i++) {
key += static_cast<char>('a' + random() % 6);
}
if (step % 3 == 2) {
assert(mine.erase(key) == (model.erase(key) == 1));
} else {
assert(mine.insert(key) == model.insert(key).second);
}
mine.check_invariants();
}
std::vector<std::string> expected(model.begin(), model.end());
assert(mine.in_order() == expected);
}
void test_plain_tree_measures() {
PlainTree<int> tree;
for (int key = 0; key < 100; key++) {
tree.insert(key);
}
assert(tree.height() == 99);
assert(tree.height_and_depth().second == 99 * 100 / 2);
assert(tree.contains(50));
assert(!tree.contains(100));
assert(!tree.insert(50));
}
} // namespace
int main() {
test_four_cases();
test_one_to_seven_is_perfect();
test_fibonacci_trees();
test_sorted_insertions_are_exact();
test_every_order_of_eight_keys();
test_erase_cases();
test_erase_cascade();
test_random_against_std_set();
test_strings();
test_plain_tree_measures();
std::cout << "ok\n";
return 0;
}Laboratorio
Archivos de partida del laboratorio de la semana.
// 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# Informe del laboratorio
Peguen aquí la salida de `make bench` 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.
## Tabla
## Altura con claves ordenadas
¿Cuánto vale la altura del AVL frente a `log2n` y a `1.44log`? ¿Y la del árbol sin balance? ¿Por qué con claves
ordenadas el AVL queda tan por debajo de 1.44 log₂ n?
## El peor caso
En la última tabla, ¿qué tan cerca de 1.44 log₂ n llega la altura? ¿Por qué esos árboles son el peor caso, y qué
tan lejos queda ese peor caso de lo que dieron las claves al azar?
## Rotaciones y tiempo
¿Cuántas rotaciones por inserción hizo el AVL con claves ordenadas, y cuántas con claves al azar? ¿Cuánto más rápido
fue el AVL con claves ordenadas, y cómo cambia esa razón al duplicar n?// Mide su AvlMap: la altura, las rotaciones y el tiempo, frente al árbol sin balance.
// Las alturas y las rotaciones son conteos. Los tiempos dependen de la máquina.
// Compilar con -O2 y sin sanitizers.
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>
#include "avl_map.h"
#include "bench.h"
#include "fibonacci_tree.h"
#include "plain_tree.h"
namespace {
// Hasta aquí se mide el árbol sin balance con claves ordenadas: cuesta Θ(n²).
const int plain_limit = 16000;
std::vector<int> ascending(int n) {
std::vector<int> keys(n);
std::iota(keys.begin(), keys.end(), 0);
return keys;
}
struct AvlResult {
int height = 0;
long rotations = 0;
double seconds = 0;
};
AvlResult run_avl(const std::vector<int>& keys) {
AvlResult result;
result.seconds = median_seconds(3, [&] {
AvlMap<int, int> map;
for (int key : keys) {
map.insert(key, key);
}
result.height = map.height();
result.rotations = map.rotations();
});
return result;
}
int run_plain(const std::vector<int>& keys, double& seconds) {
int height = 0;
seconds = median_seconds(3, [&] {
PlainTree<int> tree;
for (int key : keys) {
tree.insert(key);
}
height = tree.height();
});
return height;
}
void print_avl_columns(const AvlResult& result, int n) {
std::cout << std::setw(7) << result.height << std::setprecision(3) << std::setw(8)
<< static_cast<double>(result.rotations) / n;
}
} // namespace
int main() {
std::cout << "Claves ordenadas\n";
std::cout << std::setw(9) << "n" << std::setw(7) << "log2n" << std::setw(8) << "1.44log" << std::setw(7) << "h.avl"
<< std::setw(8) << "rot/n" << std::setw(9) << "t.avl" << std::setw(9) << "h.sin" << std::setw(9) << "t.sin" << "\n";
for (int n = 1000; n <= 1024000; n *= 4) {
std::vector<int> keys = ascending(n);
double log_n = std::log2(n);
std::cout << std::setw(9) << n << std::fixed << std::setprecision(1) << std::setw(7) << log_n
<< std::setw(8) << 1.44 * log_n;
AvlResult avl = run_avl(keys);
print_avl_columns(avl, n);
std::cout << std::setprecision(4) << std::setw(9) << avl.seconds;
if (n <= plain_limit) {
double seconds = 0;
int height = run_plain(keys, seconds);
std::cout << std::setw(9) << height << std::setw(9) << seconds;
} else {
std::cout << std::setw(9) << "-" << std::setw(9) << "-";
}
std::cout << std::endl;
}
std::cout << "Claves al azar\n";
std::cout << std::setw(9) << "n" << std::setw(7) << "log2n" << std::setw(8) << "1.44log" << std::setw(7) << "h.avl"
<< std::setw(8) << "rot/n" << std::setw(9) << "t.avl" << std::setw(9) << "h.sin" << std::setw(9) << "t.sin" << "\n";
std::mt19937 random(11);
for (int n = 1000; n <= 1024000; n *= 4) {
std::vector<int> keys = ascending(n);
std::shuffle(keys.begin(), keys.end(), random);
double log_n = std::log2(n);
std::cout << std::setw(9) << n << std::fixed << std::setprecision(1) << std::setw(7) << log_n
<< std::setw(8) << 1.44 * log_n;
AvlResult avl = run_avl(keys);
print_avl_columns(avl, n);
std::cout << std::setprecision(4) << std::setw(9) << avl.seconds;
double seconds = 0;
int height = run_plain(keys, seconds);
std::cout << std::setw(9) << height << std::setw(9) << seconds << std::endl;
}
std::cout << "El peor caso: arboles de Fibonacci, armados insertando por niveles\n";
std::cout << std::setw(9) << "n" << std::setw(7) << "log2n" << std::setw(8) << "1.44log" << std::setw(7) << "h.avl"
<< std::setw(8) << "rot" << std::setw(8) << "h/log2n" << "\n";
for (int h = 4; h <= 24; h += 4) {
std::vector<int> keys = fibonacci_keys(h);
AvlMap<int, int> map;
for (int key : keys) {
map.insert(key, key);
}
double log_n = std::log2(static_cast<double>(keys.size()));
std::cout << std::setw(9) << keys.size() << std::fixed << std::setprecision(1) << std::setw(7) << log_n
<< std::setw(8) << 1.44 * log_n << std::setw(7) << map.height() << std::setw(8) << map.rotations()
<< std::setprecision(2) << std::setw(8) << map.height() / log_n << "\n";
}
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 <iterator>
#include <map>
#include <random>
#include <string>
#include <utility>
#include <vector>
#include "avl_map.h"
#include "fibonacci_tree.h"
// Deja a las pruebas ver el árbol por dentro, rotar a mano y dañarlo.
struct AvlMapTestAccess {
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); }
template <typename Map, typename Node>
static void update_height(Map&, Node* node) { Map::update_height(node); }
};
using Access = AvlMapTestAccess;
namespace {
using IntMap = AvlMap<int, int>;
using Keys = std::vector<int>;
// Clave que solo se puede comparar con <, y que cuenta las comparaciones.
struct LessOnly {
int value = 0;
inline static long comparisons = 0;
bool operator<(const LessOnly& other) const {
comparisons++;
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;
}
int floor_log2(long n) {
int result = 0;
while (n > 1) {
n /= 2;
result++;
}
return result;
}
// Revisa el árbol por su cuenta, sin usar check_invariants ni las alturas guardadas.
// Devuelve la altura real. Si check_heights, además exige alturas correctas y balance.
template <typename Node, typename K>
int verify_node(const Node* node, const K* low, const K* high, std::size_t& count, bool check_heights) {
if (node == nullptr) {
return -1;
}
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);
int left = verify_node(node->left, low, &node->key, count, check_heights);
int right = verify_node(node->right, &node->key, high, count, check_heights);
int height = 1 + std::max(left, right);
if (check_heights) {
assert(node->height == height);
assert(std::abs(left - right) <= 1);
}
return height;
}
// Para las pruebas del mapa de partida y de las rotaciones: orden, padres, raíz y tamaño.
template <typename K, typename V>
void verify_links(const AvlMap<K, V>& map) {
const auto* root = Access::root(map);
assert(root == nullptr || root->parent == nullptr);
std::size_t count = 0;
verify_node(root, static_cast<const K*>(nullptr), static_cast<const K*>(nullptr), count, false);
assert(count == map.size());
}
// Todo lo anterior, más cada altura guardada y la condición AVL.
template <typename K, typename V>
void verify_avl(const AvlMap<K, V>& map) {
const auto* root = Access::root(map);
assert(root == nullptr || root->parent == nullptr);
std::size_t count = 0;
verify_node(root, static_cast<const K*>(nullptr), static_cast<const K*>(nullptr), count, true);
assert(count == map.size());
}
template <typename K, typename V>
void assert_same_as_model(const AvlMap<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);
}
// Inserta las claves, que no provocan ninguna rotación, y comprueba que así fue.
IntMap make_without_rotations(const Keys& keys) {
IntMap map = make_map(keys);
assert(map.rotations() == 0);
return map;
}
// ---- 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.find(1) == nullptr);
assert(map.in_order_keys().empty());
assert(map.rotations() == 0);
assert(map.repairs() == 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_in_order_is_sorted() {
IntMap map = make_map({5, 3, 8, 1, 4, 7});
assert((map.in_order_keys() == Keys{1, 3, 4, 5, 7, 8}));
}
void test_strings_as_keys() {
AvlMap<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() {
AvlMap<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.erase(LessOnly{2}));
assert(map.find(LessOnly{2}) == nullptr);
verify_links(map);
}
void test_no_objects_left_behind() {
{
AvlMap<int, Live> map;
for (int i = 0; i < 100; i++) {
map.insert((i * 37) % 101, Live(i));
}
assert(Live::count == 100);
for (int i = 0; i < 100; i += 2) {
assert(map.erase((i * 37) % 101));
}
assert(Live::count == 50);
}
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(copy.pre_order_keys() == original.pre_order_keys());
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(assigned.pre_order_keys() == original.pre_order_keys());
}
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_erase_absent() {
IntMap map = make_map({2, 1, 3});
assert(!map.erase(9));
assert(map.size() == 3);
IntMap empty;
assert(!empty.erase(1));
verify_links(map);
}
// Esta no mira el balance: comprueba el mapa como mapa.
void test_random_against_map_links() {
std::mt19937 random(20261110);
IntMap mine;
std::map<int, int> model;
for (int step = 0; step < 4000; step++) {
int key = static_cast<int>(random() % 200);
int action = static_cast<int>(random() % 10);
if (action < 5) {
assert(mine.insert(key, step) == model.insert({key, step}).second);
} else if (action < 9) {
assert(mine.erase(key) == (model.erase(key) == 1));
} 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());
if (step % 20 == 0) {
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;
int sum = 0;
for (auto [key, value] : map) {
keys.push_back(key);
sum += value;
}
assert((keys == Keys{5, 10, 15, 20, 25, 30, 35}));
assert(sum == 1400);
const IntMap& reader = map;
int count = 0;
for (const auto& entry : reader) {
count += entry.key > 0 ? 1 : 0;
}
assert(count == 7);
}
// ---- Paso 1: altura y rotaciones ----
// Los árboles se arman en un orden que no provoca rotaciones, así que estas pruebas valen antes y
// después del paso 2. Tras rotar a mano, el árbol puede no ser AVL: no llamen a check_invariants.
void test_update_height_from_children() {
IntMap map = make_without_rotations({4, 2, 6, 1});
auto* one = Access::node(map, 1);
auto* two = Access::node(map, 2);
auto* six = Access::node(map, 6);
auto* four = Access::node(map, 4);
Access::update_height(map, one);
assert(one->height == 0);
Access::update_height(map, six);
assert(six->height == 0);
Access::update_height(map, two);
assert(two->height == 1);
Access::update_height(map, four);
assert(four->height == 2);
// Usa las alturas guardadas de los hijos: no baja a recalcular.
one->height = 7;
Access::update_height(map, two);
assert(two->height == 8);
one->height = 0;
Access::update_height(map, two);
assert(two->height == 1);
}
void test_rotate_right_at_root() {
IntMap map = make_without_rotations({4, 2, 6, 1, 3, 5, 7});
auto* two = Access::node(map, 2);
auto* raised = Access::rotate_right(map, Access::root(map));
assert(raised == two);
assert(Access::root(map) == two);
assert(two->parent == nullptr);
verify_links(map);
assert((map.pre_order_keys() == Keys{2, 1, 4, 3, 6, 5, 7}));
}
void test_rotate_left_at_root() {
IntMap map = make_without_rotations({4, 2, 6, 1, 3, 5, 7});
auto* six = Access::node(map, 6);
auto* raised = Access::rotate_left(map, Access::root(map));
assert(raised == six);
assert(Access::root(map) == six);
assert(six->parent == nullptr);
verify_links(map);
assert((map.pre_order_keys() == Keys{6, 4, 2, 1, 3, 5, 7}));
}
// El nodo que se rota es hijo izquierdo de alguien: hay que cambiar el enlace de ese padre.
void test_rotate_under_left_link() {
IntMap map = make_without_rotations({4, 2, 6, 1, 3, 5, 7});
auto* four = Access::node(map, 4);
Access::rotate_left(map, Access::node(map, 2));
verify_links(map);
assert(four->left == Access::node(map, 3));
assert((map.pre_order_keys() == Keys{4, 3, 2, 1, 6, 5, 7}));
Access::rotate_right(map, Access::node(map, 3));
verify_links(map);
assert((map.pre_order_keys() == Keys{4, 2, 1, 3, 6, 5, 7}));
}
// Igual, por el enlace derecho.
void test_rotate_under_right_link() {
IntMap map = make_without_rotations({4, 2, 6, 1, 3, 5, 7});
auto* four = Access::node(map, 4);
Access::rotate_right(map, Access::node(map, 6));
verify_links(map);
assert(four->right == Access::node(map, 5));
assert((map.pre_order_keys() == Keys{4, 2, 1, 3, 5, 6, 7}));
Access::rotate_left(map, Access::node(map, 5));
verify_links(map);
assert((map.pre_order_keys() == Keys{4, 2, 1, 3, 6, 5, 7}));
}
// El subárbol del medio cambia de padre: es el enlace que más se olvida.
void test_rotate_moves_middle_subtree() {
IntMap map = make_without_rotations({4, 2, 6, 1, 3, 5, 7});
auto* three = Access::node(map, 3);
auto* four = Access::node(map, 4);
Access::rotate_right(map, four);
assert(four->left == three);
assert(three->parent == four);
IntMap other = make_without_rotations({4, 2, 6, 1, 3, 5, 7});
auto* five = Access::node(other, 5);
auto* other_four = Access::node(other, 4);
Access::rotate_left(other, other_four);
assert(other_four->right == five);
assert(five->parent == other_four);
}
// Sin subárbol del medio: no hay padre que arreglar, y un acceso a él sería un error.
void test_rotate_without_middle_subtree() {
IntMap left = make_without_rotations({4, 2, 6, 1});
Access::rotate_right(left, Access::node(left, 2));
verify_links(left);
assert((left.pre_order_keys() == Keys{4, 1, 2, 6}));
IntMap right = make_without_rotations({4, 2, 6, 7});
Access::rotate_left(right, Access::node(right, 6));
verify_links(right);
assert((right.pre_order_keys() == Keys{4, 2, 7, 6}));
}
void test_rotate_keeps_in_order() {
IntMap map = make_without_rotations({4, 2, 6, 1, 3, 5, 7});
Keys sorted = map.in_order_keys();
for (int key : {4, 2, 6}) {
Access::rotate_left(map, Access::node(map, key));
verify_links(map);
assert(map.in_order_keys() == sorted);
// Tras subir su hijo derecho, key es hijo izquierdo de él: se puede deshacer.
Access::rotate_right(map, Access::node(map, key)->parent);
verify_links(map);
assert(map.in_order_keys() == sorted);
assert((map.pre_order_keys() == Keys{4, 2, 1, 3, 6, 5, 7}));
}
}
// Las rotaciones no tocan las alturas: la semana 12 las usa en un árbol sin ellas.
void test_rotate_leaves_heights_alone() {
IntMap map = make_without_rotations({4, 2, 6, 1, 3, 5, 7});
int mark = 100;
for (int key : {1, 2, 3, 4, 5, 6, 7}) {
Access::node(map, key)->height = mark + key;
}
Access::rotate_left(map, Access::node(map, 4));
Access::rotate_right(map, Access::node(map, 6));
for (int key : {1, 2, 3, 4, 5, 6, 7}) {
assert(Access::node(map, key)->height == mark + key);
}
}
// Cada nodo sigue siendo el mismo, con su contenido: solo cambian los enlaces.
void test_rotate_keeps_nodes_in_place() {
IntMap map = make_without_rotations({4, 2, 6, 1, 3, 5, 7});
int* value_of_four = map.find(4);
int* value_of_six = map.find(6);
Access::rotate_left(map, Access::node(map, 4));
assert(map.find(4) == value_of_four);
assert(map.find(6) == value_of_six);
assert(*map.find(6) == 60);
}
void test_rotate_counts_rotations() {
IntMap map = make_without_rotations({4, 2, 6, 1, 3, 5, 7});
assert(map.repairs() == 0);
Access::rotate_left(map, Access::node(map, 4));
assert(map.rotations() == 1);
Access::rotate_right(map, Access::node(map, 6));
assert(map.rotations() == 2);
assert(map.repairs() == 0);
}
// Muchas rotaciones seguidas sobre nodos elegidos al azar.
void test_rotate_random_nodes() {
IntMap map;
std::mt19937 random(99);
for (int key : fibonacci_keys(8)) {
map.insert(key, key);
}
Keys sorted = map.in_order_keys();
assert(sorted.size() == 88);
for (int i = 0; i < 2000; i++) {
auto* node = Access::node(map, sorted[random() % sorted.size()]);
if (random() % 2 == 0) {
if (node->right != nullptr) {
Access::rotate_left(map, node);
}
} else if (node->left != nullptr) {
Access::rotate_right(map, node);
}
verify_links(map);
}
assert(map.in_order_keys() == sorted);
}
// ---- Paso 2: insertar con balance, y check_invariants ----
void test_check_accepts_healthy_trees() {
IntMap empty;
empty.check_invariants();
IntMap map;
for (int key = 0; key < 200; key++) {
map.insert(key, key);
map.check_invariants();
}
}
void test_case_left_left() {
IntMap map = make_map({30, 20, 10});
verify_avl(map);
assert((map.pre_order_keys() == Keys{20, 10, 30}));
assert(map.rotations() == 1);
assert(map.repairs() == 1);
}
void test_case_right_right() {
IntMap map = make_map({10, 20, 30});
verify_avl(map);
assert((map.pre_order_keys() == Keys{20, 10, 30}));
assert(map.rotations() == 1);
assert(map.repairs() == 1);
}
void test_case_left_right() {
IntMap map = make_map({30, 10, 20});
verify_avl(map);
assert((map.pre_order_keys() == Keys{20, 10, 30}));
assert(map.rotations() == 2);
assert(map.repairs() == 1);
}
void test_case_right_left() {
IntMap map = make_map({10, 30, 20});
verify_avl(map);
assert((map.pre_order_keys() == Keys{20, 10, 30}));
assert(map.rotations() == 2);
assert(map.repairs() == 1);
}
void test_one_to_seven() {
IntMap map = make_map({1, 2, 3, 4, 5, 6, 7});
verify_avl(map);
assert((map.pre_order_keys() == Keys{4, 2, 1, 3, 6, 5, 7}));
assert(map.rotations() == 4);
assert(map.repairs() == 4);
assert(map.height() == 2);
}
// La rotación doble con subárboles de verdad: los dos hijos del nodo que sube cambian de padre.
void test_double_rotation_moves_subtrees() {
IntMap left_right = make_map({50, 20, 70, 10, 30, 25});
verify_avl(left_right);
assert((left_right.pre_order_keys() == Keys{30, 20, 10, 25, 50, 70}));
IntMap also = make_map({50, 20, 70, 10, 30, 35});
verify_avl(also);
assert((also.pre_order_keys() == Keys{30, 20, 10, 50, 35, 70}));
IntMap right_left = make_map({50, 20, 80, 70, 90, 75});
verify_avl(right_left);
assert((right_left.pre_order_keys() == Keys{70, 50, 20, 80, 75, 90}));
IntMap mirrored = make_map({50, 20, 80, 70, 90, 65});
verify_avl(mirrored);
assert((mirrored.pre_order_keys() == Keys{70, 50, 20, 65, 80, 90}));
}
// La reparación ocurre abajo: la raíz no cambia, y su enlace debe apuntar al nodo que subió.
void test_repair_below_the_root() {
IntMap map = make_map({10, 5, 20, 30, 40});
verify_avl(map);
assert((map.pre_order_keys() == Keys{10, 5, 30, 20, 40}));
IntMap other = make_map({10, 20, 5, 3, 1});
verify_avl(other);
assert((other.pre_order_keys() == Keys{10, 3, 1, 5, 20}));
}
void test_sorted_height_is_floor_log2() {
IntMap up;
IntMap down;
for (int i = 1; i <= 3000; i++) {
up.insert(i, i);
down.insert(-i, i);
assert(up.height() == floor_log2(i));
assert(down.height() == floor_log2(i));
}
verify_avl(up);
verify_avl(down);
}
// operator[] también inserta, así que también debe balancear.
void test_subscript_balances() {
IntMap map;
for (int i = 0; i < 1023; i++) {
map[i] = i;
}
verify_avl(map);
assert(map.height() == 9);
assert(map[500] == 500);
}
// La referencia que entrega operator[] sigue valiendo aunque esa inserción haya rotado.
void test_subscript_reference_after_rotation() {
IntMap map;
map[1] = 10;
map[2] = 20;
int& value = map[3];
assert(map.rotations() == 1);
value = 30;
assert(*map.find(3) == 30);
}
void test_repeated_key_changes_nothing() {
IntMap map = make_map({1, 2, 3, 4, 5});
long rotations = map.rotations();
Keys shape = map.pre_order_keys();
for (int key = 1; key <= 5; key++) {
assert(!map.insert(key, 0));
}
assert(map.rotations() == rotations);
assert(map.pre_order_keys() == shape);
verify_avl(map);
}
// Basta una reparación por inserción, y una reparación son 1 o 2 rotaciones.
void test_one_repair_per_insert() {
std::mt19937 random(2026);
IntMap map;
for (int i = 0; i < 20000; i++) {
long repairs = map.repairs();
long rotations = map.rotations();
map.insert(static_cast<int>(random() % 1000000), i);
assert(map.repairs() - repairs <= 1);
assert(map.rotations() - rotations <= 2);
assert((map.repairs() == repairs) == (map.rotations() == rotations));
}
verify_avl(map);
assert(map.repairs() > 1000);
}
// Insertado por niveles, un árbol de Fibonacci no necesita ninguna rotación. Reparar de más se nota.
void test_fibonacci_needs_no_rotation() {
for (int h = 0; h <= 12; h++) {
std::vector<int> keys = fibonacci_keys(h);
assert(static_cast<long>(keys.size()) == min_avl_nodes(h));
IntMap map;
for (int key : keys) {
map.insert(key, key);
}
verify_avl(map);
assert(map.height() == h);
assert(map.rotations() == 0);
}
}
void test_pointers_survive_rotations() {
IntMap map;
map.insert(1, 10);
int* value = map.find(1);
auto it = map.begin();
for (int key = 2; key <= 100; key++) {
map.insert(key, key * 10);
}
assert(map.rotations() > 0);
assert(map.find(1) == value);
assert(*value == 10);
++it;
assert((*it).key == 2);
}
void test_iterate_after_rotations() {
IntMap map;
for (int key = 500; key >= 1; key--) {
map.insert(key, key);
}
int expected = 1;
for (auto [key, value] : map) {
assert(key == expected);
assert(value == expected);
expected++;
}
assert(expected == 501);
}
void test_comparisons_follow_height() {
AvlMap<LessOnly, int> map;
for (int key = 0; key < 1023; key++) {
map.insert(LessOnly{key}, key);
}
assert(map.height() == 9);
for (int key : {0, 511, 1022, 300}) {
LessOnly::comparisons = 0;
assert(map.find(LessOnly{key}) != nullptr);
assert(LessOnly::comparisons <= 20);
}
}
void test_random_inserts_against_map() {
std::mt19937 random(7);
IntMap mine;
std::map<int, int> model;
for (int step = 0; step < 3000; step++) {
int key = static_cast<int>(random() % 5000);
assert(mine.insert(key, step) == model.insert({key, step}).second);
verify_avl(mine);
mine.check_invariants();
}
assert_same_as_model(mine, model);
}
// Cada una de estas daña un árbol sano. check_invariants debe detener el programa.
// test_lab.py exige ver "sano" y luego un fallo, así que no pasan sin check_invariants.
// Si no se detiene, se sale sin destruir: el fallo no debe venir del destructor sobre un árbol roto.
void healthy(const IntMap& map) {
map.check_invariants();
std::cout << "sano" << std::endl;
}
void test_broken_deep_order() {
IntMap map = make_map({5, 3, 8, 4});
healthy(map);
// 7 es mayor que su padre 3, como debe ser, pero está a la izquierda del 5.
Access::root(map)->left->right->key = 7;
map.check_invariants();
std::_Exit(0);
}
void test_broken_parent() {
IntMap map = make_map({5, 3, 8, 4});
healthy(map);
auto* root = Access::root(map);
root->left->right->parent = root;
map.check_invariants();
std::_Exit(0);
}
void test_broken_size() {
IntMap map = make_map({5, 3, 8});
healthy(map);
Access::add_to_size(map);
map.check_invariants();
std::_Exit(0);
}
// La altura guardada de una hoja está mal.
void test_broken_stale_leaf_height() {
IntMap map = make_map({5, 3, 8, 4});
healthy(map);
Access::node(map, 8)->height = 1;
map.check_invariants();
std::_Exit(0);
}
// La altura de un nodo interno está mal, y sin embargo la diferencia con su hermano es válida.
void test_broken_stale_inner_height() {
IntMap map = make_map({5, 3, 8, 1, 4, 7, 9});
healthy(map);
Access::node(map, 3)->height = 0;
map.check_invariants();
std::_Exit(0);
}
// Solo la altura de la raíz está mal: nadie por encima la usa para notar el error.
void test_broken_root_height() {
IntMap map = make_map({5, 3, 8});
healthy(map);
Access::root(map)->height = 5;
map.check_invariants();
std::_Exit(0);
}
// Todas las alturas son correctas y el árbol está desbalanceado: rompe solo la condición AVL.
void test_broken_real_imbalance() {
IntMap map = make_map({2, 1, 4, 3, 5});
healthy(map);
// Queda 2(1,3(_,4(_,5))): el 3 y la raíz tienen balance -2. Se ponen bien todas las alturas.
Access::rotate_right(map, Access::node(map, 4));
for (int key : {5, 4, 3, 1, 2}) {
Access::update_height(map, Access::node(map, key));
}
map.check_invariants();
std::_Exit(0);
}
// ---- Paso 3: borrar con balance ----
void test_erase_needs_single_rotation() {
IntMap right = make_map({5, 3, 7, 8});
assert(right.erase(3));
verify_avl(right);
assert((right.pre_order_keys() == Keys{7, 5, 8}));
IntMap left = make_map({5, 3, 7, 2});
assert(left.erase(7));
verify_avl(left);
assert((left.pre_order_keys() == Keys{3, 2, 5}));
assert(left.repairs() == 1);
}
void test_erase_needs_double_rotation() {
IntMap right_left = make_map({5, 2, 8, 7});
assert(right_left.erase(2));
verify_avl(right_left);
assert((right_left.pre_order_keys() == Keys{7, 5, 8}));
assert(right_left.rotations() == 2);
IntMap left_right = make_map({5, 2, 7, 3});
assert(left_right.erase(7));
verify_avl(left_right);
assert((left_right.pre_order_keys() == Keys{3, 2, 5}));
assert(left_right.rotations() == 2);
}
// El hijo pesado tiene balance 0, que solo pasa al borrar: va la rotación simple.
void test_erase_heavy_child_with_zero_balance() {
IntMap left = make_without_rotations({4, 2, 5, 1, 3});
assert(left.erase(5));
verify_avl(left);
assert((left.pre_order_keys() == Keys{2, 1, 4, 3}));
assert(left.rotations() == 1);
IntMap right = make_without_rotations({2, 1, 4, 3, 5});
assert(right.erase(1));
verify_avl(right);
assert((right.pre_order_keys() == Keys{4, 2, 3, 5}));
assert(right.rotations() == 1);
}
// Igual, con nietos de alturas distintas: aquí una rotación doble deja el árbol desbalanceado.
void test_erase_zero_balance_uneven_grandchildren() {
IntMap right = make_without_rotations({5, 2, 10, 1, 8, 12, 7, 13});
assert(right.erase(1));
verify_avl(right);
assert((right.pre_order_keys() == Keys{10, 5, 2, 8, 7, 12, 13}));
IntMap left = make_without_rotations({9, 5, 12, 2, 6, 13, 1, 7});
assert(left.erase(13));
verify_avl(left);
assert((left.pre_order_keys() == Keys{5, 2, 1, 9, 6, 7, 12}));
}
// La reparación debe empezar donde salió de verdad el nodo: el padre del sucesor.
void test_erase_two_children_repairs_from_successor() {
IntMap map = make_map({5, 3, 8, 2, 4, 9, 1});
assert(map.erase(5));
verify_avl(map);
assert((map.pre_order_keys() == Keys{3, 2, 1, 8, 4, 9}));
assert(*map.find(8) == 80);
assert(map.find(5) == nullptr);
IntMap deep = make_map({8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15, 16});
assert(deep.erase(8));
verify_avl(deep);
assert(*deep.find(9) == 90);
assert(deep.size() == 15);
}
void test_erase_until_empty() {
IntMap map = make_map({1, 2, 3, 4, 5, 6, 7, 8, 9});
for (int key = 9; key >= 1; key--) {
int top = map.pre_order_keys().front();
assert(map.erase(top));
verify_avl(map);
map.check_invariants();
assert(map.find(top) == nullptr);
}
assert(map.empty());
assert(map.height() == -1);
map.insert(1, 1);
verify_avl(map);
}
// Al borrar puede hacer falta reparar en todos los antepasados. No basta una, como al insertar.
void test_erase_can_repair_many_levels() {
for (int h = 2; h <= 16; h++) {
std::vector<int> keys = fibonacci_keys(h);
IntMap map;
for (int key : keys) {
map.insert(key, key);
}
assert(map.rotations() == 0);
assert(map.erase(static_cast<int>(keys.size())));
verify_avl(map);
assert(map.repairs() == h / 2);
assert(map.height() == h - 1);
}
}
// Con el árbol ya sano no se repara nada más, y nunca se pasa de h / 2 reparaciones.
void test_erase_repairs_are_bounded() {
std::mt19937 random(31);
IntMap map;
Keys keys;
for (int key = 0; key < 3000; key++) {
keys.push_back(key);
}
std::shuffle(keys.begin(), keys.end(), random);
for (int key : keys) {
map.insert(key, key);
}
std::shuffle(keys.begin(), keys.end(), random);
for (int key : keys) {
int height = map.height();
long repairs = map.repairs();
assert(map.erase(key));
long done = map.repairs() - repairs;
assert(done <= height / 2);
if (key % 50 == 0) {
verify_avl(map);
}
}
assert(map.empty());
}
void test_random_against_map_with_balance() {
std::mt19937 random(20261111);
IntMap mine;
std::map<int, int> model;
for (int step = 0; step < 6000; step++) {
int key = static_cast<int>(random() % 200);
int action = static_cast<int>(random() % 10);
if (action < 5) {
assert(mine.insert(key, step) == model.insert({key, step}).second);
} else if (action < 9) {
assert(mine.erase(key) == (model.erase(key) == 1));
} else {
const int* found = mine.find(key);
auto position = model.find(key);
assert((found != nullptr) == (position != model.end()));
assert(found == nullptr || *found == position->second);
}
verify_avl(mine);
mine.check_invariants();
assert(mine.size() == model.size());
if (step % 50 == 0) {
assert_same_as_model(mine, model);
}
}
assert_same_as_model(mine, model);
}
void test_random_strings_with_balance() {
std::mt19937 random(11);
auto word = [&] {
std::string text;
for (int i = 0; i < 3; i++) {
text += static_cast<char>('a' + random() % 6);
}
return text;
};
AvlMap<std::string, std::string> mine;
std::map<std::string, std::string> model;
for (int step = 0; step < 3000; step++) {
std::string key = word();
if (step % 3 != 2) {
std::string value = word() + "valor largo para el heap";
assert(mine.insert(key, value) == model.insert({key, value}).second);
} else {
assert(mine.erase(key) == (model.erase(key) == 1));
}
verify_avl(mine);
}
assert_same_as_model(mine, model);
}
// La copia lleva las alturas: copiar un nodo copia todos sus campos.
void test_copy_keeps_heights() {
std::mt19937 random(5);
IntMap mine;
for (int step = 0; step < 1000; step++) {
int key = static_cast<int>(random() % 100);
if (step % 3 == 0) {
mine.erase(key);
} else {
mine.insert(key, key);
}
}
IntMap copy(mine);
verify_avl(copy);
copy.check_invariants();
assert(copy.pre_order_keys() == mine.pre_order_keys());
for (int key = 100; key < 300; key++) {
copy.insert(key, key);
verify_avl(copy);
}
verify_avl(mine);
}
// La forma exacta tras una serie de operaciones: sucesor al borrar, y rotación simple con balance 0.
// La esperada sale del AvlSet de los apuntes, que es otra implementación.
void test_exact_shape_after_script() {
std::mt19937 random(424242);
IntMap map;
for (int step = 0; step < 300; step++) {
int key = static_cast<int>(random() % 64);
if (random() % 3 == 0) {
map.erase(key);
} else {
map.insert(key, key);
}
}
verify_avl(map);
Keys expected{38, 23, 11, 3, 1, 0, 2, 7, 8, 17, 13, 12, 16, 19, 18, 20, 22, 28, 25, 24, 27, 31, 30, 35, 36, 48, 43, 40, 39, 41, 46, 44, 45, 47, 56, 52, 50, 49, 51, 55, 53, 60, 58, 62, 61, 63};
assert(map.pre_order_keys() == expected);
}
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(in_order_is_sorted), 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(erase_absent),
TEST(random_against_map_links), TEST(queries_still_work),
TEST(update_height_from_children), 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_keeps_in_order), TEST(rotate_leaves_heights_alone),
TEST(rotate_keeps_nodes_in_place), TEST(rotate_counts_rotations), TEST(rotate_random_nodes),
TEST(check_accepts_healthy_trees), TEST(case_left_left), TEST(case_right_right), TEST(case_left_right),
TEST(case_right_left), TEST(one_to_seven), TEST(double_rotation_moves_subtrees), TEST(repair_below_the_root),
TEST(sorted_height_is_floor_log2), TEST(subscript_balances), TEST(subscript_reference_after_rotation),
TEST(repeated_key_changes_nothing), TEST(one_repair_per_insert), TEST(fibonacci_needs_no_rotation),
TEST(pointers_survive_rotations), TEST(iterate_after_rotations), TEST(comparisons_follow_height),
TEST(random_inserts_against_map), TEST(broken_deep_order), TEST(broken_parent), TEST(broken_size),
TEST(broken_stale_leaf_height), TEST(broken_stale_inner_height), TEST(broken_root_height),
TEST(broken_real_imbalance),
TEST(erase_needs_single_rotation), TEST(erase_needs_double_rotation), TEST(erase_heavy_child_with_zero_balance),
TEST(erase_zero_balance_uneven_grandchildren), TEST(erase_two_children_repairs_from_successor),
TEST(erase_until_empty), TEST(erase_can_repair_many_levels), TEST(erase_repairs_are_bounded),
TEST(random_against_map_with_balance), TEST(random_strings_with_balance), TEST(copy_keeps_heights),
TEST(exact_shape_after_script),
};
} // 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 11: árboles AVL. 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 del balance
# make test-rotations prueba update_height y las rotaciones (paso 1)
# make test-insert prueba la inserción con balance y check_invariants (paso 2)
# make test-erase prueba el borrado con balance, contra std::map (paso 3)
# make test-lab prueba todo su laboratorio; falla hasta que lo terminen
# make bench mide su mapa, con -O2 y sin sanitizers (paso 4)
# 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 = avl_trace rotation_demo min_nodes test_structures
BENCHES = all_orders height_table repair_counts avl_times dictionary_avl
COMMON_HEADERS = avl_set.h plain_tree.h fibonacci_tree.h bench.h
LAB_HEADERS = $(LAB_DIR)/avl_map.h lab/not_implemented.h fibonacci_tree.h
.PHONY: all lab test test-base test-rotations test-insert test-erase test-lab bench clean
all: $(PROGRAMS:%=$(BUILD)/%) $(BENCHES:%=$(BUILD)/%)
$(PROGRAMS:%=$(BUILD)/%): $(BUILD)/%: %.cpp $(COMMON_HEADERS) | $(BUILD)
$(CXX) $(CXXFLAGS) $< -o $@
# Las mediciones 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_avl: lab/tests/bench_avl.cpp $(LAB_HEADERS) plain_tree.h bench.h | $(BUILD)/$(LAB_DIR)
$(CXX) $(BENCHFLAGS) -I$(LAB_DIR) -Ilab -I. $< -o $@
$(BUILD) $(BUILD)/$(LAB_DIR):
mkdir -p $@
lab: $(BUILD)/$(LAB_DIR)/map_tests $(BUILD)/$(LAB_DIR)/bench_avl
# 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-insert: all lab
LAB_DIR=$(LAB_DIR) python3 -m unittest -v test_lab.TestInsert
test-erase: all lab
LAB_DIR=$(LAB_DIR) python3 -m unittest -v test_lab.TestErase
test-lab: all lab
LAB_DIR=$(LAB_DIR) python3 -m unittest -v test_lab
bench: $(BUILD)/$(LAB_DIR)/bench_avl
$<
clean:
rm -rf $(BUILD) __pycache__