• Декартово дерево (Treap). [4 гл.13 Задачи 13-4; 20]

Декартово дерево – это бинарное дерево. Каждая вершина x такого дерева имеет два ключа key[x] и priority[x]. По ключу key[x] – это дерево является поисковым (т.е. ключ родителя меньше ключей всех потомков левого сына и больше всех потомков правого), а по ключу priority[x] – это дерево является бинарной пирамидой (т.е. ключ вершины меньше ключей всех её потомков). В таком дереве ключ key задается условиями задачи, а ключ priority – (динамически) формируется генератором случайных чисел.

Помочь разобраться с таким деревом может следующая интерпретация. Предположим, что мы вставляем вершины x₁, x₂, … x_n со связанными с ними ключами. Тогда получающееся в результате декартово дерево представляет собой дерево, которое получилось бы в результате стандартной вставки вершин в стандартное бинарное поисковое дерево по ключам key, но в порядке, определяемом (случайно выбранными) приоритетами, т.е. priority[x_i] < priority [x_j] означает, что вершина x_i была вставлена раньше вершины x_j.

Для этой структуры данных доказано:

• Для каждого заданного множества вершин x₁, x₂, … x_n со связанными с ними ключами и приоритетами (все ключи и приоритеты, будем считать, различны) существует единственное декартово дерево.

• Математическое ожидание высоты такого дерева равно O(log(n)) и, следовательно, время поиска элемента, заданного ключом key, составляет O(log(n)) в среднем.

С таким же временем, O(log(n)) в среднем, реализуемы операции Вставить, Удалить, Найти min и ряд других операций.

В заключение раздела о рандомизированных структурах данных приведем обещание, которое дал Кнут Д.Э. в последнем издании т3. книги «Искусство программирования» [14] - «В следующее издание книги планируется добавить раздел 6.2.5, посвященный рандомизированным структурам данных. В нем будут рассмотрены списки с пропусками, рандомизированные бинарные деревья поиска, а также упомянутые в этом разделе "дучи" (декартовы деревья)».

1 Это плата за возможность поддержки единовременно двух порядков. Платить приходится за все! Весь вопрос – сколько?

226 – число букв в используемом алфавите

3 Задача (и изложение вариантов её решения) заимствована из книги [3 гл.1.]. Даже с учетом высказывания автора «...вероятно, процесс был искусственно упрощен...» этот пример нам представляется уж очень хорошим, особенно и именно в этом месте.

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

4 p-q симметричное: если р связано с q, то q связано с р.

5 p-q транзитивное: если р связано с q, a q связано с r, то р связано с r.

6 Постановка задачи в терминах теории графов. p,q – вершины неориентированного графа, p-q – его ребра. Сведения о ребре p-q надо игнорировать, если в текущем состоянии в графе уже есть путь, соединяющий вершины p и q.

7Можно отметить аналогию с квадратом, у которого, как известно, среди всех прямоугольников - максимальная площадь при минимальном периметре.

8 Двойственность одна из фундаментальных связей между проблемами, которая в математике всегда фиксируется, изучается и используется...

9 Более того, это доказано для (такой же) инверсии функции Аккермана в качестве функции G(.), а функция Аккермана возрастает быстрее любой примитивно-рекурсивной функции.

10 А это напрямую связано с анализом алгоритма решения задачи

11 Такое предположение выглядит очень правдоподобно. Системы линейных уравнений этой задачи описывают реальные системы реальных объектов, причем обычно – это большие системы, созданные человеком. В такой системе скорее всего совсем не всякий объект связан напрямую со всяким, скорее всего система состоит из обозримого количества подсистем с обозримым количеством межкомпонентных связей, и далее то же самое можно сказать о каждой из её подсистем... Т.е. в реальных задачах структура этих систем линейных уравнений не так уж и хаотична...

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

13 Данные типа указатель играют в процедурных языках программирования такую же роль, но это только с определенной точки зрения... Мы же будем придерживаться несколько иной точки зрения – массив (как структура данных) явно существует уже в конструкции ЭВМ (и соответствующей модели вычислителя) в виде адресуемой памяти, а указатели – это индексы этого массива памяти, абстракция адреса этой памяти с предопределенными операциями (в частности, с операцией new – выделить память для хранилища данных).

14 в смысле, множества равны, если у них одинаков состав элементов, независимо от того в каком порядке элементы перечислены.

15 Конечно, можно рассматривать аналогичный АТД, рассматривая «максимальный» взамен «минимального» и соответственно поправив определения нижеследующих операций.

16 Кстати, такое представление не препятствует эффективной реализации операций удаления и добавления (только) ребер.

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

18 Фактически перейти от множества к множеству с ключами элементов – словарю.

19 Можно рассматривать и случай с неуникальными ключами, хотя в этом случае придется аккуратно решать некоторые технические проблемы.

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

21 Естественно, использование поискового дерева для представления множеств предполагает задание какого-нибудь линейного порядка на этих множествах, а использование для словарей – возможность сравнивать значения ключей.

22 Некоторые случаи представляются удивительно странными, с одной стороны, и одновременно удивительно показательными. Например, известно что симлекс метод решения задачи линейного программирования имеет очень плохую оценку по времени в худшем, но статистика испытаний показывает его высокую эффективность по времени. Так называемая быстрая сортировка имеет оценку по времени O(n log(n)) только в среднем, а в худшем – банальную O(n²). Однако статистика испытаний показывает её заметно лучшие характеристики в сравнении с другими методами сортировки. Видимо это объясняется тем, что «плохие» для этих алгоритмов входные данные редко встречаются в практике их использования.

90