Какая скорость доступа в красно-черном дереве

Красно-черное дерево — это самобалансирующееся бинарное дерево поиска, гарантирующее логарифмическую скорость операций.

Сложность доступа:

• Вставка, удаление, поиск: O(log n) в худшем случае.
• Балансировка: O(1) для поворотов и перекрашиваний (локальные операции).

Пример:

TreeMap<Integer, String> tree = new TreeMap<>(); // Реализация на основе красно-черного дерева
tree.put(1, "One");   // O(log n)
tree.get(1);          // O(log n)
tree.remove(1);       // O(log n)

Гарантированная высота дерева — 2*log₂(n+1), что обеспечивает стабильную производительность даже при неблагоприятных вставках.