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

Троеточие '... ', в бинарном дереве (13), означающее дополнительных братьев в левой части семейства, содержащего ®, также может быть пустым. Приятная инФормация о поворотах заключается в том, что при этом изменяются только три связи: правая связь из ®, левая из ® и указатель сверху.

Повороты сохраняют порядок симметричного обхода бинарного дерева и обратный порядок обхода леса. (Заметим также, что повороты бинарного дерева естественным образом соответствуют применению аееациаишвнога закона (од) = и(» ) (14) в алгебраической Формуле.) сделано для ьввлк! н$апаса.ого 26 КОМВИНАТОРНЫй ПОИСК Для генерации всех бинарных деревьев или лесов посредством поворотов можно воспользоваться простой схемой, очень похожей на классическнй рефлексивный код Грея для и-кортежей (алгоритм 7.2.1.1Н) и метод простых изменений для перестановок (алгоритм 7.2.1.2Р). Рассмотрим лес из и — 1 узлов, с я корнями ®, ..., ®.

В таком случае существует к+ 1 лесов из и узлов, которые имеют одну и ту же последовательность первых и — 1 узлов в обратном порядке обхода с последней вершиной ®; например, при л = 3 это ФЙК'32Ц полученные последовательными поворотами ®, ® и (1!) влево. Кроме того, в крайних случаях, когда ® находится справа или вверху, можно выполнять любой требующийся поворот над остальными и — 1 узлами, поскольку узел ® не находится на указанном пути. Таким образом, как замечено в работе Д,М. Ьпсаз, О.

Кое!апФз тап Вагоаащ4еп апб Р. Нпзкеу, Х А)йогй!ипз, 16 (1993), 343-366, можно расширить любой список (и — 1)-узловых деревъев до списка и-узловых деревьев, просто позволив узлу ® "прогуливатъся" назад и вперед. Уделив внимание низкоуровневым деталям, можно въшапнить указанную работу с замечательной эффективностью. Алгоритм Ь (Связанные бинарные деревъя путем поворотов). Алгоритм генерирует все пары массивов !е!«...1„н г«...г„, представлякнцих собой левые и правые связи п-узловых бинарных деревьев, где !е — корень дерева, а связи (!«, г«) указывают соответственно левое и правое поддеревья л-го в симметричном порядке обхода узла.

