6. yW = (+l,+l,-l,+l) y() = (+l, 0,-1, 0) у(=> = (+1,-1,+1,+1) у(> = (-1,+1,+1,+1) yW = ( 1, О, О, 0)

7. См. упр. 15.

Число 34 является, вероятно, наименьшим числом Фибоначчи F„, для которого многофазный метод не дает оптимального слияния с обратным чтением для F„ начальных серий на трех лентах. Это дерево имеет длину внешнего пути 178, что на 2 лучше, чем в многофазном методе, для которого соответствуюш;ий параметр равен 176.

8. Для Г = 4 дерево с длиной внешнего пути 13 не является T-lifo-деревом, и любое дерево с длиной внешнего пути 14 включает однопутевое слияние.

9. Используя результат упр. 2.3.4.5-6, можно рассмотреть полное (Г - 1)-арное дерево; степень "последнего" внутреннего узла лежит между 2 и Т-1. Если в нем имеется (Г-1) -т внешних узлов, то [т/{Т-2)\ из них находятся на уровне q-1, а оставшиеся - на уровне q.

11. Верно, что доказывается индукцией по числу начальных серий. Если правильное распределение S серий и две соседние серии находятся в одинаковом направлении, то существует нужное распределение меньшего, че.м 5, числа серий, но его не существует при 5=1.

12. Условия (а) и (Ь) очевидны. Если имеется какая-нибудь конфигурация в (4) для некоторого имени ленты А и некоторых i < j < к, то узел j должен быть в поддереве ниже узла i и слева от узла к по определению прямого порядка. Следовательно, случай "j - Г не может иметь места и А должно быть "специальным" именем, так как оно появляется на внешней ветви. Но это противоречит тому, что специальное имя, как мы предположили, находится на крайней слева ветви ниже узла г.

13. Узлы, пронумерованные 4, 7, 11, 13, можно преобразовать во внешние, и по отношению к ним не нужно использовать однопутевое слияние. В результате длина внешнего пути будет на единицу больше, чем в случае многофазного дерева.

15. Назовем ленты А, В и С. Построим несколько видов деревьев, каждый из которых характеризуется определенной структурой корня и листьев (внешних узлов).

Тип r(A) Корень А

Тип s(A, С) Корень А; нет С-листьев

Тип t{A) Корень А; нет А-листьев

Тип и(А, С) Корень А; нет С-листьев, нет составных В-листьев

Тип v{A, С) Корень А; нет С-листьев, нет составных А-листьев

Тип w{A, С) Корень А; нет А-листьев, нет составных С-листьев

"Составной лист" - это лист, "брат" которого не является листом. Можно получить 3-lifo-дерево типа г{А), вырастив сначала его левое поддерево типа s{B,C), а затем - правое поддерево типа г(С). Аналогично тип s{A,C) получается из типов s{B,C) и t{C); тип и{А,С) - из v{B,C) и w(C,B); тип v{A,C) - из и{В,С) и и;(С, А). Можно вырастить З-НГо-дерево типа t(A), левое поддерево которого имеет тип и{В, А), а правое поддерево - тип s(C, А), позволив вырасти его левому поддереву, за исключением его (несоставных) С-листьев и его правого поддерева. В этот момент левое поддерево имеет только А- и В-листья, так что мы можем вырастить правое поддерево всего дерева, затем выбросить А-листья из левого-левого поддерева и, наконец, вырастить левое-правое поддерево. Аналогично дерево типа w{A, С) можно образовать из и(В, А) и v{C, А). [Дерево из упр. 7 есть г(А)-дерево, построенное этим способом.]

Пусть г(п),..., w{n) обозначают минимальную длину внешнего пути среди всех деревьев соответствуюш;его типа с п-листьями, построенных с помош;ью такой процедуры. Имеем г(1) = s(l) = u(l) = О, г(2) = «(2) = w{2) = 2, t(l) = v(l) = ги{1) = s(2) = и(2) = v{2) = 00. Для n > 3 имеем

r{n) = п + mmk{s(k) + r{n - к)), u{n) - n + mmk{v{k) + w{n - к)), s{n) = n + mmk{s{k)+t{n - к)), v{n) = n + mmk{u{k) + w{n - к)), t{n) = n + minfc(u(fc) + s(n - k)), w{n) = n + mmk{u(k) + v{n - k)).

Отсюда следует, что r(n) < s{n) < u{n), s{n) < v{n) и r{n) < t{n) < w{n) для всех n; кроме того, s{2n) = t{2n -f-1) = 00. (Последнее было очевидно априори.)

Пусть А{п) - функция, определяемая правилами А(1) = О, А(2п) = 2п + 2А(п), А(2п + 1) = 2п + 1 + А{п) + А{п + 1); тогда А(2п) = 2п + А{п - 1) -f А{п -Ь 1) - (О или 1) для всех п > 2. Пусть С - константа, такая, что при 4 < п < 8

i) для четных п имеем w{n) < А{п) + Сп - 1;

ii) для нечетных п имеем и{п) и v{n) оба < А(п) + Сп - 1.

(Это в действительности справедливо для всех С > .) По индукции получаем, что эти соотношения верны для всех п > 4 (в качестве подходяш;его к выберем [n/2j ±1). Но А{п) является нижней оценкой в (9), если Г = 3 и г{п) < mm{u{n),v{n),w{n)); таким образом, мы доказали, что А{п) < Кз{п) < г{п) < А{п) + п - 1. [Здесь константа может быть уменьшена.]

17. [Этот метод использовался в программе сортировки для univac iii и в 1962 году был представлен на симпозиуме АСМ Sort Symposium.]

Чтобы перейти с уровня п на уровень п +1 во время начального распределения, введите ifci "подуровней", в которых на ленты (Т1, Т2,..., Т5) добавляется соответственно (4, 4,3, 2,1) серий к2 "подуровней" с (4,3,3,2,1) сериями, кз - с (3,3,2,2,1), к4 -- с (2,2,2,1,1), кь - с (1,1,1,1,0) сериями, где fci < an, 2 < Ьп, кз < Сп, ki < dn, къ < е„. [Если (fci,..., fcs) = (on, • • •, вп), значит, достигнут уровень п + 1.] Добавьте фиктивные серии, если необходимо дополнить подуровень. Затем выполните слияние 1+2+3 + 4+ its

серий с (Т1,..., Т5) на Т6, fci +----h 4 серий с (Т1,..., Т4) на Т5, ..., серии ifci с Т1 на

Т2, ifci - с (Т2,..., Т6) на Т1, fc2 - с (ТЗ,..., Т6) на Т2, ... и ifcs - с Т6 на Т5. 18. (Решение предложено М. С. Патерсоном (М. S. Paterson).) Предположим, запись j помещена в последовательность на ленте номер г,. По меньшей мере, Сг записей могут иметь данную последовательность г, где С зависит от объема внутренней памяти (см.

раздел 5.4.8). Следовательно, ri Н-----\-\tn\ = {N\og N).

20. Сильное Г-йГо-дерево имеет T-fifo-расстановку меток, в которой нет трех ветвей, имеющих вид соответственно

0 © © О

или А

© ©

□

или А

©

□

для некоторого имени ленты А и некоторых i<j<k<l<s. Неформально, чтобы "вырастить" некоторое А, необходимо вырастить все остальные деревья А до создания какого-либо нового А.

21. В этом дереве очень слабый порядок fifo: