К какой категории структур данных относится красно-черное дерево?

Красно-черное дерево относится к категории самобалансирующихся бинарных деревьев поиска (Binary Search Tree, BST).

Ключевые характеристики:

• Гарантирует логарифмическую высоту дерева (O(log n)) за счет набора правил балансировки.
• Каждый узел имеет «цвет» (красный или черный), что обеспечивает соблюдение инвариантов:
  1. Корень всегда черный.
  2. Все листья (NIL) черные.
  3. У красного узла оба потомка черные.
  4. Все простые пути от любого узла до его листьев содержат одинаковое количество черных узлов.
• Используется для реализации ассоциативных массивов (например, java.util.TreeMap в Java).

Пример (логическая структура):

        B(8)
       /     
    R(4)     R(12)
   /        /   
 B(2) B(6) B(10) B(14)

Где B — черный узел, R — красный узел. Эта структура обеспечивает эффективные операции вставки, удаления и поиска (O(log n)).