AOP_Tom1 (1021736), страница 160
Текст из файла (страница 160)
[Инициализация [ Установить Р +- НЕАР, Р' +- НЕКО', это заголовки соответствующих списков данных правопрошитых бинарных деревьев. Перейти к шагу КЗ. К2. [Проверка поля 1МРО.! Если 1МРО(Р) «1МРО(Р'), прекратить выполнение алгоритма (Т «Т'); если 1МРО(Р) Ь 1МРО(Р ), прекратить выполнение алгоритма (Т м Т').
КЗ. [Переход влево] Если ШМК(Р) = Л = ШМК(Р'), перейти к шагу К4: если ШМК(Р) = Л ф Ы.1МК(Р'), прекратить выполнение алгоритма (Т «Т'), если ШМК(Р) ф й = ШМК(Р'), прекратить выполнение алгоритма (Т Ь Т'); н противном случае установить Р е- ШИК(Р), Р' + — ШИК(Р') и перейти к шагу К2. К4. [Конец обходаг[ Если Р = КЕАО (или, что эквивалентно, если Р' = ЕЕАО'), прекратить выполнение алгоритма (Т эквивалентно Т ). 115. [Переход вправо.] Если НТАС(Р) = 1 = НТАС(Р'), установить Р з- Н1.1МК(Р), Р' +- НЬ1ИК(Р') и перейти к шагу ВА. Если НТАС(Р) = 1 ~ НТАС(Р'), прекратить выполнение алгоритма (Т -с Т').
Если НТАС(Р) ТА 1 ле НТАС(Р'), прекратить выполнение алгоритма (Т ы Т'). В противном случае установить Р +- И1.1ИК(Р), Р' +- НЬ1ИК(Р') и перейти к шагу В2. Для доказательства справедливости этого алгоритма (и, следовательно, для понимания принципа его работы) можно методом индукции по размеру дерева Те показать, что справедлива следующее утверждение: "Начиная с шага Я2 с Р и Р', указывающими па корни двух непугтых правопрошитых би~арньгх деревьев Те и Те, выполнение алгоритлга прекращается, если Те н Те не эквивалентны, но известно, что либо Те м Тес, либо Те м Те.
Алгоритм досзнгнет шага )л4, если Те и Те яеляюпься эквивалентными с Р и Р', указывающими соответственно на узлы-последователи для узлов Те н Те в снмллетрнчном порядке". 28. Исходное дерево эквивалентно н подобно его копии. 29. Докажите методом индукции по размеру дерева Т, что справедливо следующее утверждение; "Начиная с шага С2 с Р, указывающим на корень непустого бинарного дерева Т, с Ц, указывающим на узел, который имеет пустые левое н правое поддеревья, эта процедура в конечном итоге достигнет шага Сб после установки 1МРП(Ц) +- 1ИРО(Р) и прнсоедннения копий левого и правого поддеревьев узла МОПЕ(Р) к узлу МОСЕ(Ц) и с Р и Ц, указывающими соответственно на узлы-предшественники деревьев Т и узла МОСЕ(Ц) в прямом порядке".
30. Предположим, что указатель Т в (2) равен ЬЬТМК(НЕАП) в (10). 1 1. [Инициализация.] Установить Ц +- НКАП, НЬ1МК(Ц) +- Ц. Ь2. [Продвижение.] Установить Р з — Цз (см. ниже). ЬЗ. [Прошивка.] Если КЬ1МК(Ц) = Л, установить НЬ1ИК(Ц) л — Р, НТАС(Ц) +- 1; в против- ном случае установить НТАС(Ц) +- О. Если ЬЬТИК(Р) = Л, установить ЬЬТМК(Р) < — Ц, ЬТАС(Р) +- 1; в противном случае установить ЬТАС(Р) +- О.
1 4.[Обход завершену] Если Р ф НЕАП, установить Ц +- Р и вернуться к шагу Ь2. $ На шаге Ь2 этого алгоритма предполагается активизация сопрограммы симметричного порядка обхода, как в алгоритме Т, с дополнительным условием, что алгоритм Т посещает узел НЕАП после полного обхода всего дерева. Это обозначение является удобным упрощением при описании алгоритмов обхода деревьев, поскольку не требуется повторять описание стека из алгоритма Т.
Конечно, на шаге Ь2 не может использоваться алгоритм Я, посказьку дерево еще не прошито. Но алгоритм из упр. 21 использовать можно, и благодаря этому появляется еще один удобный метод прошивки дерева без какогшлибо вспомогательного стека. 31. Х1. Установить Р л — НЕАП. Х2. Установить Ц л- Рл (используя, например, алгоритм Я модифицированного право- прошитого дерева). ХЗ.
Если Р ф НЕАП, установить АТА11 ~ Р. Х4. Если Ц ~ НЕАП, установить Р л- Ц и вернуться к шагу Х2. Хб. Установить ЬЬ1ИК(НКАП) л — Л. $ Очевидно, что возможны и другие решения, которые сокращают протяженность внутреннего цикла, хотя порялок основных шагов довольно сомнителен. Укаэанная процедура работоспособна, поскольку ни один узел не возвращается в область доступных ячеек до тех пор, пока алгоритм 5 не исследует его связи ЬЬТМК и НЬ1ИК.
Как упоминалось в тексте данного раздела„каждая из этих связей используется в точности один раэ прн полном обходе дерева. 32. М.ТМК(Ц) < — Ы.1МК(Р), ЗВС(Ц) +- ЗОС(Р), ЗОС(Р) <†Н11МК(Р) +- Ц, РЕЕВ(Ц) +- Р, РЕЕВ(БОО(Ц)) <- Ц. ЗЗ. Вставка узла МОВЕОЦ) слева и снизу узла МОВЕ(Р) выполняется довольно просто: установить ШМКТ(Ц) +- ШМКТ(Р), ШМК(Р) +- Ц, ЕТАО(Р) +- О, Н1.1МК(Ц) +- Л, Вставку справа выполнить гораздо сложнее, поскольку для этого необходимо найти эЦ, что так же сложно выполнить, как н найти Ц( (см. упр.
19). Для этого можно использовать метод перемещения узлов, который рассматривается в упр. 23. Поэтому в общем случае вставки при таком типе прошивки выполняются гораздо сложнее. Но вставки согласно алгоритму С выполняются гораздо проще, чем вставки общего типа. Действительно, процесс копирования осуществляется несколько быстрее для такого типа прошивки. С1.
Установить Р +- НЕАВ, Ц е — О, перейти к шагу С4. (Далее используются предположения и идеология алгоритма С из данного раздела.) С2. Если НЕ1МК(Р) ~ Л, установить Н ~ АУА11, ШМК(Н) +- 111МК(Ц), ЕТАО(Н) +- 1, Ы.1МК(Н) +- Л, Н(.1МК(Ц) +- 1Л.1МК(Ц) +- Н. СЗ. Установить ХМРО(Ц) +- 1МРО(Р). С4. Если ЕТАО(Р) = О, установить Н ~ АЧА1)ч ШМК(Н) +- ШМК(Ц), ЕТАООК) э- 1, М.1МК(Н) е — Л, ШМК(Ц) +- Н, 1ТАО(Ц) +- О. С5. Установить Р < — ШМК(Р), Ц +- ШМК(Ц). Сб. Если Р ф НЕАВ, перейти к шагу С2. $ Теперь этот алгоритм выглядит настолько простым, что возникают сомнения в его корректности! Алгоритм С для прошитых или правопрошитых бинарных деревьев выполняется несколько дольше иэ-за дополнительных затрат времени на вычисление Р~, Цк на шаге С5. Можно обычным образом прошить связи М.ХМК или поместить (Р в Н11МК(Р) в сочетании с методом копирования за счет заданных соответствующим образом значений Н1.1МК (Н) и Н11МКТ(Ц) на шагах С2 и С4.
34. А1. Установить Ц +- Р, а затем нн разу не устанавливать или устанавливать Ц ~- НЕ1МК(Ц) до тех пор, пока не выполнится условие НТАО(Ц) = 1. А2. Установить Н < — НПМК(Ц). Если ШМК(Н) = Р, установ ь ШМК(Н) +- Л. В противном случае установить Н е- ШМК(Н), затем ни разу не устанавливать или устанавливать Н < — Н1.1МК (Н) до тех пор, пока не выполнится условие Н11МК (Н) = Р; наконец, установить НЕ1МКТ(Н) +- МЕХМЕТ(Ц). (На этом шаге узел МОВЕ(Р) и его полдеревья удаляются нз исходного дерева.) АЗ.
Установить Ж.1МК(Ц) е- ЕЕАВ, ШМК(НЕАВ) е- Р. $ (Ключом к успеху при разработке и/или понимании этого алгоритма является построение достаточно наглядных схем состояний "до и после".) 36. Нет; см. ответ к упр. 1.2.1-15(е). 37. Если Ы1МК(Р) = НЕ1МК(Р) = Л для представления (2), положим 11МК(Р) = Л; в противном случае положим 11МК(Р) = Ц, где МОВЕ(Ц) соответствует МОВЕ(ШМК(Р) ) и МОВЕ(Ц+1) соответствует МОВЕ(Н11МК(Р)), Условие ШМК(Р) нли Н11МК(Р) = Л представлено с помощью признака в узле МОВЕ(Ц) или МОВЕ(Ц+1) соответственно.
Для этого представления потребуется от и до 2п — 1 ячеек памяти. Для принятых допущений в случае (2) потребовалось бы 18 слов памяти по сравнению с 11 словами в данной схеме. При этом операции вставки и удаления будут выполняться приблизительно с одинаковой эффективностью в любом представлении. Но данное представление не так универсально при совместной работе с другими структурами. 1. Если  — пустое дерево, то Р(В) — пустой лес.
В противном случае лес Р(В) состоит из дерева Т и леса г'(правое поддерево(В)), где корень(Т) = корень(В) и пцлдеревья(Т) = г (поддерево(В)). 2. Количество нулей в двоичном формате представления деревьев соответствует количеству десятичных разделительных знаков в десятичной системе обозначений Точная формула такого соответствия выглядит так: анап .аь+э1"01" 0...01" где 1' обозначает а расположенных подряд единиц.
3. Рассортируем в лексикографическом порядке обозначения узлов в десятичной системе обозначений Дьюи (слева направо, как в словаре), размещая более короткую последовательность аь .аь перед ее расширениями а~..аю .а„для прямого порядка обхода и после расширений — для обратного порядка обхода узлов. Таким образом, при сортировке слов, а не последовательностей чисел, для прямого порядка обхода потребовалось бы разместить слова каш и кашаракша в обычном порядке следования слов в словаре. А для получения обратного порядка обхода придется обратить исходное расположение слов: кагларакша, каш. Эти правила легко доказать методом индукции по размеру дерева. 4.
Да, справедливо, и это легко доказать методом индукции по количеству узлов дерева. б. (а) Симметричный. (Ь) Обратный. Формулировка строгого доказательства эквивалентности этих алгоритмов обхода на основе метода индукции представляет собой довольно интересную задачу. 6. Прямой порядок обхода дерева Т = прямой порядок обхода дерева Т', обратный порядок обхода дерева Т = симметричный порядок обхода дерева Т', даже если Т имеет узлы только с одним ребенком. Остальные два порядка не имеют прос гой взаимосвязя, например корень дерева Т находится в конце в одном случае и приблизительно в середине — в другом случае. 7.
(а) Да, (Ь) нет, (с) нет, (б) да. Обратите внимание, что порядок. реверсивный прямому порядку обхода леса, эквивалентен обратному порядку правопрошитого реверсивного леса (как при зеркальном отражении). 8. Т "С Т' означает, что либо ш1о(корень(Т)) м 1п(о(корень(Т')), либо информация, содержащаяся в корнях, эквивалентна и выполняется следующее условие предположим.
что Тп..., Т являются поддеревьями корня дерева Т, а Т,',, Т„', — поддеревьями корня дерева Т, и допустим, что й > 0 такое максимально возможное, что Тз эквивалентно Тз для 1 < у' < к. Тогда либо и = п, либо lс < и и Тээ~ .~ Ть',, 9. В непустом лесу количество неконцевых узлов на один меньше количества правых связей, равных Л, потому что все пустые правые связи соответствуют крайнему справа ребенку каждого неконцевого узла, а также корню крайнего справа дерева в этом лесу. (На основании данного факта можно привести еще одно доказательство упр. 2 3.1-14, так как количество пустых левых связей, очевидно, равно количеству концевых узлов.) 10. Эти леса подобны тогда и только тогда, когда и = и' и г1(п~) = Ы(и') для 1 < у' < и; они эквивалентны тогда и только тогда, когда, кроме того, !пЕо(из) = ш1о(н',), 1 < у' < и.
Это доказательство выполняется аналогично предыдущему доказательству на основе обобщения леммы 2.3.1Р, где следует допустить, что ((и) = И(и) — 1. 11. Установить Н11МКТ(Н) +- НЕТМКТ(Ц). Н11МК(Ц) <- Н, НТАИЦ) +- О. СЗ Копи рвание анных т е поля 1МГО Пале ТУРЕ скопировано. С4.
Есть ли ел слева? Если ШМК(Р) ф Л, выполнить переход 12. Если 1МГО(Ц1) ф О, Установить Н < — СОРУ(Р1); если ТУРЕ(Р2) = О и 1МГО(Р2) ЧА 2, Уста- новить Н+- ТНЕЕ("7",ТНЕЕ(1ИГО(Р2) — !)); если ТУРЕ(Р2) ф О, установить Н < — ТНЕЕ("7",Н. ТНЕЕ(" †",СОРУ(Р2),ТНЕЕ(!))); затем установить Ц! <- И~Л.Т(01,МОЕТ(СОРУ(Р2),Н)). Если 1МГО(Ц) ЗА О, установить Ц +- ТНЕЕ("х",ЮЛ Т(ТНЕЕ(")пл „СОРУ(Р1)),Ц),ТНЕЕ('7", СОРУ(Р1).СОРУ(Р2))), Наконец, перейти к шагу 01ГГ(4). 13.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
