Caso real

Los árboles de la biblioteca estándar

Los diccionarios y conjuntos ordenados de la biblioteca estándar de C++ (map y set) son, en las implementaciones habituales, árboles binarios de búsqueda balanceados (rojinegros). Rust eligió otra cosa: BTreeMap es un B-tree, con muchas claves por nodo. Los dos dan un diccionario ordenado; la diferencia está en la memoria, como verás en el último tema de la unidad.

Un diccionario ordenado responde dos cosas que una tabla hash no sabe: cuál es el siguiente en orden y qué claves hay entre a y b. ¿Qué pasa cuando un calendario con 100 000 citas, con altas y cancelaciones a cualquier hora, tiene que contestar «¿cuál es la primera cita después de las 15:00?» miles de veces por segundo?