Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007, страница 3

(Согласио упражнению 2.3.2-20 узел ( является потомком узла й в лесу тогда и только тогда, когда у < к и р > рь, если мы помечаем узлы в обратном порядке обхода.) Таблица инверсий с1сз... с„характеризует эту перестановку в соответствии с правилом, соглвсво которому справа от Й имеется ровно сь элемевтов, меньших к (см.

упражнение 5.1.1-7); у допустимых таблиц инверсий с1 = 0 и (10) 0< +,< +1дл 1<А< Кроме того, в упражиеиии 3 доказывается, что сь представляет собой уровень, па котором в лесу находктся к-й в прямом порядке обхцэа узел (глубина к-й левой скобки); этот факт эквивалентен формуле сь = 2й — 1 — зы В табл. 1 и упражнении 6 проиллюстрирован специальный вид соошеешсшеил (шаЫппк), при котором 2п человек за круглым столом могут одповремепяо пожать руки, причем без перекрещивания. Таким образом, алгоритм Р может оказаться полезным. Но если наша цель — генерация всех бинарных деревьев с и впутреииими узлами, представлениыми левыми связями 11(з...

1„и правыми связями г1 гз... г, то лексикографическая последовательность в табл. 1 весьма неудобна; данные, которые требуются для перехода от одного дерева к следующему за пим, яе будут легкодоступными. К счастью, существуег остроумпый альтерпативный алгоритм для непосредственной генерации всех связаняых бинарных деревьев. Алгоритм В (Випарпые деревья). Для заданного п ~ 1 алгоритм генерирует все бинарные деревья с и внутренними узлами, представляя их с помощью левых связей 11(з...

1„и правых связей г~гз...г„, с узлами, помечеииыми в прямом порядке. (Таким образом, например, узел 1 — всегда корневой, а 1ь всегда равио либо к + 1, либо 0; если 11 = 0 и и > 1, то г1 = 2.) В1. (Инициализация.) Устаиовить 1ь — 1+1 и гь — 0 для 1 < к < п; установить также 1„- г„- О, и 1„+1 - 1 (для удобства иа шаге ВЗ). В2. (Посещеиие.) Посетить бияарпое дерево, представлепиое связями 11(з...1 и г1гз...гв. сделано для мгивгдн(апаса.ого 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМВИНАТОРНЫХ ОБЪЕКТОВ 17 ВЗ.

[Поиск ).[ Установить у - 1. Пока 1 = О, устанавливать гу — О, 1, ~- у+ 1 и ) -,) + 1. Затем прекратить выполнение алгоритма, если ) > и. В4. [Поиск й и 9.[ Установить у — 11 и й — О. Пока г„> О, усгаяавливать й ~ — р иу Вб, [Продвижение 9.[ Если к > О, установить гь — О; в противном случае установить 1; — О. Затем установить г„- г,, г, +- 9 и вернуться к шагу В2. 1 [См. %. ЗйагЬе)с, ТЬеогеяса) Сотригег Ясюпсе, 57 (1988), 153-159; на шаге ВЗ используется иден Д. Корша (Л.

КогэЬ).[ В упражнении 44 доказывается, что циклы на шагах ВЗ и В4 обычно достаточно коротки. Фактически в среднем требуется менее девяти обращений к памяти для преобразования связанного бинарного дерева в следующее за ним. В табл. 2 показаны 14 бинарных деревьев, сгенерированных при и = 4, вместе с соответствующими лесами н двумя связанными последовательностями: е1еэ... е„ и эгвт... э„, определяемыми тем свойством, что узел Й в прямом порядке имеет еь дочерних узлов и эь потомков в связанном лесу. (Таким образом, оь — размер к-го левого поддерева в бинарном дереве, а эь + 1 — величина поля ЗСОРЕ в смысле 2.3.3-(5).) Следующей столбец повторяет 14 лесов из табл.

1 в лексикографическом порядке алгоритма Р, но с зеркальным отражением по вертикали. Последний столбец показывает бинарные деревья, которые представляют лес в отраженном лексикографическом (солексном) порядке. Они также представляют лес из столбца 4, но с использованием связей с левым братом и правым потомком вместо левого потомка и правого брата, Последний столбец предоставляет интересную связь между вложенными скобками и бинарными деревьями, так что вносит определенный вклад в понимание того, почему алгоритм В корректно работает (см. упражнение 19).

"'Коды Грея для деревьев. Наш предыдущий опыт работы с другими комбинаторными объектами говорит нам, что, вероятно, мы можем генерировать строки скобок и деревья путем минимальных изменений между соседними экземплярами. И действительно, существует, как минимум, три очень красивых способа добиться Рассмотрим сначала случай вложенных скобок, которые могут быть представлены последовательностью х1 э...

г„, удовлетворяющей условию (8). '*Близкий к ндеальному" способ генерации всех таких сочетаний (см. раздел 7.2.1.3) представляет собой способ, при котором мы проходим по всем возможным сочетаниям так, что на каждом шаге изменяется только один компонент х), причем изменение равно Ы или х2; это означает, что яэ каждой строки скобок мы получаем следующую за ней путем простых изменений — либо 0 ) (, либо () ) + ) ) ( вблизи (-й левой скобки. Вот один из вариантов при п = 4: 1357,1356,1346,1345,1347,1247,1245,1246,1236,1234,1235,1237,1257,1256. Любое решение для и — 1 можно расширить для случая и, беря каждый шаблон хгхэ... х„1 и позволяя х„пройти по всем допустимым значениям с использованием еяао-яоряока нли обратного к нему (см. 7.2.1.3 — (45)), двигаясь вниз от Зл — 2, а затем вверх до 2п — 1 (нли наоборот) и опуская все элементы, которые ( г„ь сделано для вьлкпИапаса.ого 18 КОМБИНАТОРНЫЙ ПОИСК 1.2,1 Таблица 2, Св«эанные бинарные деревья н сопутствужнцне объекты при п = 4 Ы«1«14 г1««гъг4 Бинарное Лес «1««е««4 «1«««««4 Солексный Левый брат~ дерево лес правый потомок 1110 1 оно 3210 0340 2000 З140 0300 2040 ЗООО ~ф 0040 2300 ззе сов 1о 0300 2040 0210 3110 1010 3010 1010 ° ° 1 ело 0010 1200 3200 Озоа 020О ~ъ 2100 3100 2зао 04оо Д 2300 4000 ф» 0300 2400 УУ~~~~ 1191 ° ( 01ОО 2100 ОПЮ зооо зааа х ' 2000 2000 2 ° ° 1000 1000 2000 4ЗОО Д.: 2000 3040 а 0000 2340 ° .

°, 0000 Алгоритм Х (Вложенные скобки, близкие к идеальным). Алгоритм посещает все п-сочетания «1 ««... «„ элементов (1,..., 2п), которые представляют собой индексы левых скобок в строке вложенных скобок, подчиняющиеся условию изменения индексов по одному. Процессом управляет вспомогательный массив д1... д„, который представляет временные цели алгоритма.

Х1. (Иннцналвзация.] Установить «1 — 21 — 1 н ду ~ — 2у — 2 для 1 < у <~ и. 112. (Посещение,] Посетить и-сочетание «1... «„. Затем установить | - и. Хй. (Поиск у.] Если «1 = д, установить д - д Е 1 (тем самым обращая младший бит), у — у — 1 н повторить этот шаг. Х4. (Финал?] Если ду — «3 четно, установить «; - «+2 и вернуться к шагу Х2. сделано для ьдедьолп$апаса,огЕ 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМБИНАТОРНЫХ ОБЪЕКТОВ 19 р»6.

(Уменьшение.] Установить 1 — е — 2. Если 1 < О, завершить работу алгоритма. В противном случае,если» < е и установить» -1+2(1 < е 11+1. Наконец, установить е +- 1 и вернуться к шагу Н2. ! 1Похожий алгоритм был описан в работе П. Вое1апСз тап Вагоне(3)еп, Х А18опйше, 36 (2000), 100-107; см. также Х(ап3, 1»з)п)ппа апб Тапа, 1пб Ргос. Хееееге, 76 (2000)„ 169-174. Ф. Раскн (Р. Нпекеу) и А. Проскуровски (А, Ргоекпгопек)) ранее в з.

А1- 3опйше, 11 (1990), 68 — 84, показали, как построить идеальные коды Грея для всех таблиц ее... е„для четных и > 4 таким образом, чтобы на каждом шаге изменялось только одно значение е на х1; однако их построение весьма сложное, и неизвестна ни одна идеальная схема, достаточно простая для практического использования. В упражнении 48 показано, что идеальная схема невозможна для нечетных п > 5,) Если наша цель состоит в генерации связанных древовидных структур, а не строк скобок, идеальности с точки зрения изменений е-индексов недостаточно, поскольку простые изменения наподобие О ) ( не обязательно соответствуют простым действиям со связями. Существенно лучший подход может быть основан на алгоритмах '"поворотов", с помощью которых мы поддерживали сбалансированность деревьев поиска в разделе 6.2.3.

Поворвш влево изменяет бинарное дерево (12) на таким образом соответствующий лес изменяется А В ~~в) С) (13) "Узел ОА становится крайним слева дочерним узлом своего правого брата". Повврош вправо, разумеется, представляет противоположное преобразование: "крайний левый дочерний узел узла ОВ становится его левым братом". Вертикальная линия на рисунках (12) означает соединение с общим контекстом — левую или правую связь либо указатель на корень. Любое из поддеревьев и, д или ы (или все они) может быть пустым.