31. [34] (М. л. Фредман (М. L. Fredman), 1975.) Придумайте представление линейных списков, такое, что вставка нового элемента между позициями m - 1 и m при данном т требует O(logm) единиц времени.

32. [М27] Даны два бинарных дерева с п узлами - Г и Т. Будем говорить, что Т::< Т, если Т может быть получено из Т с помощью последовательности из нуля или нескольких поворотов вправо. Докажите, что Т -< Т тогда и только тогда, когда Гд, < rjj для 1 < к < п, где r-fe и гк означают соответственно размеры правых поддеревьев fc-x узлов (в симметричном порядке) деревьев Т и Т.

► 33. [25] (А. Л. Бухсбаум (А. L. Buchsbaum).) Поясните, каким образом можно неявно закодировать фактор сбалансированности AVL-дерева для сохранения двух битов на узел за счет дополнительной работы при обращении к дереву.

И велел Самуил подходить всем коленам Израилевым, и указано колено Вениаминово.

И велел подходить колену Вениаминову по племенам его, и указано племя Матриево; и приводят племя Матриево по мужам, и назван Саул, сын Кисов; и искали его,

и не находили.

- Первая книга Царств, 10:20-21

6.2.4. Сильноветвящиеся деревья

Обсуждавшиеся выше методы поиска были разработаны, в первую очередь, для внутреннего поиска, когда выполняется просмотр таблицы, целиком содержащейся в высокоскоростной внутренней памяти. Теперь рассмотрим внешний поиск, когда нужно получить информацию из очень большого файла, расположенного на внешних запоминающих устройствах с прямым доступом, таких как диски и барабаны (о дисках и барабанах можно прочесть в разделе 5.4.9).

Древовидные структуры довольно удобны для внешнего поиска, если выбрать подходящий способ представления дерева. Рассмотрим большое бинарное дерево поиска, показанное на рис. 29, и представим, что оно хранится в дисковом файле (поля LLINK и RLINK теперь представляют собой адреса на диске, а не во внутренней памяти). Если наивно проводить поиск в таком дереве так же, как в случае внутреннего поиска, нам понадобится около IgTV обращений к диску для вьшолнения одного поиска. При 7V, равном миллиону, это означает порядка 20 обращений к диску. Однако стоит разделить таблицу на 7-узельные "страницы", как показано на рис. 29, и при доступе к одной странице за один раз потребуется примерно в три раза меньше обращений к диску, т. е. практически поиск ускорится в три раза!

Группирование узлов в страницы фактически приводит к преобразованию бинарного дерева в "октарное" с разветвлением в каждой странице-узле на 8 путей. Если страницы будут иметь большие размеры, с разветвлением на 128 путей после каждого обращения к диску, то поиск элемента в таблице с миллионом элементов завершится при просмотре всего лишь трех страниц. Можно постоянно хранить корневую страницу во внутренней памяти, так что потребуются лишь два обращения к диску (при этом во внутренней памяти одновременно будет находиться не более 254 ключей).

Рис. 29. Большое бинарное дерево поиска может быть разделено на "страницы".

Разумеется, не следует делать страницы очень большими, так как размеры внутренней памяти ограничены и чтение большей страницы отнимает больше времени. Например, предположим, что для чтения страницы, допускающей разветвление на m путей, необходимо 72.5-1-0.05т ms. Время на внутреннюю обработку каждой страницы составит около а -f 6Igm ms, где а мало по сравнению с 72.5 ms, так что общее время поиска в большой таблице примерно пропорционально IgN, умноженному на

(72.5 + 0.05m)/lgm + 6.

Эта величина достигает минимума при m и 307; в действительности этот минимум очень "широк" - близкие к оптимальному значения достигаются при m в диапазоне от 200 до 500. На практике получение подобного диапазона подходящих значений m зависит от характеристик используемых внешних запоминающих устройств и от длины записей в таблице.

В. И. Ландауэр (W. I. Landauer) [IEEE Trans. ЕС-12 (1963), 863-871] предложил строить т-арные деревья следующим образом: размещать узлы на уровне I -\- I, лишь если уровень I почти заполнен. Эта схема требует довольно сложной системы поворотов, так как для вставки одного нового элемента может потребоваться основательная перестройка дерева. Ландауэр исходил из предположения, что поиск приходится выполнять гораздо чаще вставок и удалений.

