CS
Задачник Базовый курс EN

Задача

Проверка раскраски

дерево поиска дерево обход поиск в проде

Библиотека сбрасывает красно-чёрное дерево на диск: для каждого узла — ключ, цвет и номера детей. После сбоя часть файлов могла испортиться, и прежде чем загрузить файл, его надо проверить. Проверка идёт в таком порядке, и выводится первое найденное нарушение:

  1. ORDER — дерево не дерево поиска: у какого-то узла в левом поддереве есть ключ не меньше его ключа или в правом — не больше. Равные ключи тоже нарушение.
  2. ROOT — корень красный.
  3. RED — у красного узла есть красный ребёнок.
  4. BLACK — на путях от какого-то узла вниз до пустых ссылок разное число чёрных узлов.

Если нарушений нет, выведите OK и чёрную высоту — число чёрных узлов на любом пути от корня до пустой ссылки, считая корень. Третий и четвёртый тесты — целые деревья: 19 073 землетрясения каталога USGS, вставленные по порядку времени, и первые 20 000 разных слов «Войны и мира»; в других тестах такие же деревья, в том числе из адресов страниц legost.in, повреждены в одном месте. Ключ — десятикратное место исходного ключа по порядку.

Вход

В первой строке n и r (1 ≤ n ≤ 10⁵, 1 ≤ r ≤ n) — число узлов и номер корня. Дальше n строк: в i-й — ключ узла i (целое от 1 до 10⁹), его цвет (R или B) и номера левого и правого ребёнка, 0 — если ребёнка нет. Гарантируется, что это двоичное дерево с корнем r, в котором есть все n узлов.

Выход

Одно слово — ORDER, ROOT, RED или BLACK, — или OK и через пробел чёрную высоту.

Примеры

Пример 1

Вход
7 1
40 B 2 3
20 R 4 5
60 R 6 7
10 B 0 0
30 B 0 0
50 B 0 0
70 B 0 0
Выход
OK 2

Пример 2

Вход
5 1
40 B 2 3
20 R 4 5
60 B 0 0
10 B 0 0
30 R 0 0
Выход
RED

Ограничения

Время · Python
4000 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
12 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Каждое правило проверяется одним обходом дерева. Но правило поиска говорит обо всех ключах поддерева, а не только о детях: сравнить узел с его детьми мало.

2Подсказка 2

Спускаясь от корня, несите вниз границы: в левом поддереве узла с ключом k все ключи меньше k, в правом — больше. У корня границ нет, и каждый шаг вниз сужает одну из них. Чёрные высоты удобнее считать снизу вверх.

3Идея

Один обход сверху вниз с явным стеком: для каждого узла проверяем, что ключ строго внутри границ, переданных от предков, и запоминаем порядок обхода. Потом цвет корня, потом каждого красного узла с детьми. Потом проходим запомненный порядок задом наперёд — дети тогда идут раньше родителей — и считаем чёрную высоту: у пустой ссылки 0, у узла — общая высота детей плюс один, если узел чёрный; если у детей высоты разные, ответ BLACK.

4Разбор

Почему границ достаточно. Если ключ каждого узла лежит строго между границами, которые задали предки, то для любого предка все ключи его левого поддерева меньше его ключа: при спуске налево от предка верхняя граница стала равна его ключу и дальше только уменьшалась. Наоборот, если дерево — дерево поиска, все ключи внутри своих границ. Значит, проверка границ равносильна правилу поиска для всех поддеревьев.

Ловушка — проверка «узел больше левого ребёнка и меньше правого». В пятом тесте глубоко в левой половине дерева из слов романа ключ одного узла заменён на ключ чуть больше корневого. С родителем и детьми этот узел в порядке: он правый ребёнок и больше родителя, а правого ребёнка у него нет. Но он лежит в левом поддереве корня и больше корня — поиск этого ключа от корня пойдёт направо и его не найдёт. В девятом тесте так же подменён ключ в дереве адресов сайта, только новый ключ равен корневому.

Порядок проверок задан условием, и он же порядок, в котором имеет смысл чинить: если сломан порядок ключей, о цветах говорить рано. В седьмом тесте один красный узел дерева из землетрясений перекрашен в чёрный — порядок и цвета соседей в порядке, а чёрные высоты разошлись. В восьмом чёрный узел под красным родителем стал красным — это сразу и RED, и BLACK, и выводится первое.

Целое дерево из землетрясений, вставленных по порядку времени, имеет чёрную высоту 13 при высоте 26 — правый край у него чередует чёрные и красные узлы, как рассказано в статье.

4+Решение
5Сложность

O(n) времени и памяти: каждый узел один раз попадает в стек и один раз участвует в подсчёте высот.

6Типичные ошибки
  • Сравнение только с детьми. Пропускает нарушения через несколько этажей — пятый и девятый тесты.
  • Нестрогое сравнение. Равные ключи в дереве поиска — тоже нарушение: поиск найдёт только один из них.
  • Рекурсия. В одиннадцатом тесте дерево — цепочка из 50 000 узлов: рекурсивный обход в Python упрётся в предел глубины.
  • Чёрная высота по одному пути. Пройти по самому левому пути и сравнить с самым правым мало: расхождение может быть в середине дерева. Сравнивать надо у каждого узла его двух детей.

Алгоритмы задачи

DS Структура данных Красно-чёрное дерево Дерево поиска с узлами двух цветов: высота до 2·log₂(n + 1), не больше трёх поворотов на операцию. O(log n) на поиск, вставку и удаление 2 задачи DS Структура данных Двоичное дерево поиска Меньшие налево, большие направо: поиск, порядок и k-й элемент за высоту дерева — от log n до n. O(h): от O(log n) до O(n) 2 задачи
Каталог алгоритмов