Splay-дерево¶

Splay-дерево — это самобалансирующееся двоичное дерево поиска, в котором операции поиска, вставки и удаления выполняются с амортизированной логарифмической сложностью O(log n). Основная особенность splay-дерева заключается в том, что после каждой операции (включая поиск) дерево перестраивается с помощью специальных поворотов, называемых «сплей» (splay), в результате чего недавно использованный узел перемещается в корень. Это свойство делает splay-деревья особенно эффективными для работы с данными, к которым часто обращаются повторно (локальность обращений).

¶История

Splay-дерево было изобретено и впервые описано в 1985 году американскими учёными Дэниелом Слитором (Daniel Sleator) и Робертом Тарьяном (Robert Tarjan) в статье «Self-Adjusting Binary Search Trees». Работа была опубликована в журнале Journal of the ACM. Идея создания splay-дерева возникла как альтернатива традиционным сбалансированным деревьям (например, красно-чёрным или АВЛ-деревьям), которые требуют хранения дополнительной информации о балансе в каждом узле (например, цвет или высота). Splay-дерево не хранит никакой избыточной информации, что упрощает его реализацию и позволяет экономить память.

¶Принцип работы

Основная операция splay-дерева — это сплей (splay), которая поднимает заданный узел к корню дерева, выполняя последовательность поворотов. Повороты бывают трёх типов: одинарный (zig), двойной (zig-zig) и тройной (zig-zag). Выбор типа поворота зависит от взаимного расположения узла, его родителя и дедушки.

¶Операции

• Поиск (search): выполняется как в обычном двоичном дереве поиска. После нахождения искомого узла (или последнего узла на пути, если элемент не найден) к нему применяется сплей, поднимающий его в корень.
• Вставка (insert): сначала выполняется поиск, который приводит к сплею последнего узла на пути. Затем новый узел вставляется как корень, а дерево разделяется на две части: левое поддерево (узлы меньше нового) и правое поддерево (узлы больше нового).
• Удаление (delete): сначала выполняется сплей удаляемого узла, поднимая его в корень. Затем корень удаляется, и два его поддерева (левое и правое) соединяются: к самому правому узлу левого поддерева применяется сплей, после чего правое поддерево присоединяется как его правая ветвь.

¶Амортизационный анализ

Амортизированная сложность каждой операции в splay-дереве составляет O(log n). Это означает, что хотя отдельная операция может потребовать O(n) времени (например, в случае вырожденного дерева), среднее время по последовательности операций остаётся логарифмическим. Анализ основан на использовании потенциальной функции, которая учитывает логарифм размера поддеревьев. Доказано, что splay-дерево обладает свойством «статической оптимальности»: если к некоторым элементам обращаются чаще, чем к другим, то амортизированное время доступа к ним будет стремиться к оптимальному.

¶Преимущества и недостатки

¶Преимущества

• Простота реализации: не требуется хранить дополнительную информацию о балансе (цвет, высоту), что упрощает код и экономит память.
• Адаптивность к локальности: если к одним и тем же данным обращаются часто, они быстро оказываются в корне, что ускоряет последующие доступы.
• Амортизированная эффективность: гарантирует логарифмическое время в среднем при любой последовательности операций.
• Свойство статической оптимальности: приближается к идеальному дереву для заданного распределения запросов.

¶Недостатки

• Высокая стоимость отдельных операций: в худшем случае (например, при последовательном доступе к элементам в порядке возрастания) дерево может вырождаться в цепочку, и сплей будет требовать O(n) времени.
• Не подходит для реального времени: из-за возможности длительных операций splay-деревья не используются в системах, где критичны гарантии времени выполнения (например, в авионике или медицинских устройствах).
• Сложность параллельной реализации: одновременный доступ нескольких потоков к дереву требует сложной синхронизации из-за частых перестроений.

¶Применение

Splay-деревья находят применение в различных областях компьютерных наук, где важна локальность обращений к данным:

• Кэширование: в системах кэширования (например, кэш страниц в операционных системах) splay-деревья позволяют эффективно хранить и быстро извлекать часто используемые записи.
• Сборка мусора: в некоторых реализациях сборщиков мусора (например, в языке программирования Java) splay-деревья используются для управления памятью.
• Сетевые маршрутизаторы: в алгоритмах маршрутизации, где часто встречаются повторяющиеся запросы к одним и тем же адресам.
• Базы данных: в индексах, поддерживающих частые запросы к ограниченному набору ключей.
• Компиляторы: в некоторых алгоритмах оптимизации кода (например, при выделении регистров).

¶Пример реализации на языке C++

Ниже приведён упрощённый пример реализации splay-дерева на языке C++:

```cpp

¶include <iostream>

struct Node { int key; Node left; Node right; Node(int k) : key(k), left(nullptr), right(nullptr) {} };

class SplayTree { private: Node* root;

Node rightRotate(Node x) { Node* y = x->left; x->left = y->right; y->right = x; return y; }

Node leftRotate(Node x) { Node* y = x->right; x->right = y->left; y->left = x; return y; }

Node splay(Node root, int key) { if (root == nullptr || root->key == key) return root;

if (root->key > key) { if (root->left == nullptr) return root; if (root->left->key > key) { root->left->left = splay(root->left->left, key); root = rightRotate(root); } else if (root->left->key < key) { root->left->right = splay(root->left->right, key); if (root->left->right != nullptr) root->left = leftRotate(root->left); } return (root->left == nullptr) ? root : rightRotate(root); } else { if (root->right == nullptr) return root; if (root->right->key > key) { root->right->left = splay(root->right->left, key); if (root->right->left != nullptr) root->right = rightRotate(root->right); } else if (root->right->key < key) { root->right->right = splay(root->right->right, key); root = leftRotate(root); } return (root->right == nullptr) ? root : leftRotate(root); } }

public: SplayTree() : root(nullptr) {}

void insert(int key) { if (root == nullptr) { root = new Node(key); return; } root = splay(root, key); if (root->key == key) return;

Node* newNode = new Node(key); if (root->key > key) { newNode->right = root; newNode->left = root->left; root->left = nullptr; } else { newNode->left = root; newNode->right = root->right; root->right = nullptr; } root = newNode; }

bool search(int key) { root = splay(root, key); return root != nullptr && root->key == key; }

void remove(int key) { if (root == nullptr) return; root = splay(root, key); if (root->key != key) return;

if (root->left == nullptr) { root = root->right; } else { Node* newRoot = root->left; newRoot = splay(newRoot, key); newRoot->right = root->right; delete root; root = newRoot; } } }; ```

¶Интересные факты

• Splay-дерево является одним из немногих самобалансирующихся деревьев, которое не требует хранения дополнительной информации в узлах (например, цвета или высоты). Это делает его особенно привлекательным для встраиваемых систем с ограниченной памятью.
• Доказано, что splay-дерево является «динамически оптимальным» в определённом классе деревьев — то есть его амортизированная производительность не хуже, чем у любого другого дерева поиска, которое может перестраиваться за счёт поворотов.
• В 1990 году Роберт Тарьян получил премию Тьюринга (совместно с Джоном Хопкрофтом) за фундаментальные достижения в области алгоритмов и структур данных, включая разработку splay-дерева.

¶Источники

• Sleator, D. D., & Tarjan, R. E. (1985). Self-Adjusting Binary Search Trees. Journal of the ACM, 32(3), 652–686.
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. (2013). Алгоритмы: построение и анализ (3-е изд.). Вильямс.
• Okasaki, C. (1998). Purely Functional Data Structures. Cambridge University Press.