12. Декартово дерево
Декартово дерево (англ. treap от англ. tree «дерево» + англ. heap «куча») — структура данных, сочетающая свойства бинарного дерева поиска и двоичной кучи. Хранит пары (x, y), где для ключа x служит бинарным деревом поиска, а для приоритета y — двоичной кучей. Впервые декартово дерево было описано Сесилией Арагон и Раймундом Зиделем в 1989 году. Структура Узлы декартова дерева содержат три основных компонента: значение, приоритет и указатели на дочерние узлы. Узлы могут иметь до двух дочерних узлов — левого и правого. Левый дочерний узел содержит элементы, меньшие по значению, чем родительский узел, а правый — элементы, большие. Приоритет присваивается элементу при его добавлении в дерево, может быть случайным или определяться по какому-либо критерию. Приоритеты не зависят от значений самих элементов, что позволяет эффективно поддерживать баланс дерева. Алгоритм построения Алгоритм построения декартова дерева по множеству пар (x, y): * Упорядочить все пары по ключу x и пронумеровать получившуюся последовательность ключей y: y(1), y(2), y(3), …, y(n). * Найти минимальный ключ y — он будет корнем дерева. * Ключ y(k) делит последовательность ключей y на две: y(1), …, y(k−1), y(k+1), …, y(n). * В каждой из частей найти минимальный y — это будут дети узла y(k) — левый и правый. * С получившимися 4 кусочками (возможно, меньше) поступить аналогичным образом. Свойство однозначности структуры: множество пар (x, y) однозначно определяет структуру декартового дерева. Операции Некоторые операции с декартовым деревом: Вставка узла — новый элемент вставляется как в бинарное дерево поиска, а затем проводится процедура поворота, чтобы восстановить свойства приоритетной очереди. Если новый узел имеет более высокий приоритет, чем родительский узел, производится поворот, и узел становится новым корнем поддерева. Удаление узла — если узел имеет одного или ни одного дочернего узла, его можно просто удалить. Если у узла есть оба дочерних узла, используется метод слияния: сначала выбирается один из дочерних узлов (обычно с меньшим приоритетом), который становится новым корнем поддерева, затем производится слияние оставшегося дочернего узла с новым корнем. Поиск узла — осуществляется аналогично поиску в бинарном дереве поиска: начинается с корня дерева, и в зависимости от значения элемента производится переход либо в левое, либо в правое поддерево. Применение Декартово дерево используется в различных областях информатики, например: задачи, в которых требуется сбалансированное дерево поиска (например, эффективная реализация множеств или словарей); задачи с запросами на диапазонах (RSQ, RMQ и др.), в том числе с обновлениями на отрезках; поиск порядковых статистик (определение k-го по величине элемента).
Декартово дерево (англ. treap от англ. tree «дерево» + англ. heap «куча») — структура данных, сочетающая свойства бинарного дерева поиска и двоичной кучи. Хранит пары (x, y), где для ключа x служит бинарным деревом поиска, а для приоритета y — двоичной кучей. Впервые декартово дерево было описано Сесилией Арагон и Раймундом Зиделем в 1989 году. Структура Узлы декартова дерева содержат три основных компонента: значение, приоритет и указатели на дочерние узлы. Узлы могут иметь до двух дочерних узлов — левого и правого. Левый дочерний узел содержит элементы, меньшие по значению, чем родительский узел, а правый — элементы, большие. Приоритет присваивается элементу при его добавлении в дерево, может быть случайным или определяться по какому-либо критерию. Приоритеты не зависят от значений самих элементов, что позволяет эффективно поддерживать баланс дерева. Алгоритм построения Алгоритм построения декартова дерева по множеству пар (x, y): * Упорядочить все пары по ключу x и пронумеровать получившуюся последовательность ключей y: y(1), y(2), y(3), …, y(n). * Найти минимальный ключ y — он будет корнем дерева. * Ключ y(k) делит последовательность ключей y на две: y(1), …, y(k−1), y(k+1), …, y(n). * В каждой из частей найти минимальный y — это будут дети узла y(k) — левый и правый. * С получившимися 4 кусочками (возможно, меньше) поступить аналогичным образом. Свойство однозначности структуры: множество пар (x, y) однозначно определяет структуру декартового дерева. Операции Некоторые операции с декартовым деревом: Вставка узла — новый элемент вставляется как в бинарное дерево поиска, а затем проводится процедура поворота, чтобы восстановить свойства приоритетной очереди. Если новый узел имеет более высокий приоритет, чем родительский узел, производится поворот, и узел становится новым корнем поддерева. Удаление узла — если узел имеет одного или ни одного дочернего узла, его можно просто удалить. Если у узла есть оба дочерних узла, используется метод слияния: сначала выбирается один из дочерних узлов (обычно с меньшим приоритетом), который становится новым корнем поддерева, затем производится слияние оставшегося дочернего узла с новым корнем. Поиск узла — осуществляется аналогично поиску в бинарном дереве поиска: начинается с корня дерева, и в зависимости от значения элемента производится переход либо в левое, либо в правое поддерево. Применение Декартово дерево используется в различных областях информатики, например: задачи, в которых требуется сбалансированное дерево поиска (например, эффективная реализация множеств или словарей); задачи с запросами на диапазонах (RSQ, RMQ и др.), в том числе с обновлениями на отрезках; поиск порядковых статистик (определение k-го по величине элемента).