Алгоритмы - построение и анализ (1021735), страница 109
Текст из файла (страница 109)
Поддерживаемые стеком операции Ризи и Ров должны работать со значениями, представляющими отдельные машинные слова. Стек должен иметь возможность роста до размеров, существенно превышающих размер оперативной памяти, так что его большая часть должна храниться на диске. Простая, но неэффективная реализация стека хранит его весь на диске. В памяти поддерживается только указатель стека, который представляет собой дисковый адрес элемента на вершине стека. Если указатель имеет значение р, элемент на вершине стека является (р пюс1 т)-м словом на странице 1р/ууз), где т — количество слов в одной странице. 534 Часть Ч.
Сложные структуры данных Для реализации операции Рази мы увеличиваем указатель стека, счятываем в оперативную память с диска соответствующую страницу, хо. пируем вносимый в стек элемент в соответствующее место на странице и записываем страницу обратно на диск. Реализация операции Рор аналогична реализации операции Рьян. Мы уменьшаем указатель стещ считываем в оперативную память с диска соответствующую страницу и возвращаем элемент на вершине стека. Нет необходимости записывать страницу назад на диск, поскольку она не была модифицирована. Поскольку дисковые операции достаточно дорогие в смысле времени их выполнения, мы учитываем при любой реализации стека две стоимости: общее количество обращений к диску и необходимое процессорное время.
Будем считать, что дисковые операции со страницей размером т слов требуют одного обращения к диску и процессорное время О (пь). а) Чему в наихудшем случае равно асимптотическое количество обращений к диску при такой простейшей реализации стека? Чему равно требуемое процессорное время для п стековых операций? (Ваш ответ на этот и последующие вопросы данной задачи должен выражаться через пь и и.) Теперь рассмотрим реализацию стека, при которой одна страница стека находится в оперативной памяти (кроме того, небольшое количеспю оперативной памяти используется для отслеживания того, какая имен. но страница находится в оперативной памяти в настоящее время).
Само собой разумеется, что мы можем выполнять стековые операции толью в том случае, если соответствующая дисковая страница находится в опе. ративной памяти. При необходимости страница, находящаяся в данный момент в оперативной памяти, может быть записана на диск, а в память считана новая дисковая страница. Если нужная нам страница уже находится в оперативной памяти, то выполнение дисковых операций ле требуется.
б) Чему в наихудшем случае равно количество необходимых обращений к диску для и операций Ризи? Чему равно соответствующее процессорное время? в) Чему в наихудшем случае равно количество необходимых обраще. ний к диску для и стековых операций? Чему равно соответствующее процессорное время? Предположим, что стек реализован таким образом, что в оперативной памяти постоянно находятся две страницы (в дополнение к небольшому количеству оперативной памяти, которое используется для отслеживания Глава 18.
В-деревья 535 того, какие именно страницы находятся в оперативной памяти в настоя- щее время). г) Как следует управлять страницами стека, чтобы амортизированное количество обращений к диску для любой стековой операции составляло О (1/гп), а амортизированное процессорное время— О (1)? 18-2. Объединение и разделение 2-3-4-деревьев Операция объединения (]о(п) получает два динамических массива У и У' и элемент х, такой что Ьеу[х'] < Ьеу[х] < Ьеу[х"] для любых х' Е У и х" Е У', и возвращает множество Я = У и (х) О У'. Операция разделения (зррй) представляет собой обращение операции объединения: для данного динамического множества Я и элемента х е Я она создает множество Я', содержащее все элементы из Я вЂ” (х), ключи которых меньше Йеу [х], и множество У', содержащее все элементы из Я вЂ” (х), ключи которых больше Ьеу [х]. В данной задаче мы рассматриваем реализацию этих операций над 2-3-4-деревьями.
Для удобства полагаем, что элементы представляют собой ключи и что все ключи различны. а) Покажите, каким образом поддерживать хранение в каждом узле дерева информации о высоте поддерева, корнем которого является данный узел, чтобы это не повлияло на асимптотическое время выполнения операций поиска„вставки и удаления. б) Покажите, как реализовать операцию объединения. Для данных 2- 3-4-деревьев Т' и Т" и ключа Й объединение должно выполняться за время О (1+ [Ь' — Ь" [), где Ь' и Ь" — значения высоты деревьев Т' и Т" соответственно. в) Рассмотрим пуп р от корня 2-3-4-дерева Т к данному ключу lс, множество У ключей Т, которые меньше Ь, и множество У' ключей Т, которые больше /с.
Покажите, что р разбивает У на множество деревьев (То, Т,',..., Т,'„) и множество ключей Щ, Ь'„..., к,'„), причем для всех у Е Т,' и з Е Т,' выполняется у < Й,' < з (( = 1, 2,..., т). Как связаны высоты Т и Т,'? На какие множества деревьев и ключей р разбивает У'? г) Покажите, как реализовать операцию разделения 2-3-4-дерева Т.
Воспользуйтесь операцией объединения для того, чтобы собрать ключи из У в единое 2-3-4-дерево Т', а ключи из У' в единое 2-3-4- дерево Т". Время работы операции разделения должно составлять О (18 и), где п — количество ключей в Т. (Указание: при сложении стоимости операций объединения происходит сокращение членов (телескопической) суммы.) 536 Часть Ч. Сложные структуры данных Заключительные замечания Сбалансированные деревья и В-деревья достаточно подробно рассмотрены в книгах Кнута (КпитЬ) 1185], Ахо (АЬо), Хопкрофта (Норсгой), Ульмана (1Л!тап) 15] и Седжвика (Яебйеичск) 1269].
Подробный обзор В-деревьев дан Комером (Сошег) 166]. Гибас (СтшЬаз) и Седжвик 1135] рассмотрели взаимосвязи между различными видами сбалансированных деревьев, включая красно-черные деревьв и 2-3-4-деревья. В 1970 году Хопкрофт предложил ввести понятие 2-3-деревьев, которые была предшественниками В-деревьев и 2-3-4-деревьев и в которых каждый внутренний узел имел 2 или 3 дочерних узла. В-деревья предложены Баером (Вауег) и МакКрейтом (МсСге18Ьт) в 1972 году 132] (выбор названия для своей разработки оня не пояснили). Бендер (Вепг1ег), Демейн (13егпа1пе) н Фарах-Колтон (РагасЬ-Со!юп) 137] изучили производительность В-деревьев при наличии иерархической памяти. Алгоритмы с игнорированием кзширования эффективно работают без явного знания о размерах обмена данными между различными видами памяти.
ГЛАВА 19 Биномиальные пирамиды В данной главе и главе 20 представлены структуры данных, известные под названием сливаемых пирамид (гпегаеаЫе пеарз), которые подцерживают следующие пять операций. МАКЕ НЕАР() создает и возвращает новую пустую пирамиду. 1изеит(Н, х) вставляет узел х (с заполненным полем йеу) в пирамиду Н. М~ммим(Н) возвращает указатель на узел в пирамиде Н, обладающий минимальным ключом. Ехтклст Мпч(Н) удаляет из пирамиды Н узел, ключ которого минимален, возвращая при этом указатель на этот узел. Ш~10х(НН Нз) создает (и возвращает) новую пирамиду, которая содержит все узлы пирамид Н1 и Нз.
Исходные пирамиды при выполнении этой операции уничтожаются. Кроме того, структуры данных, описанные в этих главах, подцерживают следую- щие две операции. Весиелзе Кеу(Н, х, 1с) присваивает узлу х в пирамиде Н новое значение ключа Й (предполагается, что новое значение ключа не превосходит текущего)'. азам.ете(Н, х) удаляет узел х из пирамиды Н. 'Как упоминалось во введении к пятой части книги, по умолчанию сливаемые пирамиды являются неубывающими сливаемыми пирамидами, так что к ним применимы операции М~ямпм, Ехтклст Мьч и 0пскааза Кау.
Мы можем также определить невозрастающие сливаемые пирамиды с операциямн Млх~мпм, Ехтклст Мах и 1нскалза К ау. Часть Ч. Сложные структуры данныз 538 Как видно из табл. 19.1, если нам не нужна операция ()н!о!ч, вполне хорошо работают обычные бинарные пирамиды, использовавшиеся в пирамидальной сортировке (глава 6). Все остальные операции выполняются в бинарной пирамилс в худшем случае за время 0 (18 и). Однако при необходимости поддержки опера. цни ()н!он привлекательность бинарных пирамид резко уменьшается, посюльку реализация операции (Лч!он путем объединения двух массивов, в которых хранят. ся бинарные пирамиды, с последующим выполнением процедуры М!н НеАе!Рт, как показано в упражнении 6.2-2, требует в худшем случае времени 6 (п). Таблица 19.1.
Время выполнения операций у разных реализаций слнваемых пирамид Процедура Бинарная пирамида (нанхулшнй случай) Пирамида Фнбоначчи (амортнзнрованнас время) Бнномнальная пирамида (наихудший случай) 6(1) 6(1) 6(1) 0(18 ц) 6(1) 6(1) 0(1я и) 6(1) 6(!я и) 6(1) 6(1я ц) 6(п) 6(18 п) 6(18 ц) 6(1) 0()в ц) 0()б и) 6(1я и) Й(!я ц) 6(18 и) 6(18 ц) МАКЕ НЕАР !н5ект Мммим Ехтклст Мгн ()н!он РескеА5е Кеу РЕЬЕТЕ В данной главе мы познакомимся с биномиальными пирамидами, время выполнения операций в наихудшем случае для которых также показаны в табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
