Как устроены std::set и std::map в C++ на низком уровне?

В C++ std::set и std::map обычно реализуются с использованием сбалансированных бинарных деревьев поиска, чаще всего красно-черных деревьев.

Красно-черное дерево:

Это самобалансирующееся бинарное дерево поиска, которое поддерживает порядок элементов и обеспечивает логарифмическую сложность для большинства операций (вставка, удаление, поиск).

Основные свойства красно-черного дерева:

1. Каждый узел имеет цвет: красный или черный.
2. Корень дерева всегда черный.
3. Листья (нулевые узлы) всегда черные.
4. Красный узел не может иметь красного потомка.
5. Все простые пути от любого узла до листьев, входящих в поддерево этого узла, содержат одинаковое количество черных узлов.

Как это применяется в std::set и std::map:

• std::set: Хранит уникальные элементы в отсортированном порядке. Каждый узел дерева содержит сам элемент. Сравнение элементов используется для определения порядка в дереве.

  c

• std::map: Хранит пары "ключ-значение". Элементы сортируются по ключу. Каждый уз