Сплей-дерево¶

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

¶История

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

¶Основные принципы работы

¶Структура

Сплей-дерево является двоичным деревом поиска: для каждого узла все ключи в левом поддереве меньше ключа узла, а все ключи в правом поддереве — больше. Дерево не имеет жёстких ограничений на высоту, но его структура динамически подстраивается под последовательность запросов.

¶Операция «сплей»

Операция «сплей» (splay) — это последовательность вращений, которая перемещает заданный узел в корень дерева. Вращения выполняются в зависимости от взаимного расположения узла, его родителя и дедушки. Существует три основных случая:

• Zig (одиночный поворот): выполняется, когда узел является дочерним элементом корня. В этом случае производится один поворот вокруг родителя, и узел становится корнем.
• Zig-zig (двойной поворот): выполняется, когда узел и его родитель являются левыми (или правыми) потомками своих родителей. В этом случае сначала вращается родитель вокруг дедушки, затем узел вокруг родителя. Это позволяет поднимать узел на два уровня вверх.
• Zig-zag (двойной поворот): выполняется, когда узел является левым потомком правого родителя (или правым потомком левого родителя). В этом случае сначала вращается узел вокруг родителя, затем узел вокруг дедушки.

Операция «сплей» применяется после каждой операции поиска, вставки или удаления, что гарантирует, что часто используемые элементы оказываются близко к корню.

¶Амортизированная сложность

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

¶Операции

¶Поиск

Поиск элемента в сплей-дереве выполняется как в обычном двоичном дереве поиска: начиная с корня, алгоритм сравнивает искомый ключ с ключом текущего узла и переходит в левое или правое поддерево. После нахождения узла (или после того, как будет достигнут конец дерева, если элемент отсутствует) выполняется операция «сплей» для последнего посещённого узла. Если элемент найден, он перемещается в корень. Если элемент не найден, в корень перемещается узел, с которым было произведено последнее сравнение.

¶Вставка

Вставка нового элемента в сплей-дерево происходит в два этапа. Сначала выполняется операция «сплей» для узла, который должен стать родителем нового элемента (или для корня, если дерево пусто). Затем новый узел вставляется в корень, а левое и правое поддеревья перераспределяются: если ключ нового узла меньше ключа старого корня, то старый корень становится правым потомком нового, а левое поддерево старого корня — левым потомком нового. В противном случае старый корень становится левым потомком нового, а правое поддерево — правым.

¶Удаление

Удаление элемента из сплей-дерева также использует операцию «сплей». Сначала выполняется поиск удаляемого узла с последующим «сплеем», который перемещает его в корень. Затем дерево разделяется на два поддерева: левое (с ключами меньше удаляемого) и правое (с ключами больше). Далее в левом поддереве выполняется операция «сплей» для максимального элемента, который становится его корнем. После этого правое поддерево присоединяется к левому как правое поддерево нового корня. Если левое поддерево пусто, корнем становится правое.

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

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

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

¶Недостатки

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

¶Применение

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

• Кэширование: в алгоритмах кэширования, где часто используемые данные должны быть доступны максимально быстро.
• Компиляторы: в некоторых реализациях компиляторов для хранения таблиц символов.
• Сетевые маршрутизаторы: для хранения таблиц маршрутизации, где часто повторяются запросы к определённым адресам.
• Базы данных: в некоторых системах управления базами данных для индексации данных с неравномерным распределением запросов.
• Алгоритмы сжатия данных: в алгоритмах, таких как LZW, где требуется быстрый поиск по словарю.

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

• Сплей-дерево является примером «саморегулирующейся» структуры данных, которая не требует явного хранения информации о балансе.
• Роберт Тарьян, один из создателей сплей-дерева, является лауреатом премии Тьюринга (1986) за вклад в теорию алгоритмов и структур данных.
• Сплей-деревья часто используются в учебных курсах по алгоритмам и структурам данных для демонстрации концепции амортизированного анализа.

¶Источники

• Sleator, D. D., & Tarjan, R. E. (1985). Self-Adjusting Binary Search Trees. Journal of the ACM, 32(3), 652–686.
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. (2013). Алгоритмы: построение и анализ. 3-е издание. Вильямс.
• Седжвик, Р. (2014). Алгоритмы на Java. 4-е издание. Вильямс.