Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 31
Текст из файла (страница 31)
Покюките, что если свободное пространство связано в сбалансированное дерево, то можно найти как (а) наилучшую подходящую, так н (Ь) первую подходящую области за О(!ой и) единиц времени, где и — количество доступных областей (алгоритмы из раздела 2.5 выполняют поставленную задачу за О(п) шагов). З1. )84) (М. Л. Фредман (М. 1, гтейаеп), 1975.) Придумайте представление линейных списков, такое, что вставка нового элемента между позициями гп — 1 и гп прн данною тп требует 0(1ай тп) единиц времени.
ЗЗ. )МЗ7) Даны два бинарных дерева с и узлами — Т и Т'. Будем говорить, чта Т -( Т', если Т' может быть получено нз Т с помощью последовательности нз иухя нлн нескольких поворотов вправо. Докажите, чта Т < Т' тогда и талька тогда, когда г„< ть для 1 < к < и, где ть и ть означают соответственно размеры правых поддеревьев А.-х узлов (е симметричном порядке) деревьев Т и Т'. ь ЗЗ.
)Зб) (А. Л. Бухсбаум (А. 1,. ВцсвэЬацш).) Поясните, каким образам можно неявно закодировать фактор сбалансированности АЪЧ дерева дле сохранения двух битов иа узел зе счет дополнительной работы прн обращении к дереву. И велел Самуил подходить всем коленам ИЗРаылЕВЫМ, И УКаэаНО ИОЛЕНО ВЕНИаиниаеа. и велел подходить колену Венизминаву па племенем его, и указано племя Матпиева; и пливодят племя гдатпиева па мужем, и назван Саул, сын Кисов1 и исиали его, и не находили. — ПеРвая кнИга Царств, 10пео-к1 6.2.4.
Сильиоеетеищиеся деревья Обсуждавшиеся выше методы поиска были разработаны, е первую очередь, для внутреннего поиска, когда выполняется просмотр таблицы, целиком содержащейся в высокоскоростной внутренней памяти. Теперь рассмотрим внешний поиск, когда нужно получить информацию из очень большого файла, расположенного иа внешних запоминающих устройствах с прямым доступом, таких как диски и барабаны (о дисках и барабанах люжно прочесть в разделе 5.4.9). Древовидные структуры довольно удобны для внешнего поиска, если выбрать подходящий способ представления дерева. Рассмотрим большое бинарное дерево поиска, показанное на рис.
29, и представим, что оно хранится в дисковом файле (поля ШЙК и йьХИК теперь представляют собой адреса на диске, а не во внутренней памяти). Если наивно проводить поиск в таком дереве так же, как в случае внутреннего поиска, нам понадобится около 18Ф обращений к диску для выполнения одного поиска. При Аг, равном миллиону, это означает порядка 29 обращений к диску. Однако стоит разделить таблицу иа 7-узельные *'страницы", как показано на рис.
29, н при доступе к одной странице за один раз потребуется примерно в три раза меньше обращений к диску, т. е. практически поиск ускорится в три раза! Группирование узлов в страницы фактически приводит к преобразованию бинарного дерева в "октарное" с разветвлением в каждой странице-узле на 8 путей. Если страницы будут иметь большие размеры, с разветвлением на 128 путей после каж,цого обращения к диску, то поиск элемента в таблице с миллионом элементов завершится при просмотре всего лишь трех страниц, Можно постоянно хранить корневую страницу во внутренней памяти, так что потребуются лишь два обращения к диску (при этом во внутренней памяти одновременно будет находиться ие более 254 ключей).
Рис. 29. Большое бинарное дерева поиска может быть разделено на "страницы'! Разумеется, не следует делать страницы очень большими:, так как размеры внутренней памяти ограничены н чтение ббльшей страницы отнимает больше времени. Например, предположим, что для чтения страницы, допускающей разветвлеиие на гл путей, необходимо 72. 5+0.05т шв. Время на внутреннюю обработку каждой страницы составит около а+ Ый гп шэ, где а малб по сравнению с 72.5 шв, так что общее время поиска в большой таблице примерно пропорционально 16 Х, умноженному на (72.5+ 0.05ш)/)йш+ Ь.
Эта величина достигает минимума при т ж 307; в действительности этот минимум очень "широк" — близкие к оптимальному значения достигаются прн щ в диапазоне от 200 до 500. На практике получение подобного диапазона подходящих значений т зависит от характеристик используемых внешних запоминающих устройств и от длины записей в таблице. В. И. Ландауэр (%. 1.
1.апбвцег) )1ЕЕЕ Тгалз. ЕС-12 (1963), 863-67Ц предложил строить пьарные деревья следующим образом: размещать узлы на уровне 1+ 1, лишь если уровень 1 почти заполнен. Эта схема требует довольно сложной системы поворотов, так как для вставки одного нового элемента может потребоваться основательная перестройка дерева. Ландауэр исходил из предположения, что поиск приходится выполнять гораздо чаще вставок и удалений. Если файл хранится на диске и является объектом сравнительно редких вставок и удалений, для его представления подходит трехуровневое дерево, где первый уровень разветвления определяет, какой цилиндр диска будет использоваться, второй уровень разветвления определяет дорожку на этом цилиндре, а третий уровень содержит собственно записи. Такой метод называется пндсксно-последовательной организацией файла [см.
ЯАСМ 16 (1969), 569 — 57Ц, Р. Мюнц (й. Мппгя) и Р. Узгалнс (К. Вайа!ш) (Ргос. РПпсегоп Сопй оп Упс Яс)епсаэ апс) Яуэ1ешз 4 (1970), 345-349) предложили изменить алгоритм поиска по дереву со вставкой 6.2.2Т таким образом, что все вставки порождают узлы, относящиеся к той же странице, что н их родительский узел (если только это возможно) Если страница заполнена, начинается новая страница (если таковая имеется). Если количество страниц не ограничено и если данные поступают в случайном порядке, можно показать, что среднее количество обращений к страницам примерно равно ХХм/(ХХ,„— 1), что лишь немногим больше числа обращений при использовании наилучшего гл-арного дерева (см.
упр. 6). В-деревья (В-Фгеее). Новый подход ко внешнему поиску с помощью сильноветвящихся деревьев был открыт в 1972 году Р. Байером (Н. Вауег), Э. Мак-Крейтом (Е. МсСге(6Ьс) (Лога ХлХогшагка 1 (1972), 173-189) и независимо от них в то же время М. Кауфманом (М. Капйпэл) (не опубликовано]. Их идея, которая основана на изменчивости нового вида структур данных, называемых В-деревьями, делает возможным поиск и обновление больших файлов с гарантированной эффективностью в наихудшем случае с помощью сравнительно простых алгоритмов, В-деревам глчю порядка называется дерево, удовлетворяющее следующим условиям.
~) Каждый узел имеет не более гл потомков. й) Каждый узел, за исключением корневого узла и листьев, имеет не менее т/2 потомков. й) Корневой узел, если он не является листом, имеет минимум двух потомков. М) Все листья находятся на одном и том же уровне и не содержат информации. т) Нелистовой узел с й потомками содержит и — 1 ключей.
(Как обычно, под листом подразумевается конечный, не имеющий потомков узел. Поскольку листья не несут информации, их можно рассматривать как внешние узлы, которых нет в дереве, так что указатели на листы равны Л.) На рис. 30 показано В-дерево порядка 7. Каждый узел (за исключением корня и листьев) имеет от (7/2) до 7 потомков, т. е. содержит 3, 4, 5 нли 6 ключей. Корневой узел может содержать от 1 до 6 ключей: в приведенном на рисунке случае их 2. Все листья расположены на уровне 3. Заметьте, что (а) ключи расположены в порядке возрастания слева направо с использованием естественного обобщения концепции симметричного порядка; (Ь) количество листьев на единицу превышает количество ~людней.
В-деревья порядка 1 и 2, очевидно, не представляют интереса, поэтому будем рассматривать только случай, когда т > 3. 2-3-деревья, описанные в раздаче 6.2.3, представляют собой В-деревья порядка 3. (Байер и Мак-Крейт рассматривали только нечетные т; некоторые авторы, говоря о В-деревьях порядка гл, подразумевают под ними то, что мы назвали бы деревом порядка 2т+ 1.) Узел, содержащий Х ключей н Х' + 1 указатель, может быть представлен как где К~ < Кэ ( ° < К,, а р; указывает на поддерево с ключами между К; и К;.ь~. Таким образом, поиск в В-дереве прямолинеен; после размещения узла (1) во внутренней памяти выполняется поиск данного аргумента среди ключей К,, Хгт,..., К,. (При больших,у, вероятно, удобнее воспользоваться бинарным поиском; при малых Х наилучшим способом поиска будет последовательный поиск.) Если поиск успешен, значит, искомое найдено; при неудачно завершенном поиске, когда ключ находится между К; и К;+м следует загрузить в оперативную память узел, на который указывает Р;, и продолжить процесс.
Если аргумент поиска меньше Км используется указатель Ре,. при аргументе, большем К», для продолжения поиска применяется указатель Рз. Если Р; = Л, значит, поиск завершился неудачно. Приятная особенность В-деревьев заключается в простоте вставки. Рассмотрим, например. рис. 30. Каждый лист ссютветствует месту, где может быть выполнена новая вставка. Чтобы вставить новый ключ 337, просто заменим соответствующий узел (2) узлом С другой стороны, при попытке вставить новый ключ 071 (программистам на С/ С++: не примите случайно это число (071) за восьмеричную запись числа 37:-).— Прим.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
