Является ли красно-черное дерево бинарным деревом поиска?

Да, красно-черное дерево (Red-Black Tree, RBT) — это самобалансирующееся бинарное дерево поиска (BST). Оно удовлетворяет основному свойству BST: для любого узла все ключи в левом поддереве меньше, а в правом — больше ключа узла.

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

1. Бинарность: Каждый узел имеет не более двух потомков.
2. Цвет: Узел может быть красным или черным.
3. Корень и листья: Корень всегда черный. Листья (NIL-узлы) считаются черными.
4. Ограничение на красные узлы: У красного узла оба потомка должны быть черными (красные узлы не могут быть соседями по вертикали).
5. Черная высота: Все простые пути от узла до листьев содержат одинаковое количество черных узлов (гарантирует логарифмическую высоту).

Пример структуры узла на Java:

class RBNode<K extends Comparable<K>, V> {
    K key;
    V value;
    RBNode<K, V> left, right, parent;
    boolean color; // true = RED, false = BLACK

    RBNode(K key, V value) {
        this.key = key;
        this.value = value;
        this.color = RED; // Новые узлы обычно вставляются красными
    }
}

Эти свойства обеспечивают балансировку, поэтому операции поиска, вставки и удаления выполняются за O(log n) в худшем случае.