Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007 (1119377), страница 25
Текст из файла (страница 25)
Алгоритм Ъ обладает тем же свойством. сделано для экэлк! н$аааса.ого ОТВЕТИ К УПРАЖНЕНИЯМ 105 24. Ув1у... 1ш = 2 0 1 0 3 0 0 6 5 О 8 0 0 12 11 4; ту... тш = О 15 0 10 7 0 О 9 0 14 13 0 О О 0; йу... йув = О 0 2 2 4 5 5 4 8 4 10 11 11 10 2; ду... 9ш = 2 1 15 4 3 10 8 5 7 6 9 14 11 13 12 и иу... иш = 12 3 1 0 0 5 О 3 1 0 0 1 0 1 О. (Если узлы леса Г пронумерованы в обратном порядке обхода, й является левым братом у; или если « — крайний слева дочерний узел р, то й = й„. Формулируя иначе, й — родитель «в лесу г'~~. И й«равно также,у — 1 — и„+у «, количеству элементов, меньших «, находЯЩихсЯ в стРоке ау...
9» слева от «.) 25. Используя подсказки из алгоритмов Х и В, мы хотим расширить каждое (и — 1)- узловое дерево в список из двух или большего количества и-узловых деревьев. Идея в этом случае заключается в том, чтобы сделать п дочерним узлом и — 1 в бинарном дереве в начале и конце каждого такого списка, Приведенный далее алгоритм использует дополнительные поля связей р«и ву, где р указывает на родительский по отношению к «узел в лесу, а ву указывает на левого брата «или на крайнего справа брата,у, если « — крайний слева в своем семействе.
(Эти указатели ру и в, конечно же, не являются перестановками ру...р» в табл. 1 или полями ву... в„в табл. 2. Фактически ву... в„представляют собой перестановки А нз упражнения 33.) М1. ]Инициализация.] Установить 1« — «+ 1, т« — О, в; — «, ру +- у — 1 и о« вЂ” — 1 для 1 < у' < и, за исключением 1„— О. М2. ]Посещение.] Посетить 1у... 1„и ту... т„, Затем установить « — и.
МЗ, [Поиск „у.] Если о«> О, установить й — р. и перейти к шагу М5, если й ф « — 1. Если о < О, установить й +- ву и перейти к шагу М4, если й ф « — 1. Если й = у — 1 в любом случае, установить оу ~ — — оу, у —,у — 1 и повторить данный шаг. М4. ]Передача вниз.] (В этот момент й представляет собой левого брата «или крайний справа член семейства у.) Если й > .у, завершить работу алгоритма, если « = 1; в противном случае установить х — р, 1, — О, г — й и й — 0 (тем самым отсоединив узел «от родительского узла и вьаедя его на верхний уровень).
Но если й < «, установить х ~- р. + 1, г +- вв, ть <- 0 и в» - й (тем самым отсоединив у от й и перенеся его на уровень вниз). Затем установить х — й + 1, У вЂ” в, в — г, в — Р, гг — «и х — «. Пока х Р О, Устанавливать р, — й и х — т . Вернуться к шагу М2. Мб. ]Передача вверх.] (В этот момент й является родителем «.) Установить х +- — й+ 1, уу ~- ву, г - в», в» - уу и т„- О. Если й ф О, установить у - рь, -,у, в — й, вв+у - г и х — «; в противном случае установить у — « — 1, 1в — «, ву — г и х +- у. Пока х уг О, устанавливать р +- уу и х — т,.
Вернуться к шагу М2. 1 Примечание о времени рабатам алгоритма: можно доказать, как в упражнении 44, что стоимость шага М3 составляет 2С„+3 (С„у + " + Су) обращений к памяти и что шаги М4 и М5 вместе стоят 8ф— 2(С„у + + Су) плюс удвоенное количество присваиваний х ~- т,. Последнюю величину трудно точно проанализировать;например,прин =15и« =балгоритмуствлавливаетх — т (1,2,3,4,5,6) раз в (45, 23, 7, 9, 2, 4) случаях соответственно. Однако эвристическн среднее количество присваиваний х — т~ должно быть примерно 2-2« " для данного «, т.е.
всего около (2С» (С» С»-у) (С» — у С» — г)/2 (С»-г С» — з)/4 ' ' ')/С» 8/7. сделано для вълк! ВГаяаса.огя 106 ОТВЕТЫ К УПРАЖНЕНИЯМ Эмпирические тесты подтверждают предсказанное поведение, поюаыввл, что общая стоимость в пересчеге на одно дерево стремится к 266/21- 12.6 обращений к памяти при и — со. 26.
(а) Необходимость условия очевидна. А если оно выполняется, можно однозначно построить К: узел 1 и его братья являются корнями леса, а их потомки индуктивно определяются непересекающимися разбиениями. (Фактически можно вычислить координаты глубины с~... с„непосредственно из ограниченно растущей последовательности П а~... а: установить с1 — 0 и 1е — О. Для 2 < у < п, если аз > гпах(аг...,ау г), установить с, - ср 1+1 и ь1, - су, в противном случае установить с; — 1в, ) (Ь) Если П и П' удовлетворяют условию непересекаемости, так что их наибольшим общим утончениемв является П У П', и можно поступить так, как в упражнении 7.2.1.5-12 (а).
(с) Пусть хм..., х — дочерние узлы некоторого узла Г и 1 < 1 < й < гп. Образуем Г' путем удавения х +м..., иь из их семейства и присоединим нх в качестве дочерних к узлу ху+1 — 1, крайнему правому потомку хз. (4) Очевидно из ответа (с).
Таким образом, леса ранжируются снизу вверх по количеству содержащихся в них внутренних узлов (которое на единицу меньше количества блоков в П). (е) Ровно ~„~, е еь (еь — 1)/2, где ее —— и — е1 — — е» вЂ” количество корней. Щ Дуализация подобна операции транспонирования в упражнении 12, но вместо левого сына н правого брата мы используем левого брата и правого сына и выполняем транспонирование относительно младшей диагонали. ("Правые" связи теперь идут вниз.
Обратите внимание, что у является крайним справа дочерним узлом й в Р тогда и только тогда, когда 1' является левым братом Й в Г'~. Прямой порядок обхода Г~' представляет собой обращение прямого порядка обхода Г, так же, как обратный порядок обхода Гт представляет собой обращение обратного порядка обхода Г.) (й) Из ответа (1) видно, что г' покрывает Р тогда н только тогда, когда Г~ покрывает Г'и.
(Следовательно, г и имеет п+ 1 — й листьев, если у Г их й,) (1,) Р х Р (Ро У Р и) и есм. рвражиение 7д.1.5-12, — Примеч. ред. сделано для ькькьклпГапаса,ого ОТВЕТЫ К УПРАЖНЕНИЯМ 107 (1) Нет. Если бы это было так, то в соответствии с дуальиостью должно было бы вьшолияться равенство. Но, иапример, 0101 Д 0121 = 0000 и 01011'0121 = 0123, в то время как 1еатеэ (0101) + 1еатеэ (0121) 1~ 1еатеэ (0000) + 1еаеее (0123)т.
[Непересекающиеся разбиеиия впервые были рассмотрены Г.Б. Беккером (Н.%. Вес1сег) в МаГЬ. Млй., 22 (1948), 23-26. В 1971 году Г. Креверас (С. Кгепегаэ) доказал, что оии образуют решетку; см. ссылки в ответе к упражнению 2.3.4.6-3.] 27. (а) Это утверждение эквивалентно упражнению 2.3.3 — 19. (Ь) Если мы представим лес с использоваиием связей с правым сыном и левым братом, то прямой порядок обхода будет соответствовать симметричному обходу бинарного дерева (см. упражнение 2.3.2-5), а е; будет равно размеру правого полдерева узла у.
Поворот влево вокруг любого внутреннего узла этого бинарного дерева уменьшает ровно одну из координат е, и величииа уменьшения настолько мала, насколько это возможно при условии корректности таблицы ет... е„. Следовательно, Г' покрывает Р тогда и только тогда, когда Е получается из гч путем такого поворота. (Поворот в представлении с левым сыном и правым братом аналогичен, ио по отиошеиию к обратному порядку обхода.) (с) Дуализация сохраняет отношение покрытия, ио заменяет "лево" иа "правое и наоборот. (4) ГТ.Р' = (Г~'1.Г'о) ~~. Таким же образом, как указывается в упражнении 6.2.3- 32, можно независимо минимизировать размеры левых поддеревьев.
(е) Покрывающее преобразование в ответе 26 (с) очевидным образом делает е < е' для всех .у. (() Истинно, потому что РдЕ < Р .1 Р.1.:ре и Ед Р'к Г' -1 Р1Р'. (8) Ложно; например, 01211~0122 = 0123 и 0121Т0122 = 0122. (Но, применяя лувлизацию к выражению из ответа (1), получим РТЕ' -1 Г У ге.) (Ь) Длиннейший путь (длиной (",)) многократно уменьшает крайнее справа иеиулевое значение еу иа 1. Кратчайший путь длиной п — 1 просто поочередно устаиавливает крайние слева ненулевые значения е равными О. Ответ к упражнению 6.2.3-32 содержит ряд ссылок иа литературу о решетках Там ври.
28. (а) Нужно просто вычислить ппп (сы с',)... ппп (с,се) и шах(ем с',)... ... шах(с„,се), поскольку с1...с является корректной последовательностью тогда и только тогда, когда с1 = 0 и су < су 1+ 1 для 1 <,у < ц. (Ь) Это очевидно вытекает из ответа (а). Примечание: элементы произвольиой дистрибутивной решетки могут быть представлены как порядковые идеалы некоторого частичного упорядочения.
Для случая, приведенного иа рис. 41, чвстичиое упорядочение имеет вид, а аиалогичиан треугольиая сетка со сторонами длиной и — 2 дает решетку Стенли порядка п. (с) Возьмем узел й леса Р, у которого имеется левый брат у. Удалим (е из его семейства и поместим его в качестве нового правого дочернего узла,у„за которым разместим его бывшие дочерние узлы в качестве дочерних узлов у; бывшие дочерние узлы (е сохраняют своих потомков. (Эта операция соответствует замене ")(' иа '()' в строке вложенных скобок. Таким образом, "идеальиыйе код Грея для скобок соответствует Гамильтоиову пути в покрывающем графе решетки Стенли. Для и = 4 Певчее() означает колнчеетео лнетьее у артунента втой функннн.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
