Cartesian tree container

Тестовое задание для компании Syntacore

Класс, представляющий из себя расширенное сбалансированное дерево, хранящее ключи и предоставляющее интерфейс для выполнения двух следующих запросов:

• Запрос (m i) на поиск i-го наименьшего элемента (k-ая наименьшая статистика)
• Запрос (n j) на поиск количества элементов, меньших, чем заданный j

Установка и запуск

1. Склонировать этот репозиторий
2. Запустить скрипт сборки с помощью запуска bash build.sh
3. Запустить исполняемый файл ./build/syntacore-tools-intership-task

Программа принимает четыре команды:

• Запрос (m i) на поиск i-го наименьшего элемента (k-ая наименьшая статистика)
• Запрос (n j) на поиск количества элементов, меньших, чем заданный j
• Запрос (k j) на добавление ключа j в дерево
• Запрос (q) на завершение работы

Алгоритм работы

Дерево балансируется с помощью дополнительного поля(prior_) в каждой вершине. Оно инициализируется случайным значением. Доказательство глубины в логарифм.

Логарифмическая сложность операций нахождения k-ой статистики и кол-ва числе меньше достигается из-за добавления в вершину поля size, обозначающую размер поддерева и её обновление с помощью скрытой функции recalc(), вызов которой происходит при каждом изменении правого или левого ребёнка ноды.

Реализация алгоритма поиска k-ой статистики

1. Находим размер левого поддерева корня
2. Если размер поддерева равен номеру статистики, то это корень
3. Если размер поддерева больше номера статистики, то спускаемся в левое поддерево и повторяем процесс
4. Если размер поддерева меньше номера статистики, то уменьшаем k на (размер левого поддерева + 1), спускаемся в правое поддерево и повторяем процесс

Можно увидеть, что кол-во вершин которые обошли будет равняться высоте дерева => logN

Реализация алгоритма поиска кол-ва чисел меньших чем k

1. Пока ключ текущей вершины меньше k спускаемся в правое поддерево
2. Как только встретили ключ >= k или обошли все вершины возвращаем величину равную (размер всего дерева - размер первого неподходящего поддерева)

Можно увидеть, что кол-во вершин которые обошли будет равняться высоте дерева => logN

Тестирование

Тестирование проведено с помощью библиотеки GoogleTest

• Отдельно было проведено юнит-тестирование ноды дерева
• Было проведено интеграционное тестирование всего модуля cartesian-tree-container
• Запустить тесты можно запустив из каталога build команду ctest

При запуске скрипта для сборки сразу запускаются написанные тесты

Визуализация времени выполнения операций

Также представлен бенчмарк для визуализации времени выполнения операций, запустить сбор данных можно с помощью выполнения команды bash bench.sh