Если файл хранится на диске и является объектом сравнительно редких вставок и удалений, для его представления подходит трехуровневое дерево, где первый уровень разветвления определяет, какой цилиндр диска будет использоваться, второй уровень разветвления определяет дорожку на этом цилиндре, а третий уровень содержит собственно записи. Такой метод называется индексно-последовательной организацией файла [см. JACM 16 (1969), 569-571].

Р. Мюнц (R. Muntz) и Р. Узгалис (R. Uzgalis) [Ргос. Princeton Conf. on Inf. Sciences and Systems 4 (1970), 345-349] предложили изменить алгоритм поиска по дереву со вставкой 6.2.2Т таким образом, что все вставки порождают узлы, относящиеся к той же странице, что и их родительский узел (если только это возможно) Если страница заполнена, начинается новая страница (если таковая имеется). Если количество страниц не ограничено и если данные поступают в случайном порядке, можно показать, что среднее количество обращений к страницам примерно равно

Нм1{Нт - 1), ЧТО ЛИШЬ не.многим больше числа обращений при использовании наилучшего т-арного дерева (см. упр. 8).

В-деревья (B-trees). Новый подход ко внешнему поиску с помощью сильновет-вящихся деревьев был открыт в 1972 году Р. Байером (R. Bayer), Э. Мак-Крейтом (Е. McCreight) [Acta Informatica 1 (1972), 173-189] и независимо от них в то же время М. Кауфманом (М. Kaufman) [не опубликовано]. Их идея, которая основана на изменчивости нового вида структур данных, называемых В-деревьями, делает возможным поиск и обновление больших файлов с гарантированной эффективностью в наихудшем случае с помощью сравнительно простых алгоритмов.

В-деревом т-го порядка называется дерево, удовлетворяющее следующим условиям.

i) Каждый узел имеет не более m потомков.

ii) Каждый узел, за исключением корневого узла и листьев, имеет не менее т/2 потомков.

iii) Корневой узел, если он не является листом, имеет минимум двух потомков.

iv) Все листья находятся на одном и том же уровне и не содержат информации.

v) Нелистовой узел с к потомками содержит А; - 1 ключей.

(Как обычно, под листом подразумевается конечный, не имеющий потомков узел. Поскольку листья не несут информации, их можно рассматривать как внешние узлы, которых нет в дереве, так что указатели на листы равны Л.)

На рис. 30 показано В-дерево порядка 7. Каждый узел (за исключением корня и листьев) имеет от 7/2] до 7 потомков, т. е. содержит 3, 4, 5 или 6 ключей. Корневой узел может содержать от 1 до 6 ключей; в приведенном на рисунке случае их 2. Все листья расположены на уровне 3. Заметьте, что (а) ключи расположены в порядке возрастания слева направо с использованием естественного обобщения концепции симметричного порядка; (Ь) количество листьев на единицу превышает ко.пичество ключей.

В-деревья порядка 1 и 2, очевидно, не представляют интереса, поэтому будем рассматривать только случай, когда m > 3. 2-3-деревья, описанные в разделе 6.2.3, представляют собой В-деревья порядка 3.

(Байер и Мак-Крейт рассматривали только нечетные т; некоторые авторы, говоря о В-деревьях порядка т, подразумевают под ними то, что мы назвали бы деревом порядка 2т -Н 1.)

Узел, содержащий j ключей и j --1 указатель, может быть представлен как

(?0,Ku?i,k2,?2,---,li-X,Kj,?, (1)

где Кх < К2 < • • < Kj, a?i указывает на поддерево с ключами между Ki и Ki+i. Таким образом, поиск в В-дереве прямолинеен: после размещения узла (1) во внутренней памяти выполняется поиск данного аргумента среди ключей К\,К2, - ,Kj. (При больших j, вероятно, удобнее воспользоваться бинарным поиском; при малых j наилучшим способом поиска будет последовательный поиск.) Если поиск успешен, значит, искомое найдено; при неудачно завершенном поиске, когда ключ находится