AOP_Tom3 (1021738), страница 119
Текст из файла (страница 119)
Поиск оказался неудачным, и теперь мы можем вставить БА01ТТАН1ОБ в то место, где завершился наш поиск, на место внепшего узла (э). Таким образом, таблица может расширяться без перемещения существукццих записей. Дерево на рис. 10 получено путем последовательной вставки в пустое дерево ключей САРН1СОНМ, АЦОАН1ОБ, Р1БСЕБ, АНТЕБ, ТАОНОБ, ОЕМ1М1, САМСЕН, ЕЕО, 71НОО, 11ВНА, БСОНР10 в указанном порядке.
На рис. 10 все ключи левого поддерева меныпе (в алфавитном порядке), чем САРН1СОНМ, а все ключи правого полдерева — больше. То же самое справедливо и для левого и правого поддеревьев любого узла. Отсюда следует, что при обходе дерева в симметричном порядке (см. раздел 2,3.1), поскольку симметричный порядок * Список знаков зодиака„упорядоченный по иеснцаи.
такое: Козерог (Саргьсогп), Водолеи (Ац1гагпга), Рыбы (Р1есее), Овен (Апее), Телец (Тапгпе), Близнецы (Сенпггг), Рак (Сапсег), Лее () ео), Дева (%ген), Весы (1льга), Скорпион (Бсогрно), Стрелец (Бафггапн*). — Прнлг. персе. основан на обходе сначала левого поддерева каждого узла, затем — самого узла, а после — правого поддерева, мы получим список ключей в алфавитном порядке: АЦОАК105, АЕ1ЕБ, САМСЕМ„ САРК1СОКМ, СЕМХМ1, ЕЕО, ..., Ч1КОО. Ниже приводится подробное описание процесса поиска со вставкой.
Алгоритм Т (Поиск по дереву со всгпввкой (Тгее веагсЬ апд (пвег(юп)). Дана таблица записей, образующая бинарное дерево. Этот алгоритм (рис. 11) предназначен для поиска данного аргумента К. Если К в таблице отсутствует, новый узел, содержащий К, вставляется в дерево в надлежащее место. Предполагается, что узлы дерева содержат, по крайней мере, следующие поля: КЕЧ(Р) — ключ, хранящийся в узле МООЕ(Р); (.Е1МК(Р) — указатель на левое поддерево узла МООЕ(Р); Ж.1МК(Р) -- указатель на правое поддерево узла МООБ(Р).
Пустые поддеревья (внешние узлы на рис. 10) представляются пустыми указателями Л. Переменная ЕООТ указывает на корень дерева. Для удобства полагаем, что дерево не пусто, т. е. ЙООТ ф Л, так как при АООТ = Л необходимые операции тривиальны. Т1.[Инициализация,[ Установить Р е- АООТ. (Переменная-указатель Р будет перемещаться вниз по дереву.) ТЗ.
[Сравнение.) Если К < КЕЧ(Р), перейти к шагу ТЗ; если К ) КЕЧ(Р), перейти к шагу Т4; и если К = КЕЧ(Р), поиск успешно завершается. ТЗ. [Перемещение влево.) Егзи ЕЕ1МК(Р) ф Л, установить Р < — Е(.1МК(Р) и перейти к шагу Т2; в противном случае перейтн к шагу Т5, Т4. [Перемещение вправо.) Если й1.1МК(Р) ф Л, установить Р +- И.1МК(Р) и перейти к шагу Т2. Тб.
[Вставка в дерево.) (Поиск оказался неудачным; теперь мы должны поместить К в дерево.) Установить Ц ~ АЧАЛ (адрес нового узла). Присвоить КЕЧ(Ц) е— К, ШМК(Ц) е — Ы.1МК(Ц) +- Л. (На практике следует инициализировать и другие поля нового узла.) Если К был меньше, чем КЕЧ(Р), следует назначить ЕЕ1МК(Р) ~- Ц; в противном случае -- назначить ЕЕ1МК(Р) <- Ц. (Теперь мы можем присвоить Р +- Ц и считать поиск успешно завершившимся.) 1 Этот алгоритм сам подсказывает нам свою программную реализацию. Предположим, например, что узлы дерева имеют структуру за которой, возможно, следует дополнительная информация 1МГО.
Используя, как и в главе 2, список свободной памяти АЧА11., мы можем написать следующую М1Х- программу. Программа Т (Поиск по дереву со вставкой). гА = К, г11 = Р, г12 = Ц. 01 ШМК ЕЦО 2:3 08 И.1МК ЕЦО 4:5 Р +- ЕООТ. Т4. Пе еме ение вп ало, Я +- 1П.1МК(Р). Переход к шагу ТЕ при Я = Л. Р <- Я. Переход к шагу Т4 при К > КЕУ(Р) . Выход, если К = КЕУ(Р) . ТЗ. Пе емешение влево.
Я е- ШМК(Р). Переход к шагу Т2 при Я )А Л. Тб. Вставка в е ево. Я 4:-- АУА11. КЕУ(Я) < — К. 111МК(Я) <- 1П.1МК(Я) +- Л. Выполнялось ли условие К < КЕУ(Р)? МЕТЕК(Р) +- Я. ШМК(Р) +- Я. Выход после вставки. 3 Рис. 11. Поиск по дереву и вставка.
Первые 13 строк программы выполняют поиск, следующие 11 — вставку. Время работы фазы поиска составляет (7С + С1 — 35+ 4) и, где С вЂ” количество выполненных сравнений:, С1 — количество сравнений, когда К ( КЕУ(Р); С2 — количество сравнений, когда К > КЕУ(Р); 5 — — 1 при успешном и О при неудачном поиске. В среднем имеем С1 = -'(С+ 5), поскольку С1+ С2 = С, а С1 — 5 имеет то же распределение вероятностей, что и С2; таким образом, время работы программы— ОУ БТАНТ ЕОА 04 101 Об ЛИР Об 4Н ЕО2 07 122 Об 1Н ЕМТ1 09 2Н СИРА 10 ,10 !1 1Е 12 ЕО2 10 12Мг Ц ЯН Ы2 10 122 1б ЫХ 17 БТХ 18 БТА 10 БТХ ЕО 11.
21 ЯТ2 ЕЕ 1ИР ЕУ 1Н БТ2 84 ООМЕ ЕЯО К КОРТ 2Г 0,1(И.1МК) ЯР 0,2 1,1 4В БОССЕББ 0,1ЫЫМК) 1В АЧА11. ОЧЕНРЕОМ 0,2(НЕ1МК) АЧАП. 1,2 0,2 1Г 0,1(И.1МК) в+2 0,1(1.1.1МК) 1 1 1 С2 С2 С вЂ” 1 С с С1 С1 — 5 С1-5 1 — 5 1 — 5 1 — 5 1 — 5 1 — 5 1 — 5 1 — 5 А А 1 — 5 — А 1 — 5 около (7.5С вЂ” 2.55+ 4)и, Как видим, это лучшее значение, чем при бинарном поиске с неявными деревьями (см.
программу 6.2.1С). Продублирован код, как зто было сделано в программе 6.2.1Р, мы можем избавиться от строки 08 программы Т, уменьшая время работы до (6.5С вЂ” 2.5о+ 5)и. При неудачном поиске фаза вставки займет дополнительное время — 14и или 15и. Алгоритм Т легко адаптировать для работы с ключами и записями переменной длины. Например, если мы распределяем имеющуюся память последовательно, по принципу ПРО ("последним вошел — первым вышел"), можно очень легко создавать узлы различных размеров — первое слово в (1) может указывать размер записи. Такое достаточно эффективное использование памяти делает алгоритмы таблиц символов, основанные на деревьях, особенно привлекательными для использования в компиляторах, ассемблерах и загрузчиках.
А как насчет наихудшего варианта? Программисты зачастую скептически относятся к алгоритму Т при первом знакомстве с ним. Ведь если бы ключи из рис. 10 посту. пали в алфавитном порядке — АЦОАК1ОЯ, ..., Ч1КОΠ— - вместо календарного, алгоритм построил бы вырожденное дерево, соответствующее последовательному поиску.
Все поля ШМВ в этом дереве были бы пустыми. Точно так же поступление ключей в несколько необычном порядке— АООАВ1ОЯ, Ч1ВОО, АВ1ЕЯ, ТАОВОЯ„ САМСЕК, ЯСОКР10, САРВ1СОВИ, Р1ЯСЕЯ, ОЕМ1М1, ЫВКА, ЕЕО— привело бы к построения> зигзагообразного дерева, что ничуть не сокращает время поиска (постройте его сами — и убедитесь). С другой стороны, для успешного поиска по дереву, изображенному на рис.
10, требуется в среднем всего 3 — „сравнений; это лишь ненамного превышает миниг мально возможное количество 3, которое достигается при поиске по наилучшему из возможных бинарных деревьев. При работе с хорошо сбалансированным деревом время поиска примерно пропорционально 1ой Х; однако в случае вырожденного дерева время поиска становится пропорциональным Ф. В упр. 2.3.4.5-5 доказывается, что среднее время поиска пропорционально ч'Х в предположении равновероятности всех бинарных деревьев с Х узлами.
Чего же нам следует ожидать от алгоритма Т7 К счастью, можно доказать, что поиск по дереву требует лишь около 2!пХ 1.3861кХ сравнений, если ключи вставляк~тся в дерево в случайном порядке. На практике в основном встречаются хорошо сбалансированные деревья, в то время как вырожденные деревья появляются редко. Доказать это утверждение на удивление легко. Предположим, что каждая из Х! возможных перестановок Х ключей с равной вероятностью используется для построения дерева путем последовательных вставок. Число сравнений, необходимых для поиска ключа, ровно на одно больше числа сравнений, необходимых для его вставки в дерево.
Таким образом, если Сн — среднее количество сравнений при успешном поиске, а С~ — при неудачном, то С'+С'+ +С' См= 1+ (2) Однако согласно соотношению между длинами внутреннего и внешнего путей (6.2.1- (2) ) См = (1 э- —.) Сд — 1. 1 (3) Объединяя (3) и (2), получим (Х + 1) См = 2Х + Се + С1 + + С~а (4) Это рекуррентное соотношение легко решается: вычтя следующее равенство ХСт-1 = 2(Х 1) + Со + С~ + ' ' ' + Ст-г из предыдущего, мы получим (Х + 1)СЬ вЂ” ХСЬ, = 2+ С~ „следовательно., Сэ~ — — С~, + 2/(Х+ 1). Так как Се — — О, то С,' = 2Нэьь1 — 2. (5) Применив (3) и выполнив некоторые упрощения, получим требуемый результат: (6) В упр.
6 — 8 приводится более детальная информация — можно определить не только средние значения Ся и С~'„но и их точные распределения вероятностей. Сортировка путем вставки в дерево. Алгоритм Т был разработан для поиска, однако он может применяться и в качестве основы алгоритма внутренней соршироекгн его можно рассматривать как естественное обобщение вставки в список — алгоритма 5.2.1Ь. Если этот алгоритм будет корректно реализован, то среднее время его работы лишь незначительно превысит время работы лучших алгоритмов, обсуждавшихся в главе 5.
После того как дерево построено, остается только симметрично его обойти (алгоритм 2.3.1Т); так мы получим записи в рассортированном виде. Тем не менее следует предпринять определенные меры предосторожности —. требуются некоторые отличия на шаге Т2 при К = КЕУ(Р) в связи с тем, что нашей целью является не поиск, а сортировка. Одно из возлшжных решений — считать, что К = КЕУ(Р) эквивалентно Еб > КЕУ(Р). Сортировка при этом будет вполне корректна (отметим, что записи с одинаковыми ключами необязательно должны находиться в смежных узлах — — важно, чтобы они последовательно встречались при симметричном обходе дерева).
Однако при наличии большого количества повторяющихся ключей этот метод может дать плохо сбалансированное дерево, и процесс сортировки окажется замедленным. Еще одним решением может служить хранение списка записей с одним и тем же ключом для каждого из узлов. В этом случае потребуется дополнительное поле ссылок, однако при большом числе повторяющихся ключей такая сортировка окажется более быстрой. Таким образом, применение алгоритма Т только для сортировки является неплохим, хотя и не лучшим, решением. Однако этот алгоритм настоятельно рекомендуется использовать в случае комбинирования в одном приложении как поиска, так и сортировки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
