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

375

18.4-4 Рассмотрим такую реализацию операции Table-Delete: если в результате удаления элемента коэффициент заполнения падает ниже 1/3, то мы сокращаем таблицу на треть её размера. Пользуясь потенциалом

Ф(Г) = 2 • пит[Т] - size[T]\,

покажите, что при этом учётная стоимость операции Table-Delete ограничена.

Задачи

18-1 Двоичный счетчик с обратным порядком битов

В главе 32 мы расскажем о важном алгоритме, называемом быстрым преобразованием Фурье. Этот алгоритм начинается с обращения битов индекса (bit-reversal permutation) у массива А[0 . .п - 1], где п = 2к (к - натуральное число). Именно, каждое А[а] заменяется на A[revfc(a)], где rev(a) получается, если представить число а в виде последовательности к битов, а затем написать эти биты в обратном порядке. Иными словами, если а = 2 i=o a«2J, то

k-i

revfc(a) = yafc 8 i28.

8 = 0

Пример: rev4(3) = 12, поскольку 3 в двоичной записи есть ООН, а 1100 - двоичная запись числа 12.

а.Легко вычислить rev(a) за время Q(k). Как произвести операцию обращения битов индекса в массиве длиной п = 2к за время О(пк)?

Чтобы выполнять обращение битов индекса быстрее, можно применить амортизационный анализ к процедуре прибавления единицы наоборот, которая даёт revfc(a+l) по данному rev(a). Выделим массив битов длиной к для хранения счетчика с обращенным порядком битов. Нам нужно разработать процедуру Bit-Reversed-Increment, переводящую rev(a) в rev(a) + 1. Если, например, к = 4 и первоначально в счетчике с обращенным порядком битов было записано 0000, то в результате последовательных вызовов процедуры Bit-Reversed-Increment значения счётчика будут равны

0000,1000, 0100,1100, 0010,1010, ... = 0,8,4,12, 2,10,... .

б.Пусть компьютер умеет за единичное время проводить с к-битными словами такие операции, как сдвиг на произвольное

количество битов, логические И и ИЛИ и т. д. Как нужно реализовать процедуру Bit-Reversed-Increment, чтобы обращение битов индекса у массива длиной п = 2к занимало О (га) времени?

в. Пусть за единичное время /г-битное слово можно сдвинуть лишь на один бит. Можно ли в этом случае провести обращение битов индекса за время О (га)?

18-2 Динамический двоичный поиск

Чтобы сократить время на добавление элемента к отсортированному массиву, можно поступить так. Распределим элементы отсортированного массива длины га по к = [log2 га] массивам Ао, А\,..., Ak следующим образом: если (n-i, га 2,..., щ) - дво-

последнем случае массив Аг- отсортирован. На распределение га элементов по массивам Ао,..., Ап никаких условий не накладывается.

а.Реализуйте для этой структуры данных операцию Search (искать). Каково ее время работы в худшем случае?

б.Реализуйте операцию Insert (добавить элемент). Оцените ее стоимость в худшем случае и учётную стоимость (если возможны только добавления, но не удаления).

в.Как реализовать операцию Delete (удалить)?

18-3 Сбалансированные по весу деревья

Пусть х - узел двоичного дерева; через size[x] обозначим число листьев в поддереве с вершиной в х. Пусть число а удовлетворяет неравенству 1/2 а < 1. Будем говорить, что узел х «-сбалансирован (a-balanced), если

Двоичное дерево называется «-сбалансированным, если все его узлы, кроме листьев, «-сбалансированы. Подход к сбалансированным деревьям, о котором идет речь ниже, был предложен Г.Варгезе (С. Varghese).

а.Пусть х - узел двоичного дерева поиска. Объясните, как перестроить поддерево с корнем в х, чтобы оно стало 1/2-сбалансированным (самое сильное требование сбалансированности) Ваш алгоритм должен работать за время @(size[x]) и пользоваться дополнительной памятью объема 0(size[x]).

б.Покажите, что поиск в «-сбалансированном двоичном дереве с п узлами требует в худшем случае времени О (log га).

size[left[x]] а size[x]

и

size[right[x]] а size[x].

Далее будем считать, что а > 1/2. Будем считать, что после выполнения операций Insert и Delete (реализованных стандартным образом), производится балансировка: если какой-то узел дерева перестал быть «-сбалансированным, выбирается ближайший к корню из таких узлов и соответствующее поддерево перестраивается в 1/2-сбалансированное (см. пункт а).

Проанализируем эту схему балансировки с помощью метода потенциалов. Как обычно, потенциал будет тем больше, чем дальше дерево от сбалансированного. Пусть х - узел в двоичном дереве Г; положим

Д(ж) = вг,ге[/еД[ж]] - size[right[x]\ и определим потенциал Ф(Г) по формуле

Ф(Г) = с £ А(х),

хеТ:А(х)2

где с - достаточно большая положительная константа, зависящая от а.

в.Покажите, что потенциал двоичного дерева всегда неотрицателен и что потенциал 1/2-сбалансированного дерева равен нулю.

г.Будем считать, что стоимость перестройки дерева с то вершинами в 1/2-сбалансированное равна тп (напомним, что число операций есть О (то)). Какова должна быть величина с для данного а, чтобы учётная стоимость перестройки поддерева, не являющегося «-сбалансированным, была 0(1)?

д.Покажите, что учётная стоимость удаления или вставки элемента в «-сбалансированное дерево с п вершинами есть О (log га).

Замечания

Метод группировки в амортизационном анализе описан у Ахо, Хопкрофта и Ульмана [4]. Тарьян [189] рассматривает методы предоплаты и потенциалов и приводит некоторые приложения. Согласно Тарьяну, метод предоплаты восходит к работам многих авторов, в том числе Брауна (M.R.Brown), Тарьяна (R. Е. Tarjan), Хадлстона (S. Huddleston) и Мельхорна (К. Mehlhorn), в то время как метод потенциалов изобретен Слеатором (D. D. Sleator). Термин «амортизационный анализ» введён Слеатором и Тарьяном.