Задание № 5052

Студент

Набиева Мадина

Задача

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

Состояние

Завершено

Баллов

7

Назначено

19.03.2023, 23:47

Завершено

19.04.2023, 18:26

Реализовать модуль для работы с красно-черными деревьями.

Интерфейс должен быть идентичен обычному дереву поиска (см. вот эту задачу). Все требования по задачи аналогичны.

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

Дополнительно на каждом шаге тестов необходимо проверять корректность Красно-черного дерева:

  • Корень — чeрный.
  • Оба потомка каждого красного узла — черные.
  • Всякий простой путь от данного узла до любого листового узла, являющегося его потомком, содержит одинаковое число черных узлов.

Для этого нужно добавить в модуль соответствующую функцию check(tree).

Действия