Каждое дерево получается из предшественника путем простого поворота. Два вспомогательных массива Й«... Й„и оео«... о„, представлявнцие обратные указатели и направления, используются для управления процессом. Ь1. [Инициализация.[ Установить 1; - О, г — у+ 1, й - у — 1 и о, - -1 для 1< у < и. Установить также!е -ое -1, 1„-г„-О, й„— п — 1 и о„— — 1. Ь2. [Посещение.[ Посетить бинарное дерево илн лес, представленные !е!«...1„ и 1 « ...г„. Затем установить,у - п и р - О.

1 3. [Поиск !.! Если оу > О, установить тп - 1. и перейти к шагу Ьб, если п«ф О. Если о < О, установить гп ~ — й~", затем перейти к шагу 1А, если гп ф О; в противном случае установить р ~- 1. Если и = О, в любом случае установить о - -о, — у — 1 и повторить этот шаг. Ь4. [Поворот влево.] Установить г — 1;, 1, — и«, х - й и й — л. Если и = = О, установить !р — 1, в противном случае установить г — у. Вернуться к шагу Ь2. Ьб. [Поворот вправо.[ Завершить работу программы, если у = О. В противном случае установить !1 - г„„г +- у, /су — т, х - й . Если л = О, установить 1„- гп, в противном случае установить г„- т.

Вернутъся к шагу 12. 1 сделано для вълкпИаааса.огЕ 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМВИНАТОРНЫХ ОВЪЕКТОВ 21 В упражненни 38 доказывается, что алгоритму 1 требуется только около девяти обращений к памяти на генерацию одного дерева; таким образом, он почти такой же быстрый, как и алгоритм В. (Фактически можно сэкономить два обращения к памяти на шаг, если хранить количества деревьев о„, 1„и й„в регистрах. Но, конечно, так же может быть ускорен и алгоритм В.) В табл. 3 показана последовательность бинарных деревьев и лесов, посещенных алгоритмом 1 при и = 4, с некоторыми вспомогательными таблицами, которые способствуют дальнейшему пониманию процесса. Перестановка дз аздзае перечисляет узлы в прямом порядке обхода, в то время как они перечисляязтся в обратном порядке обхода и лесу (симметричном порядке в бинарном дереве); обратной к данной перестановке является перестановка р1 рзрзр4 в табл.

1. "Со-лес" представляет собой сопряжение 1отражение слева направо) леса; а числа изизизиз аналогичны ззззвзз4 в табл. 2. В последнем столбце показан так называемый "дуальный лес". Важность всех этих величин поясняется в упражнениях 11-13, 19, 24, 26 и 27. Связи 1оД... 1о и гз...

г„в алгоритме Ь и табл. 3 ие сравнимы со связями 14... 1„ и г4...г„в алгоритме В и табл. 2, поскольку алгоритм 1 сохраняет снмметрич- Таблица 3. Бинарные деревья н леса, сгенерированные прв помовш поворотов для п = 4 Ы2141414 г2гзгзг4 Й2взлзл4 БинаРное Лес 424здз44 Со-лес и2изизи4 дуальный дерево лес 1234 "! 1243 1 " 1000 Л ° д 1423 Л ' 2000 42~ 3100 2 р 2100 442 О1ОО ° 1 озао 3200 ° ° 1 3210 ° , ° , 0210 4 ° ° ° .

1 0010 4 4 1010 й ' ЗО1О ° т ° сделано для 14гиьтЛпГапаза.ого 10000 2340 0123 10003 2400 0122 10002 4300 0121 40001 2300 0120 40021 3000 0110 10023 4000 0111 10020 3040 0113 30010 2040 0103 40013 2000 0100 40123 оооо оооо 30120 0040 0003 20100 0340 0023 20103 0400 0022 40102 0300 0020 1122 'д2 ' ~ 2222 ° т ° 1324 й Р 2 3124 442 ~ 2221 3214 ах ° ° 2134 ) 4 22143 421З 22 КОМБИНАТОРНЫЙ ПОИСК ный/обратный порядок обхода, в то время как алгоритм В сохраняет прямой порядок обхода. Узел Й в алгоритме 1 представляет собой Й-й узел слева направо в бинарном дереве, так что для указания корня требуется значение 1е, в алгоритме В узел к представляет собой к-й узел в прямом порядке обхода, так что в этом случае корнем всегда является узел 1.

Алгоритм Ь обладает тем интересующим нас свойством, что на каждом шаге изменяются только три связи; но в действительности в этом отношении его можно улучшить, если придерживаться соглашение о прямом порядке обхода из алгоритма В. В упражнении 25 представлен алгоритм, который генерирует все связанные деревья или леса путем изменения только двух связей на каждом шаге, сохраняя прямой порядок обхода. Одна связь становится нулевой, в то время как вторая— ненулевой. Этот алгоритм "обрезки и прививки"„третий из обещанных красивых алгоритмов, имеет только один недостаток: его управляющий механизм существенно сложнее, чем у алгоритма 1, так что ему требуется примерно на 40% больше времени на вычисления.

Количество деревьев. Существует простая формула для общего количества вы- водимых алгоритмами Р, В, Х и 1 деревьев, а именно: с. - —, ( ") - ( ") — ( ",); зп2т факт был доказан в формуле 2.3.4.4-(14), Первыми несколькими значениями п = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 С„ = 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 Они называются числами Каталана (Сасв1вл пшпЬетв) — по имени Эжена Каталана (Еп65пе Саса1ап), который написал о них несколько важных статей (,уопгпа1 21е шаФЬ., 3 (1838), 508-516; 4 (1839), 95-99).

Приближение Стирлинга дает нам асимптотическое значение 4" / 9 145 1155 36939 8 128 1828 22788 ~ ~)' в частности, мы можем сделать вывод, что С„ ь 1 Г Зй /кз'1'1 и — = — ~1+ — + 01 — )) при ~й~ 4 —. 4ь ~ 2п 1 п2)) 2 (17) (Само собой, С 2!С„в точности равно (в+1)/(4п — 2) согласно формуле (15).) В разделе 2.3.4.4 была выведена также производящая функпия С(з) =Со+Сгх+Ств +Сзз +" = 1 — ~/Г: 4з (18) 22 и доказана важная формула г 2п+г — 1 2п+г — 1 2п+г — 1 (19) см. ответ к упражнению 2.3,4.4-33 и уравнение (5.70) в СМагй.

СДЕЛаНО ДЛЯ МгиГЬН1П$анаСа.ОГД 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМВИНАТОРНЫХ ОВЪЕКТОВ 23 Эти факты дают нам более чем достаточно информации для анализа алгоритма Р для лексикографической генерации вложенных скобок. Очевидно, что шаг Р2 выполняется С„раз; затем шаг РЗ чаще всего выполняет простое изменение и возвращается к шагу Р2. Как часто происходит переход к шагу Р4? Все просто: это количество раз, когда на шаге Р2 т = 2п — 1. Величина т — это положение крайней правой скобки '(', так что т = 2п — 1 ровно С'„1 раз. Таким образом, вероятность того, что на шаге РЗ устанавливаехся т — т — 1 н происходит возврат к шагу Р2, равна (ф— С„1)/С„= 3/4 согласно формуле (17).

С другой стороны, пусть при переходе к шагу Р4 нам нужно установить а — ')" и аь - '(' ровно А — 1 раз на каждом шаге. Количество случаев, когда 5 > х, равно количеству вложенных строк длиной 2п, заканчивающихся тривиальными парами О... О в количестве к штук, а именно С„к. Таким образом, общее количество изменений а и аь алгоритмом на шаге Р4 с учетом формулы (17) равно С„.1+С„2+ +С1 =С„~ + + + )— С~и-1 Св — 2 С,~ (20) ~т1 1+ +С итак, сделанное ранее утверждение об эффективности данного алгоритма доказано.

Более глубокому пониманию способствует изучение рекурсивной структуры (5), лежащей в основе алгоритма Р. Последовательность А)ч в этой формуле имеет С элементов, где Сро Ср12 1) + Сф 1)о ПРИ О » Р» »9 ф О) Соо 1 (21) а при р < О илн р > д значение С,„= О. Так мы можем сформировать треугольный массив Сзз С24 С24 С С С Сзо С4о Соо В нем каждый элемент представляет собой сумму ближайших соседей сверху и слева; на диагонали в нем находятся числа Каталана С„= С„„.

Элементы этого треугольника имеют древнее происхождение, ведущее отсчет от работ Муавра в 1711 голу, и называются "баллотировочными числами" (ЬаЛох пшпЬехз), поскольку представляют последовательносхи р+ д бюллетеней, для которых подсчет голосов ни в какой момент не покажет перевеса кандидата с р голосами нод кандидатом с д голосами. Общую формулу С сделано для мги1ьклп$апа1а.ого (23) Соо С С Соз С12 С22 Соз С1з Сзз Со4 Сы Сы Соо Схз Сзо Соо Сы Сто 1 1 1 1 2 2 — 1 3 5 5 1 4 9 14 14 1 5 14 28 42 42 Соо 1 6 20 48 90 132 132 24 КОМБИНАТОРНЫЙ ПОИСК 7.2.1 можно доказать как по индукции, так и многими другими способами (см. упражнение 39 и ответ к упражнению 2.2.1-4). Заметим, что согласно формуле (19) мы С, = (зР) С(э)~ Р+'. (24) При и = 4 алгоритм Р, по сути, описывает дерево рекурсии (25) поскольку иэ спецификации (5) вытекает, что А„„= (А(„О„и Ард = ) (А(р Ор,)" (А(р гцр+г)„) (А(р 0(р.„щ,...,(А(р Од приО<р<д.