Декартово дерево (treap): дерево поиска и куча в одном

Коротко

Treap (от tree + heap) — дерево, которое одновременно является деревом поиска по ключу и кучей по приоритету.

Идея

Каждый узел хранит два значения:

• ключ — по нему поддерживается свойство дерева поиска: левое поддерево меньше, правое больше;
• приоритет — по нему поддерживается свойство кучи: приоритет родителя больше приоритетов детей.

            (ключ 5, приоритет 90)
             /                  \
    (3, 70)                      (8, 60)
     /                            /
 (1, 40)                     (7, 30)

Ключевой факт: при фиксированных ключах и приоритетах структура дерева определена однозначно. А если приоритеты назначить случайно, дерево получится сбалансированным с высокой вероятностью — той же самой, что у случайного дерева поиска, то есть высотой O(log n).

Это тот же приём, что в skip list: случайность вместо явной балансировки.

Split и merge — основа всего

В отличие от АВЛ и красно-чёрных деревьев, treap строится не на поворотах, а на двух операциях.

split(tree, key) разрезает дерево на два: в первом все ключи меньше key, во втором — не меньше.

merge(left, right) склеивает два дерева, но только если все ключи левого меньше всех ключей правого.

Через них выражается всё остальное. Вставка: разрезали в нужной точке, склеили с новым узлом. Удаление: разрезали дважды, выбросили середину, склеили края.

import random


class Node:
    __slots__ = ('key', 'priority', 'left', 'right')

    def __init__(self, key):
        self.key = key
        self.priority = random.random()
        self.left = None
        self.right = None


def split(node, key):
    """Возвращает (дерево с ключами < key, дерево с ключами >= key)."""
    if node is None:
        return None, None

    if node.key < key:
        left, right = split(node.right, key)
        node.right = left
        return node, right
    else:
        left, right = split(node.left, key)
        node.left = right
        return left, node


def merge(left, right):
    """Все ключи left должны быть меньше всех ключей right."""
    if left is None:
        return right
    if right is None:
        return left

    # наверх идёт узел с большим приоритетом — свойство кучи
    if left.priority > right.priority:
        left.right = merge(left.right, right)
        return left
    else:
        right.left = merge(left, right.left)
        return right


def insert(root, key):
    node = Node(key)
    left, right = split(root, key)
    return merge(merge(left, node), right)


def erase(root, key):
    left, rest = split(root, key)
    _, right = split(rest, key + 1)     # выбрасываем середину
    return merge(left, right)


def contains(root, key) -> bool:
    while root:
        if root.key == key:
            return True
        root = root.left if key < root.key else root.right
    return False


def inorder(node, out=None):
    if out is None:
        out = []
    if node:
        inorder(node.left, out)
        out.append(node.key)
        inorder(node.right, out)
    return out


root = None
for x in [5, 3, 8, 1, 7, 9]:
    root = insert(root, x)

print(inorder(root))     # [1, 3, 5, 7, 8, 9]
print(contains(root, 7)) # True

root = erase(root, 5)
print(inorder(root))     # [1, 3, 7, 8, 9]

Обратите внимание, насколько короткая вставка: три строки против десятков в АВЛ-дереве с четырьмя видами поворотов.

Неявный ключ: массив с операциями за O(log n)

Самое мощное применение treap. Вместо ключа-значения используем позицию элемента в последовательности, которая нигде не хранится, а вычисляется из размеров поддеревьев.

Это даёт структуру, которая умеет то, чего не умеет обычный массив:

• вставить элемент в середину за O(log n);
• удалить из середины за O(log n);
• перевернуть подотрезок за O(log n);
• переместить кусок массива в другое место;
• считать сумму или минимум на отрезке.

class ImplicitNode:
    __slots__ = ('value', 'priority', 'size', 'left', 'right', 'reversed')

    def __init__(self, value):
        self.value = value
        self.priority = random.random()
        self.size = 1
        self.left = None
        self.right = None
        self.reversed = False


def size(node) -> int:
    return node.size if node else 0


def update(node):
    if node:
        node.size = 1 + size(node.left) + size(node.right)


def push(node):
    """Проталкиваем отложенный переворот вниз."""
    if node and node.reversed:
        node.left, node.right = node.right, node.left
        for child in (node.left, node.right):
            if child:
                child.reversed = not child.reversed
        node.reversed = False


def split_implicit(node, k):
    """Первые k элементов и остальные."""
    if node is None:
        return None, None
    push(node)

    if size(node.left) < k:
        left, right = split_implicit(node.right, k - size(node.left) - 1)
        node.right = left
        update(node)
        return node, right
    else:
        left, right = split_implicit(node.left, k)
        node.left = right
        update(node)
        return left, node


def merge_implicit(a, b):
    if a is None:
        return b
    if b is None:
        return a
    push(a)
    push(b)

    if a.priority > b.priority:
        a.right = merge_implicit(a.right, b)
        update(a)
        return a
    else:
        b.left = merge_implicit(a, b.left)
        update(b)
        return b


def reverse_range(root, l, r):
    """Перевернуть элементы с l по r включительно."""
    left, rest = split_implicit(root, l)
    middle, right = split_implicit(rest, r - l + 1)
    if middle:
        middle.reversed = not middle.reversed
    return merge_implicit(merge_implicit(left, middle), right)


def to_list(node, out=None):
    if out is None:
        out = []
    if node:
        push(node)
        to_list(node.left, out)
        out.append(node.value)
        to_list(node.right, out)
    return out


root = None
for x in [1, 2, 3, 4, 5]:
    root = merge_implicit(root, ImplicitNode(x))

print(to_list(root))                    # [1, 2, 3, 4, 5]
root = reverse_range(root, 1, 3)
print(to_list(root))                    # [1, 4, 3, 2, 5]

Приём с отложенным переворотом (флаг reversed и функция push) — это техника «ленивого проталкивания», знакомая по деревьям отрезков. Мы не переворачиваем поддерево сразу, а помечаем его и разворачиваем только при спуске.

Сравнение с другими деревьями

Главное преимущество treap — операции split и merge, которых нет у классических сбалансированных деревьев. Именно они открывают работу с последовательностями.

Где применяется

Олимпиадное программирование — основное применение. Задачи на отрезки с перестановками, вставками и переворотами решаются только этой структурой (или похожими splay-деревьями).

Персистентные структуры. Treap легко сделать неизменяемым: split и merge создают новые узлы вместо изменения старых, и старые версии остаются доступны.

Реализация сортированных коллекций там, где нужны диапазонные операции.

Частые ошибки

Забытый update после изменения структуры. Размеры поддеревьев разъедутся, и неявные ключи начнут указывать не туда.

Забытый push перед спуском. Отложенные операции не применятся, и результат будет неверным. Правило: push в самом начале любой функции, которая заходит в узел.

Нарушение предусловия merge. Функция не сортирует — она требует, чтобы все ключи левого дерева были меньше правого. Нарушение молча ломает дерево поиска.

Одинаковые приоритеты. При random.randint на маленьком диапазоне возможны совпадения, что ухудшает баланс. Используйте широкий диапазон или random.random().

Глубокая рекурсия. На больших деревьях split и merge могут упереться в лимит стека Python.

Что запомнить

• Treap — дерево поиска по ключу и куча по случайному приоритету одновременно.
• Случайные приоритеты дают сбалансированность без явной балансировки.
• Вся работа строится на двух операциях: split и merge.
• Неявный ключ превращает treap в массив со вставкой, удалением и переворотом отрезка за O(log n).
• Не забывайте update размеров и push отложенных операций.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→