л, и с ростка дерева

Шаг i роста дерева состоит в выборе различных имен лент В,В\,В2, ,Bk и дальнейшей замене всего образованного узла, соответствующего В,

□

Правило "последним образован - первым растет" в точности описывает способ построения представления в виде дерева непосредственно из векторного представления. Определение строго оптимальной Г-ленточной схемы слияния, т. е. дерева, имеющего минимальную длину пути среди всех Г-И£о-деревьев с данным числом внешних узлов, кажется весьма трудной задачей. Следующая неочевидная схема, например, представляет наилучший способ слияния семи начальных серий с помощью четырех лент и считывания в обратном направлении:

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

Пусть Кт{п) - минимальная длина внешнего пути, достижимая в Г-lifo-дереве с п внешними узлами. Используя теорию, развитую в разделе 2.3.4.5, несложно доказать, что

Кт{п)>пя-[{{Т-\у-п)1{Т-2)1 g=rbgt-i"l, (9)

так как это минимальная длина внешнего пути любого дерева с п внешними узлами и степенью любого узла < Т. К настоящему моменту известны относительно немногие точные значения Кт{п). Ниже приведены верхние оценки, которые, вероятно, точны.

п = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Аз(п) < О 2 5 9 12 16 21 25 30 34 39 45 50 56 61 (10) Ki{n) < О 2 3 6 8 11 14 17 20 24 27 31 33 37 40

Карп обнаружил, что любое дерево с внутренними узлами степени < Т является почти Г-lifo-деревом в том смысле, что оно может быть превращено в Г-lifo путем замены некоторых внешних узлов однопутевыми слияниями. Фактически создать подходящую расстановку меток довольно просто. Пусть А - конкретное имя ленты. Необходимо выполнить следующие действия.

Шаг 1. Присвоить имена лент ребрам схемы дерева любым способом, совместимым с условием (а), которое приведено выше, однако так, чтобы специальное имя А использовалось только в крайнем слева ребре ветви.

Шаг 2. Заменить каждый внешний узел вида

□

□

для любого в Ф А.

Шаг 3. Пронумеровать внутренние узлы в прямом порядке. Результатом будет расстановка меток, удовлетворяющая условиям (а), (Ь) и (с).

Например, если начать с дерева

и трех лент, то эта процедура расставит метки следующим образом:

Нетрудно проверить, что конструкция Карпа удовлетворяет дисциплине "последним образован - первым растет" в силу свойств прямого порядка (см. упр. 12).

Заметим, что результатом такого построения является схема слияния, в которой все начальные серии появляются на ленте А. Это предполагает следующую схему распределения и сортировки, которую можно назвать слиянием в прямом порядке.

Р1. Распределить начальные серии на ленту А, пока ввод не будет исчерпан. Пусть S - число всех начальных серий.

Р2. Выполнить описанное выше построение, используя {Т - 1)-арное дерево с S внешними узлами и минимальной длиной пути, и получить Т-lifo-дерево, длина внешнего пути которого превышает нижнюю границу (9) не более чем на S.

РЗ. Слить серии в соответствии с этой схемой.

Результат в указанной схеме получается на какой угодно ленте. Но эта схема имеет один серьезный изъян. (Видит ли читатель, что именно здесь будет неправильно работать?) Дело в том, что схема требует, чтобы первоначально одни серии на ленте А были восходящими, а другие - нисходящими в зависимости от того, где появляется соответствующий внешний узел: на нечетном или четном уровне. Не зная S заранее, эту проблему можно разрешить путем копирования серий, которые должны быть нисходящими, на вспомогательную ленту (или ленты) непосредственно перед тем, как они потребуются. Тогда суммарное количество операций, измеряемое в длинах начальных серий, окажется равным

51ogr i 5+ 0(5). (13)

Таким образом, слияние в прямом порядке определенно лучше многофазного или каскадного при 5 -> оо. В действительности оно асимптотически оптимально, так как (9) показывает, что 51og7 j 5 + 0(5) - это наименьшая оценка времени, на которую мы вообще можем надеяться при работе с Т лентами. С другой стороны, для сравнительно небольших значений 5, обычно встречающихся на практике, слияние в прямом порядке весьма неэффективно; многофазный или каскадный метод проще и быстрее, если 5 относительно мало. Возможно, удастся изобрести простую схему распределения и слияния, которая сравнима с многофазной и каскадной при небольших 5 и асимптотически оптимальна при больших 5.

Ниже, в упражнениях части 2, демонстрируется, как Карп аналогичным образом поставил вопрос для слияния с прямым чтением. Теория оказывается в этом случае значительно более сложной, хотя были получены некоторые весьма интересные результаты.

УПРАЖНЕНИЯ (часть 1)

1. [17] При слиянии с прямым чтением часто удобно отмечать конец каждой серии на ленте путем добавления искусственной "концевой" записи с ключом +оо. Как следует видоизменить этот метод при обратном чтении?

2. [20] Будут ли столбцы таблицы, аналогичной табл. 1, всегда неубывающими или возникают ситуации, когда приходится "вычитать" серии с некоторой ленты при переходе от одного уровня к другому?