Что такое расширяющееся (или косое) дерево

Расширяющееся дерево, также известное как косое дерево (англ. splay tree), — это разновидность самобалансирующегося двоичного дерева поиска, в котором недавно использованные элементы поднимаются ближе к корню. Такая структура помогает ускорить доступ к часто используемым узлам. Косое дерево особенно эффективно в ситуациях, когда определённые элементы запрашиваются чаще других, поскольку каждый доступ перестраивает дерево, чтобы улучшить время доступа к этим элементам в будущем.

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

Простыми словами

Представьте, что у вас есть ящик с папками. Если вы каждый день берёте одну и ту же папку, вы можете начать класть её ближе к верху, чтобы не копаться в глубине каждый раз. Косое дерево делает то же самое — каждый раз, когда вы находите элемент, оно перестраивает себя так, чтобы этот элемент оказался на самом верху.

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

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

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

Пример расширяющегося дерева

Пример простого косого дерева на языке Kotlin начинается с определения узла:

class Node(var key: Int, var left: Node? = null, var right: Node? = null)

Затем можно реализовать основную структуру SplayTree, включающую операцию splay. Ниже приведён упрощённый вариант функции splay, которая подтягивает нужный узел к корню:

fun splay(root: Node?, key: Int): Node? {
    if (root == null || root.key == key) return root

    if (key < root.key) {
        if (root.left == null) return root

        if (key < root.left!!.key) {
            root.left!!.left = splay(root.left!!.left, key)
            return rotateRight(root)
        } else if (key > root.left!!.key) {
            root.left!!.right = splay(root.left!!.right, key)
            if (root.left!!.right != null) {
                root.left = rotateLeft(root.left!!)
            }
        }

        return if (root.left == null) root else rotateRight(root)
    } else {
        if (root.right == null) return root

        if (key > root.right!!.key) {
            root.right!!.right = splay(root.right!!.right, key)
            return rotateLeft(root)
        } else if (key < root.right!!.key) {
            root.right!!.left = splay(root.right!!.left, key)
            if (root.right!!.left != null) {
                root.right = rotateRight(root.right!!)
            }
        }

        return if (root.right == null) root else rotateLeft(root)
    }
}

Функции rotateLeft и rotateRight — это обычные вращения, используемые также в AVL- и красно-чёрных деревьях:

fun rotateRight(x: Node): Node {
    val y = x.left!!
    x.left = y.right
    y.right = x
    return y
}

fun rotateLeft(x: Node): Node {
    val y = x.right!!
    x.right = y.left
    y.left = x
    return y
}

Когда узел подтянут к корню, последующие операции с ним происходят быстрее. Например, если часто запрашивается один и тот же элемент, он будет сохраняться ближе к верху дерева, сокращая путь доступа.

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

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

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

Где используются косое дерево

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

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

2. Таблицы символов и ассоциативные массивы:
В компиляторах или интерпретаторах косые деревья могут использоваться для хранения идентификаторов, переменных или ключей, к которым происходят частые обращения. Подтягивание популярных символов к верху ускоряет доступ.

3. Сжатие данных:
В алгоритмах сжатия, таких как move-to-front encoding, косое дерево используется для представления списка символов. При каждом обращении символ перемещается к началу структуры — что как раз реализуется через операцию splay.

4. Реализация множеств и словарей:
Если требуется структура данных, аналогичная TreeSet или TreeMap, но без необходимости строго логарифмического времени для каждой операции, можно использовать косое дерево. В ситуациях, где одни и те же ключи часто добавляются или ищутся, оно работает эффективно.

5. Эмуляция стека, очереди и деков:
Благодаря своей гибкости косое дерево может использоваться для реализации разных абстракций данных, включая стек или очередь, особенно если важна производительность доступа к последним использованным элементам.

6. Виртуальные машины и интерпретаторы:
В средах исполнения, где постоянно обращаются к одними и тем же переменным или инструкциям, splay-деревья помогают быстро находить нужные блоки кода или значения.

7. Управление интервалами и диапазонами:
В системах, где необходимо поддерживать множество перекрывающихся диапазонов (например, в редакторах текста или при управлении памятью), splay-деревья позволяют быстро находить и обновлять нужные сегменты.

Хотя в реальных проектах splay-деревья используются реже, чем AVL- или красно-чёрные деревья (в силу нестабильной производительности на отдельной операции), они находят своё место в приложениях, где важна адаптация к часто используемым элементам без дополнительной памяти и сложной логики балансировки.