AOP_Tom1 (1021736), страница 159
Текст из файла (страница 159)
Установить Н +- НЕ1ИК(Н) и прекратить выполнение алгоритма с Ц <- Н, если Р = ШМК(Н) В противном случае не устанавливать или устанавливать Ц <— ШМК(Ц) до тех пор, пока не выполнится условие БОТАС(Ц) = 1; затем установить Ц < — ШИК(Ц) и прекратить выполнение алгоритма. А Среднее время выполнения алгоритма Г для произвольного узла Р дерева равно 0(1). Действительно, если подсчитать только шаги Ц с в ШИК(Ц), когда Р— правый потомок, или только шаги Н +- Н1.1МК(Н) когда Р— левый потомок, то обход каждой связи будет выполнен в точности для одного узла Р. Строки 06-09 нужно заменить строками ТЗ ЕИТ4 О.
6 506 АЧА11 162 ОЧЕНР50М ЫХ 0,60.1МК) БТХ АЧА11 БТБ 0,6(1ИРО) БТ4 0,6(ЬТМК) Строки 12 и 13 нужно заменить строками Ы4 0,6(11МК) 505 0,6(1МРО) ЬОХ АЧАП. БТХ 0,6(ЬТМК) БТБ АЧАП. ЕИТБ 0,4 20. Если в строку 06 добавить еще две строки ТЗ ЬОЗ 0,5(ЕЫМК) 332 ТБ Пе ей р ти к шагу Т5, если 1.1.1МК(Р) = Л. с соответствующими изменениями строк 10 и 11, то время выполнения программы (ЗОп+ а+ 4)п сократится до (27а+ бп — 22)и.
(Аналогично можно было сократить время выполнения программы Т до (12а + бп — 7)п, что несколько меньше при а = (и+ 1)/2 ) 21. Приведенное ниже решение Джозефа М. Морриса [уозерЬ М. Могпз, 1пб Ргос. Ъеггеш 9 (1979), 197 — 200] позволяет совершить обход только в прямом порядке (см.
упр. 18). Ш. [Инициализация.] Установить Р +- Т и Н +- Л. П2. [Обход завершен?) Если Р = Л, прекратить выполнение алгоритма. ПЗ. [Обход слева.] Установить Ц г- ШИК(Р). Егли Ц = Л, посетить узел ИООЕ(Р) в прямом порядке и перейти к шагу ()б. 114. [Поиск связи-нити.] Ни разу не устанавливать или устанавливать Ц +- Н51МК(Ц) до тех пор, пока не выполнится либо условие Ц = Н, либо условие НЫМК(Ц) = Л.
1)5. [Вставка или удаление связи-нити,] Если ц ф Н, установить Ы.1ИК(Ц) г- Р и перейти к шагу П8. В противном случае установить М1.1МК(Ц) +- Л (связь-нить временно была установлена в Р, а теперь совершим обход левого поддерева Р). ()б. [Посещение в симметричном порядке.] Посетить МОНЕ(Р) в симметричном порядке. ПТ.[Переход вверх или вправо.] Установить Н +- Р, Р +- Н51МК(Р) и вернуться к шагу 1)2. 1)8. [Посещение в прямом порядке.] Посетить ИООЕ(Р) в прямом порядке.
1)9. [Переход влево,] Установить Р +- ьь1МК(Р) и вернуться к шагу 113. 5 Моррис также предложил несколько более сложный способ обхода дерева в обратном порядке. Совершенно иное решение было найдено Дж. М. Робсоном [1. М. ВоЬзоп, 1лб Ргос. 1еггегз 2 (1973), 12-14].
Назовем узел заполненным, если его связи 111МК и НЬТИК не пусты, и назовем его пустым, если обе его связи ШИК и Н11МК пусты. Робсон нашел способ организации стека указателей на заполненные узлы, правые полдеревья которых посещаются во время обхода дерева, используя поля связи из пустых узлов! Еще один способ избежать использования вспомогательного стека был независимо найден Г. Э. Линдстромом и В.
Двайером [С. Ь|пг(зггош апг) В. 1)ъуег, 1пб Ргос. Ееггегз 2 (1973), 47-51, 143-145]. В их алгоритме обход дерева совершается в глройнозг порядке ((шр(е оп(ег), т. е. каждый узел посещается в точности три раза: один раз — в прямом, 05 53 ВВБ 04 152 05 О4 СИР Б 06 ЗЕ 07 ЕИТ4 06 ЬВБ 00 1652 1,4(Н11ИК) О, Б Я11ИК) 53 1,6®1.1ИК) 7151Т 1,БЯВ1ИК) Оз 10 ОБ 5ТБ 11 59 ЬВБ 12 ЗМР 15 БН БТЕ 14 Об )МР 15 ОТ ВВ5 16 62 1552 а — 1 17 ВОИЕ второй — в симметричном, а третий — в обратном порядке.
Но при этом неизвестно, какой из порядков задействован для посещения узла в текущий момент. ЪЧ1. [Инициализапия.] Установить Р з — Т и Ц +- 5, где Б — это значение метки, т. е. любое число, которое наверняка отличается от значении любой другой связи в данном дереве (например, — 1). ЪЧ2. [Пропуск пустой связк.] Если Р = Л, установить Р +- Ц и Ц +- Л. ЖЗ. [()бход завершен?] Если Р = 5, прекратить выполнение алгоритма.
(По завершении работы алгоритма получим Ц = Т.) ТАГ4. [Посещение узла.] Попасть в узел ИОВЕ(Р). ЖБ. [Обращение.] Установить Н <- Ы.1ИК(Р), 1Л.1ИК(Р) е- %П.1ИК(Р), Ю.1ИК(Р) +- Ц, Ц < — Р, Р+- Н и вернуться к шагу Ч(2. 4 Справедливость алгоритма следует из того, что есви начать шаг %2 со значением Р, указывающим на корень бинарного дерева Т, и значением Ц, указывающим на Х, где Х не является связью в этом дереве, то данный алгоритм трижды выполнит обход дерева и достигнет ш га Ч(3 со значениями Р = 1 и Ц = Т. Если о(Т) = х(хг .. хз является результирующей последовательностью узлов в трой- ном порядке обхода, то в таком случае получим а(Т) = Та(12.1ИК(Т) ) То(Ы.1ИК(Т) ) Т. Сле- довательно, как и заметил Линдстром, три подпоследовательности х(хз ..
хз -з хзхз ..хзч-(( хзхе... хз содержат все узлы дерева, причем каждый из них встречается в них всего один раз. (Так как узел х а, является либо родителем> либо потомком узла хз, эти подпоследовательности посещают узлы таким образом. что каждый из них находится на расстоянии не более трех связей от своего предшественника.
В разделе 7.2.1 описыва- ется общая схема обхода, которая назь(вается прлз(ообратнмм порядком (ргероз(оп)ег) и обладает этим свойством не только в отношении бинарных деревьев, но и деревьев общего типа.) 22. В этой программе применяются обозначения и соглашения, используемые в програм- мах Т и 8, с Ц в регистре г16 и/или г14. Старомодный компьютер И11 не очень подходит для сравнения индексных регистров. поэтому. переменная Н опущена и проверка условия Ц = Н заменена проверкой условия Ы.1ИК(Ц) = Р. 01 51 ВВБ НЕАВ(ВО1ИК) 1 ((.
и 02 52А 152 ВОИЕ 1 Если Р = Л, прекратить выполнение алгоритма. ( ( — УЗ Об» .( (( Об и+а — 1 Перейти к шагу ()б, если Ц = Л. 1,Б(НЬ1ИК) 2н — 2Ь (74. Поиск связи-нити. 5Р 2п — 2Ь Совершить переход, если Ю.1ИК(Ц) = Р. О,б 2п — 2Ь вЂ” а ч- 1 г14 +- Ц. 1,6ЯЬ1ИК) 2п — 2Ь вЂ” а+1 64 2п — 2Ь вЂ” а+1 Перейти к шагу 114 с Ц е- НЬ1ИК(Ц), если это значение Ф О. а — 1 П5а. Вставка связи-нити. Н11ИК(Ц) +- Р. ~ю.дед вм ( (, а — 1 Перейти к шагу ()3. а — 1 (75Ь.
У аленке связи-ннти. Ы.1ИК(Ц) +- Л. и ((6 Песе ение в снммет ичном по я.ке. и (77 Пе ехо вве х илн вп аво. Р < — Н1.1ИК(Р) и Ы. Оа*ы~~лю П р и(„ если Р ~ Л. Общее время выполнения равно 21п+ба — 3 — 146, где и — количество узлов, а — количество пустых связей Н1.1МК (следовательно, а — 1 — это количество непустых связей ШМК), 6— количество узлов на "правом хребте" дерева Т, НЕ1МК(Т), НЕ1МК(НЕ1МК(Т)) и т. д. 23.
Вставка узла справа: НЕ1МКТЩ) +- НЕ1МКТ(Р), НЕ1ИК(Р) + — Ц, НТАО(Р) Е- О, ШМК(Ц) е — Л. При вставке узла слева при условии, что ШИК(Р) = Л, нужно выполнить следующие действия: установить ШИК(Р) +- Ц, ШМК(Ц) е — Л, Н11МКЩ) +- Р, НТАОЩ) +- 1. Вставка узла слева между Р и ШМК(Р) ЭА Л: установить Н е — ШМК(Р), ШМК(Ц) +- Н, а затем не устанавливать или устанавливать Н +- НЕ1ИК(Н) до тех пор, пока не выполнится условие НТАО(Н) = 1;и наконеп, установить НЕ1МК(Н) +- Ц, ШМК(Р) е- Ц, НЕ1ИК(Ц) е- Р, НТАО(Ц) +- 1.
(В последнем случае люжно использовать более эффективный алгоритм, если известен такой узел Р, что Р = ШИК(Р) или Р = НЕ1МК(Р). Например, если предположить, что выполняется последнее из этих двух раненстн, можно установить 1ИРО(Р) ег 1МРО(Ц), НЕ1МК(Р) +- Ц, ШМКЩ) +- Р, НЕТМК(Р) +- Ц, НТАО(Р) е- 1. Хотя для выполнения этих действий потребуется фиксированное время, в общем случае их не рекомендуется использовать, поскольку при этом повсюду в памяти компьютера придется ныполнять интенсивный обмен содержимым узлов.) 24. Нет, как видно из этого примера.
25. Сначала методом индукции по количеству уэлон дерена Т докажем (Ь), а затем аналогично — (с). Для доказательства (а) рассмотрим несколько случаев Обозначим Т «г Т', если выполняется условие (1), обозначим Т -сг Т', если выполняется условие (й). и т, д. Тогда из Т «г Т' и Т' «Т ' следует Т «г Т"; Т «г Т' и из Т' «Т" следует Т «г Т"; оставшиеся два случая доказываются методом индукции по количеству узлов в дереве Т. 26. Если в результате двойного порядка обхода дерева Т получена последовательность (им Иг), (иг,Иг),, (иею Иг„), где и — это узлы и Иг равны 1 или 2, построим "след" дерева (щ,зг)(ш,нг) .
~(огн,зг ), где н, = 'т(о(и), аз, =!(и) или г(и) в зависимости от того, Ы, = 1 или 4, = 2 соответственно. Теперь Т .« Т' тогда и только тогда, когда определенный выше след дерева Т лексакографически предшествует или равен следу дерева Т'. Формально это значит, что либо и < и' и (о„нг) = (о,', з„') для 1 < у < и, либо есть такое А, для которого (оы н,) = (ь', з,') для 1 < у < А и либо ьз «о[., либо гь = оь и ег < э[. 27. К1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
