Красно-чёрное дерево
Самобалансирующееся двоичное дерево поиска с инвариантами «цвета»: Рудольф Байер, 1972; название дал Леонидас Гибас (1978). Самый частый выбор в стандартных библиотеках.
Пять правил гарантируют глубину O(log n) без такой строгой балансировки, как в AVL. Итог: вставка и удаление быстрее, чем в AVL, поиск — чуть медленнее. Операции требуют поворотов и перекраски.
На нём построены std::map в C++, TreeMap/TreeSet в Java, Completely Fair Scheduler в Linux, epoll в Linux и многие реализации сетевого стека. Конкуренты: B-дерево (для диска), AVL (при преобладании поиска), список с пропусками (проще сделать без блокировок).