2-3 Tree

Краткое описание семестрового проекта:

• Структура данных: 2-3 Tree.
• Основная информация: Это структура данных является В-деревом, каждый узел которого имеет либо два потомка и одно поле, либо три потомка и два поля. 2-3 деревья сбалансированы(все листовые вершины находятся на одной высоте от корня дерева).
• Используется: Ядро Linux, Completely Fair Scheduler, для отслеживания сегментов виртуальной памяти Процесса
• Операции: поиск ключа, добавление ключа, удаление ключа, слияние и разбиение ключа, очистка.
• Теоретическая сложность операций: поиск за O(log(n)), вставка за O(log(n)) удаление за O(log(n)).
• Свойства:

1. Листовые вершины находятся на одном уровне и содержат 1 или 2 поля.
2. Нелистовые вершины содержат одно поле и 2 поддерева или 2 поля и 3 поддереваю
3. Данные отсортированы (по принципу двоичного дерева поиска). Значение первого поля строго больше наибольшего значения в левом поддереве и меньше или равно наименьшему значению в правом поддереве(или в центральном поддереве). Значение второго поля(если оно есть) строго больше наибольшего значения в центральном поддереве и меньше или равно, чем наименьшее значение в правом поддереве.

Команда "Bubble Quasar"

Фамилия Имя	Вклад (%)	Прозвище
Бровин Роман	57	lv.57 Boss
Суреева Анна	43	lv.43 Hitman

Девиз команды

Мы, конечно, не Гринпис, но деревья обожаем.

Структура проекта

Здесь представлено описание основных частей семестрового проекта.

• src/include - реализация структуры данных (исходный код и заголовочные файлы);
• benchmark - контрольные тесты производительности структуры данных (операции добавления, удаления, поиска и пр.);
• examples - примеры работы со структурой данных;
• dataset - наборы данных для запуска контрольных тестов и их генерация;

Требования (Prerequisites)

Рекомендуемые требования:

1. С++ компилятор c поддержкой стандарта C++17 (GNU GCC 8.1.x и выше).
2. Система автоматизации сборки CMake (версия 3.12.x и выше).
3. Интерпретатор Python (версия 3.8.x и выше).
4. Рекомендуемый объем оперативной памяти - не менее 8 ГБ.
5. Свободное дисковое пространство объемом ~ 2 ГБ (набор данных для контрольных тестов).

Сборка и запуск

Инструкция по сборке проекта, генерации тестовых данных, запуска контрольных тестов и примеров работы.

Сборка проекта (Windows)

Склонируйте проект к себе на устройство через Git for Windows (либо используйте возможности IDE):

git clone https://github.com/Algorithms-and-Data-Structures-2021/semester-work-2-3-tree

Для ручной сборки проекта в терминале введите:

# переход в папку с проектом
cd C:\Users\username\asd-projects\semester-work-2-3-tree

# создание папки для файлов сборки (чтобы не засорять папку с проектом) 
mkdir -p build && cd build 

# сборка проекта
cmake .. -DCMAKE_BUILD_TYPE=RelWithDebInfo && cmake --config RelWithDebInfo --build . 

Генерация тестовых данных

Формат хранения данных, выбранный для этого проекта, - .csv

Генерация тестового набора данных в формате comma-seperated values (CSV):

# переход в папку генерации набора данных
cd dataset

# generate_csv_dataset.py Отвечает за генерацию данных, запустив эту программу вы сгенерируете 10 наборов данных,
# в каждом из которых будет 10 .csv файлов с различным количеством элементов

# Чтобы запустить генерацию данных, нужно написать в терминале приведенную нижу команду(требуется питон интерпретатор)
python generate_csv_dataset.py

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

# Папка data организавана следующим образом:

dataset/data/
  insert/
    01/
      100.csv
      ...
      5000000.csv
    02/ ...
    03/ ...
    ...
    10/ ...
  search/
    01/
      100.csv
      ...
      5000000.csv
    ...
    10/ ...
  ...

По названию директории /dataset/data/insert можно понять, что здесь хранятся наборы данных для контрольных тестов по добавлению элементов в структуру данных. Названия файлов 100.csv. 5000000.csv и т.д. хранят информацию о размере набора данных (т.е. количество элементов).

Контрольные тесты (benchmarks)

Для запуска контрольных тестов необходимо предварительно сгенерировать или скачать готовый набор тестовых данных. Учтите, что данные, которые вы получили в предыдущих тестах, будут стёрты. Результаты тестов будут находиться по пути semester-work-2-3-tree/benchmark/result/.

Примечание. Ссылка на архив с набором данных, который при необходимости можно скачать.(https://drive.google.com/drive/folders/15mQac1_GYA5MiZmsx76E67E3ZXS56c0G?usp=sharing)

Список контрольных тестов

Название	Описание	Метрики
benchmark_insert.cpp	добавление элементов в структуру данных	время
benchmark_remove.cpp	удаление элемента из структуры данных	время
benchmark_search.cpp	поиск элементов по случайному индексу	время

Примеры запуска

Для запуска просто нажмите run benchmark_insert.cpp or benchmark_remove.cpp or benchmark_search.cpp

Источники

1. Habr about 2-3 tree
2. Wiki about 2-3 tree
3. Youtube: the best 2-3 tree
4. About tree data structures