Splay Tree

• Структура данных - Splay Tree.
• Splay Tree — это самобалансирующееся бинарное дерево поиска. Дереву не нужно хранить никакой дополнительной информации, что делает его эффективным по памяти. После каждого обращения, даже поиска, splay tree меняет свою структуру и, за счет этого, оно позволяет находить быстрее те данные, которые использовались недавно. Splay tree не подходит для данных, которые редко или никогда не меняются, особенно в многопоточной среде. Они наиболее полезны для часто изменяемых структур данных.
• Пример использования - сетевой маршрутизатор. Сетевой маршрутизатор получает сетевые пакеты с высокой скоростью от входящих подключений и должен быстро решить, по какому исходящему проводу отправлять каждый пакет, на основе IP-адреса в пакете. Маршрутизатору нужна большая таблица (карта), которую можно использовать для поиска IP-адреса и определения того, какое исходящее соединение использовать. Если IP-адрес использовался один раз, он, вероятно, будет использоваться снова, возможно, много раз. В этой ситуации Splay-деревья могут обеспечить хорошую производительность.
• Операции:

1. Splay (расширение) Основная операция дерева. Заключается в перемещении вершины в корень при помощи последовательного выполнения трёх операций: Zig, Zig-Zig и Zig-Zag.

• a)zig Если p — корень дерева с сыном x, то совершаем один поворот вокруг ребра (x,p), делая x корнем дерева. Данный случай является крайним и выполняется только один раз в конце, если изначальная глубина x была нечетной.
• б)zig-zig Если p — не корень дерева, а x и p — оба левые или оба правые дети, то делаем поворот ребра (p,g), где g отец p, а затем поворот ребра (x,p).
• в)zig-zag Если p — не корень дерева и x — левый ребенок, а p — правый, или наоборот, то делаем поворот вокруг ребра (x,p), а затем поворот нового ребра (x,g), где g — бывший родитель p.

2. Search (поиск элемента) Поиск выполняется как в обычном двоичном дереве поиска. При нахождении элемента запускаем Splay для него.
3. Split (разделение дерева на две части) Для разделения дерева найдем наименьший элемент, больший или равный x, и сделаем для него Splay. После этого отрезаем у корня левого ребёнка и возвращаем 2 получившихся дерева.
4. Merge (объединение двух деревьев) Для слияния деревьев T1 и T2, в которых все ключи T1 меньше ключей в T2, делаем Splay для максимального элемента T1, тогда у корня T1 не будет правого ребенка. После этого делаем T2 правым ребенком T1.
5. Insert (добавление элемента) Вставка происходит как в обычном бинарном дереве поиска, после, запускаем Split() от добавляемого элемента и подвешиваем получившиеся деревья за него.
6. Remove (удаление элемента) Находим элемент в дереве, делаем Splay для него, делаем текущим деревом Merge его детей.

• Сложность операций и требование по памяти:
• Затраты по памяти - O(n)
• Splay - O(log(n))
• Search - O(log(n))
• Split - O(log(n))
• Merge - O(log(n))
• Insert - O(log(n))
• Delete - O(log(n))
• Splay tree предоставляет самоизменяющуюся структуру — структуру, характеризующуюся тенденцией хранить узлы, к которым часто происходит обращение, вблизи верхушки дерева, в то время как узлы, к которым обращение происходит редко, перемещаются ближе к листьям. Таким образом время обращения к часто посещаемым узлам будет меньше, а время обращения к редко посещаемым узлам — больше среднего. Splay Tree не обладает никакими явными функциями балансировки, но процесс скоса узлов к корню способствует поддержанию дерева в сбалансированном виде.

Команда "Stack Overflow"

Фамилия Имя	Вклад (%)	Прозвище
Кобылин Константин	√1108,89	Костя
Губайдуллин Ильшат	√1108,89	Ильшат
Иванов Тимур	√1108,89	Тимур

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

Все победы начинаются с победы над самим собой

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

Проект состоит из следующих частей:

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

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

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

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

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

Windows

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

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

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

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

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

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

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

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

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

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

# запуск Python-скрипта
python generator.py

Все папки и файлы автоматически сгенерируются

Тестовые данные представлены в CSV формате. Пример:

1. 1
2. 10
3. 3
...

Директория с наборами данных выглядит примерно так:

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

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

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

Для запуска контрольных тестов необходимо предварительно сгенерировать или скачать готовый набор тестовых данных.

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

Название	Описание	Метрики
benchmark	содержит в себе бенчмарки на все операции	время

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

Для начала нужно изменить код в файле. Для этого открываем код в редакторе, например, clion.

После открытия ищем данный фрагмент кода:

Здесь мы меняем переменные operation, trials, count_of_elements и dataset на нужные.

В верхнем примере кода у нас бенчмарки на операцию remove с 10-ью прогонами на 1-ом наборе данных с количеством элементов 5000000.

Также можно поменять время, которое будет выводится в консоль:

Так можно nanoseconds заменить на milliseconds, чтобы время выводилось в миллисекундах.

Остается построить и запустить код. Это можно сдедать напрямую в clion, либо built код в clion, а затем запустить с помощью консоли:

./benchmark.exe

В консоле будет выводится время в наносекундах.

Источники

habr
wikipedia
Гугл диск