Структура данных Treap (дерево + куча) — учебное пособие со статистическим анализом

Структура данных в информатике, называемая «Treap», представляет собой комбинацию бинарного дерева поиска и кучи. В этом вводном руководстве объясняется, как структура данных Treap использует случайно сгенерированные числа, называемые «приоритетом», для построения и поддержания достаточно сбалансированного дерева. Дерево строится так же, как и куча, с максимальным значением приоритета в корне дерева. Обратите внимание, что при построении дерева необходимо одновременно удовлетворять двум условиям: 1) значение каждого левого дочернего узла меньше значения его родителя, а значение каждого правого дочернего узла больше значения его родителя (это старое правило бинарного дерева поиска). 2) приоритет каждого дочернего узла меньше приоритета его родителя (это правило максимальной кучи). Чтобы гарантировать выполнение обоих этих условий, при вставке узла мы по-прежнему спускаемся от корня, следуя правилам стандартного бинарного дерева поиска (BST), сравнивая значения друг с другом — мы движемся влево, если значение меньше родителя, вправо, если значение больше родителя, и в конечном итоге создаем новый листовой узел. Затем, если мы обнаружим, что приоритет узла выше приоритета родительского узла, мы выполняем вращение дерева, чтобы это исправить. Сесилия Р. Арагон и Раймунд Зайдель в своей статье 1989 года под названием «Рандомизированные деревья поиска» показывают, что, хотя нет жесткой гарантии, что результирующее дерево будет сбалансированным, вероятность того, что высота дерева с n узлами будет больше натурального логарифма n на величину некоторой константы c, ограничена формулой. http://faculty.washington.edu/aragon/... В информатике «Treap» и рандомизированное бинарное дерево поиска — это две тесно связанные формы структур данных бинарного дерева поиска, которые поддерживают динамический набор упорядоченных ключей и позволяют осуществлять бинарный поиск среди ключей: https://en.wikipedia.org/wiki/Treap Лекция Аврима Блюма в CMU, в которой используется «неравенство Хоффдинга» для анализа глубины «Treap»: https://www.cs.cmu.edu/~avrim/451f11/... Автор текста и озвучка: Андрей Виолентьев