Задачи к главе 11

219

индекс key left right

11.4-2 Напишите работающую за линейное время рекурсивную процедуру, которая печатает ключи всех вершин данного двоичного дерева.

11.4-3 Как сделать то же самое (что и в предыдущем упражнении), используя нерекурсивную процедуру? (При устранении рекурсии полезен стек.)

11.4-4 Напишите работающую за линейное время процедуру, печатающую ключи всех вершин дерева, представленного по схеме «левый ребёнок - правый сосед».

11.4-5* Напишите работающую за линейное время нерекурсивную процедуру, печатающую ключи всех вершин двоичного дерева, для которой объём используемой памяти (сверх памяти, в которой хранится дерево) есть 0(1), и во время работы процедуры дерево не меняется (даже временно).

11.4-6* Придумайте способ хранения дерева с произвольным ветвлением, при котором в каждой вершине хранятся всего два (а не три, как в схеме «левый ребенок - правый сосед») указателя плюс одна булева переменная.

Задачи

11-1 Сравнение разных типов списков

Найдите асимптотику времени работы (в худшем случае) для каждой из перечисленных в начале части III (с. 194) операций, применённой к каждому из указанных типов списков.

11-2 Реализация сливаемых куч на базе списков

Структура данных под названием сливаемые кучи (mergeable heaps) хранит набор динамических множеств (куч), и поддерживает следующие операции: Маке-Heap (создание пустой кучи), Insert, Minimum, Extract-Min и, наконец, Union (объединение двух куч в одну; две старые кучи пропадают). Для каждого из перечисленных ниже случаев реализуйте (по возможности эффективно) сливаемые кучи на базе списков. Оцените время работы операций через размеры участвующих множеств.

а.Списки упорядочены.

б.Списки неупорядочены.

е. Списки неупорядочены, объединяемые множества не пересекаются друг с другом.

11-3 Поиск в отсортированном сжатом списке

В упражнении 11.3-4 требовалось хранить списки «компактно»: га-элементный список должен был занимать первые га позиций массива. Предположим ещё, что все ключи различны и что список упорядочен (иными словами, кеу[г] < key[next[i]] при next[i] ф nil). Оказывается, что в этих предположениях следующий вероятностный алгоритм выполняет поиск в списке за время о(га):

Compact-List-Search(L, к)

1г <- head[L]

2га <- length[L]

3while г ф nil and key[i] к

4do j - Random(1, га)

5if key[i] < key[j] and key[j] < к

6then i <- j

7i <- next[i]

8if key[i] = к

9then return i 10 return nil

Без строк 4-6 это был бы обычный алгоритм с последовательным перебором элементов списка. В строках 4-6 мы пытаемся перескочить на случайно выбранную позицию j. Если key[i] < key[j] < k, то при этом мы экономим время, так как не проверяем элементы, лежащие в позициях между г и j. (Благодаря тому, что список занимает непрерывный участок массива, мы можем выбрать в нём случайный элемент.)

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

Как оценить время работы? Представим себе, что на нескольких первых шагах мы выполняем только случайные скачки, а на остальных выполняем линейный поиск. Можно оценить ожидаемое расстояние до искомого элемента после первой фазы - и тем самым длительность второй фазы. Наш алгоритм будет работать не хуже такого усечённого, и остаётся только правильно выбрать длительность первой фазы, чтобы получить оценку получше.

Сделаем это аккуратно. Для каждого t 0 обозначим через Xt случайную величину, равную расстоянию (измеренному вдоль списка) от позиции г до искомого ключа к после t случайных скачков.

б.Покажите, что для каждого t 0 математическое ожидание времени работы алгоритма Compact-List-Search есть 0(t-\-

в. Покажите, что E(Xt) 2~2=i( ~ г/п)*. (Указание: воспользуйтесь формулой (6.28)).

д.Покажите, что E(Xt) n/(t + 1), и объясните «на пальцах», почему это неравенство должно быть верно.

е.Покажите, что математическое ожидание времени работы алгоритма Compact-List-Search есть 0(у/п).

Прекрасные справочники по структурам данных - книги Ахо, Хопкрофта и Ульмана [5] и Кнута [121]. Результаты экспериментов по сравнению эффективности различных операций на структурах данных можно найти в Гоннет [90]

Стеки и очереди использовались в математике и делопроизводстве в докомпьютерную эру. Кнут [121] отмечает, что в 1947 году Тьюринг (A.M.Turing) использовал стеки для связи подпрограмм.

E[Xt\).

Замечания