Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 17
Текст из файла (страница 17)
Рассмотрев соответствующие деревья, мы показали, чта для заданного значения Ж количества сравнений, необходимое для бинарного поиска, не превышает количества, которое требуется для любого другого метода, основанного на сравнении ключей. Однако методы нз предыдущего раздела годятся, в основном, для таблиц фиксираванпага размера, поскольку последовательное расположение записей делает вставку и удаление записей весьма трудоемкими. Если таблица динамически изменяется, та мы можем потратить на ее постоянное упорядочение куда больше времени, чем сэкономить ка бинарном поиске. Явное использование структуры бинарного дерева позволяет быстро вставлять и удалять записи, а также эффективна выполнять поиск в таблице.
В результате мы получаем метод, эффективный как для поиска, так и для сортировки. Цена такой гибкости — два поля ссылок в каждой записи таблицы. Технологии поиска в растущей таблице часта называют алгоритмами глаблиц символов, так как ассемблеры, компиляторы и другие системные программы обычно применяют их для хранения пользовательских символов. Например, ключом записи р Инволюниея называется такое отображение некоторого множества на о6я, квадрат которого является тожлестееннмн отображением. — Лрин.
нерее. Рис. 10. Бкнарноедерево поиска. в компиляторе может быть символьный идентификатор переменной в некоторой программе на языке РОВТВА)з или С, а остальная часть записи может содержать информацию о типе переменной и ее адресе; другим примером служит ключ, являющийся символом в МХХ-программе, а остаток записи содержит его эквивалент. Программы поиска со вставкой по дереву, которые будут описаны в этом разделе, достаточно эффективны в качестве алгоритмов таблиц символов, в особенности в приложениях, в которых может оказаться желательным вывод списка символов в алфавитном порядке. Другие алгоритмы таблиц символов описываются в разделах 6.3 и 6.4. На рис.
10 показано бинарное дерево поискаг содержащее названия одиннадцати знаков зодиакае. Если мы приступим к поиску двенадцатого имени, БАОХТТАВХОЗ, начиная от корня дерева, то увидим, что оно больше, чем САРВ1СОВМ, и нужно идти вправо; оно больнице, чем Р1БСЕБ, а потому мы опять идем вправо. Это имя меныпе, чем ТАОВОЗ, поэтому теперь мы сворачиваем влево, Так как искомое имя меньше, чем ЗСОВР10, мы попадаем во внешний узел (з(, Поиск оказался неудачным, и теперь мы можем всгкаеить ЗАОХТТАВХОБ в то место, где завершился наш поиск, на место внешнего узла [в). Таким образом, таблица может расширяться без перемещения существующих записей.
Дерево на рис. 10 получено путем последовательной вставки в пустое дерево ключей САРВ1СОВМ, АЦОАВ10Зг Р1ЗСЕЗ, АВХЕБ, ТАОВОЗ, ОЕИ1МХ, САМСЕВ, ЕЕО, ЧХВОО,АВВА. ЗСОВР10 в укаэанном порядке. Иа рис. 10 все ключи левого полдерева меньше (в алфавитном порядке), чем САРВХСОВМ, а цсс ключи правого поддерева -- больше.
То же самое справедливо н для левого и правого поддеревьев любого узла. Отсюда следует, что при обходе дерева в сгкмметричцом коряг)ке (см. раздел 2.3.1), поскольку симметричный порядок " список знаков зодиака, упоркдоченкый по кескцак„таков: козерог (сарисагп), Водолей (Лццамце), Рыбы (РГасез), Овен (Аг)ги), Телец (Тепгцз), Близнецы (Сенца)), Рак (Сапсег)> Лев (Есо), Дева (Ъзгйо), Весы (Здьга), Скорпион (Зсогрго), Стрелец (Зай(сгаг!пе). — Прим.
персе. основан на обходе сначала левого поддерева каждого узла, затем — самого узла, а после — правого поддерева,мы получим список ключей в алфавитном порядке: АЦОАК1ОЯ, АЕ1ЕЕ, САМСЕЕ, САРК1СОММ, ОЕМ1М1, |.ЕО, ..., ЧТО. Ниже приводится подробное описание процесса поиска со вставкой. Алгоритм Т (Поиск по дереву со вставкой (Тгее ееагсЬ апд (пвегг(оп)).
Дана таблица записей, образующая бинарное дерево. Этот алгоритм (рис, П) предназначен для поиска данного аргумента К. Если К в таблице отсутствует, новый узел, содержащий К, вставляется в дерево в иадлежащее место. Предполагается, что узлы дерева содержат, по крайней мере, следующие поля: КЕУ(Р) — ключ, хранящийся в узле МООЕ(Р); |.|,1МК(Р) -- указатель на левое поддерево узла МООЕ(Р); й|.1МК(Р) — указатель на правое поддерево узла МООЬ(Р). Пустые поддеревья (внешние узлы на рис.
|О) представляются пустыми указателями Л. Переменная ЕООТ указывает иа корень дерева. Для удобства полагаем, что дерево не пусто, т. е. ЕООТ ф Л, так как при ЕООТ = Л необходимые операции тривиальны. Т1. [Инициализация.) Установить Р +- ЕООТ. (Перемеииая-уквзатель Р будет перемещаться вниз по дереву.) Т2. [Сравнеиие.) Если К < КЕЧ(Р), перейти к шагу ТЗ; если К > КЕЧ(Р), перейти к шагу Т4; и если К =- КЕЧ(Р). поиск успешно завершается.
ТЗ. [Перемещение влево.) Если ШМК(Р) ф Л, установить Р +- ЕЕ1МК(Р) и перейти к шагу Т2; в противиом случае перейти к шагу Т5. Т4. [Перемещение вправо.[ Если Ы,|МК(Р) ф Л, установить Р +- Кь|МК(Р) и перейти к шагу Т2. Тб. [Вставка в дерево.[ (Поиск оказался неудачным; теперь мы должны поместить К в дерево.) Устаиовить Ц с:= АЧА15 (адрес нового узла). Присвоить КЕЧ(Ц) +- К, Ы,|МК(Ц) г- Е|.1МК(Ц) +- Л. (На практике следует инициализировать и другие поля нового узла.) Если К был меиьше, чем КЕЧ(Р), следует назначить ьь1МК(Р) е- Ц; в противном случае — иазначить Еь1МК(Р) <- Ц. (Теперь мы можем присвоить Р е- Ц и считать поиск успешно завершившимся.) Этот алгоритм сам подсказывает пам свою программную реализацию.
Предположим, например, что узлы дереиа имеют структуру за которой, возможно, следует дополнительная информация 1МРО. Используя, как и в главе 2, список свободной памяти АЧА11, мы можем написать следующую М1|- программу. Программа Т (Поиск по дереву со всшавкой). гА =- К, гП се Р, г12 гв Ц. И ЕЕ1МК ЕЦО 2гЗ Ое КЕ1МК ЕЦО 4:5 (,ЦН Р+- аоот. 00 Бткнт 04 05 00 4Н 07 00 1Н 09 2Н 10 11 12 10 14 БН 10 16 17 10 19 00 21 ЗЮ ВЯ 1Н 01 ООИЕ ЫИ К 1.01 Воат ЮНР 2Р (.аг О,1(ЕЫИК) 12Е БР еит1 о,г СИЛЛ 1,1 10 4В ж БуосеББ еог о,1((,ыик) 12ИЕ 1В Ьаг АБРАХЕ юге аченр).оы 1.01 а,г(выик) БТХ АЧАХЬ БтА 1,г БТЕ 0,2 Л.
1Р Бтг о,1(ныик) уНР в+2 БТ2 0,1(Ы.1ИК) ЕЦУ 1 1 1 С2 С2 С-1 С С С1 С1 -5 С1-Б 1 — Я 1-5 1-5 1 — Я 1 — Я 1 — Я 1 — Я А А 1 — Я вЂ” А 1-Б Т4. Пе еме елке вп аво. Ц +- ЕЕТИК(Р). Переход к шагу ТЬ при Ц = Л. Р ~- Ц. и. я~~ Переход к шэд у Т4 при К > КЕТ(Р), Выход, если К = КЕТ(Р), Т . Пе ме е е вл во. Ц ~- 111ИК(Р). Переход к шагу Т2 при Ц Р'. Л. Ц ~ АРАХИС.. кет(ц) ~- К. 11.1ИК(Ц) +- ЯЛИК(Ц) +- Л. Выпелнвлесь ли условие К < КЕТ (Р) 7 ЕХ.1ИК(Р) +- Ц.
111ИК(Р) +- Ц. Выход после вставки. $ Рис. 11. Поиск по дереву и вставка. Первые 13 строк программы выполняют поиск, следующие 11 — вставку. Время работы фазы поиска составляет (7С + С1 — 35 + 4)и, где С вЂ” количество выполненных сравнений; С1 — количество сравнений, когда К < КЕТ(Р)", С2 — количество сравнений, когда К > КЕТ(Р); 5 — 1 при успешном и О при неудачном поиске. В среднем имеем С1 = 1(С+ 5), поскольку С1+ С2 = С, а С1 — Я имеет то же распределение вероятностей, что и С2; таким образом, время работы программы— около (7.5С вЂ” 2.55+ 4)н. Как видим, это лучшее значение, чем при бинарном поиске с неявными деревьями (см.
программу 6.2.1С). Продублирован код, как это было сделано в программе 6.2.1Г, мы можем избавиться от строки 08 программы Т, уменьшая время работы до (6.5С вЂ” 2.5л'+ 5)и. При неудачном поиске фаза вставки займет дополнительное время — 14н или 15и. Алгоритм Т легко адаптировать для работы с ключами и записямн переменной длины. Например, если мы распределяем имеющуюся память последовательно, по принципу ЫГО ("последним вошел — первым вышел"), можно очень легко создавать узлы различных размеров — первое слово в (1) может указывать размер записи. Такое достаточно эффективное использование памяти делает алгоритмы таблиц символов, основанные на деревьях, особенно привлекательными для использования в компиляторах, ассемблерах и загрузчиках.
А как насчет наихудшего варианта? Программисты зачастую скептически относятся к алгоритму Т прн первом знакомстве с ням. Ведь если бь1 ключи из рис. 10 поступали в алфавитном порядке -- АОУАИ103, ..., 71300 — вместо календарного, алгоритм построил бы вырожденное дерево, соответствующее последовашельномд поиску. Все поля ЬЫИК в этом дереве были бы пустыми, Точно тяк же поступление ключей в несколько необычном порядке— АЦОА3103, 71300, АЕ133, ?АИШБ, САИСЕЕ, БСОЕР10, САРк1СОЕИ, .Р13СЕБ, ОЕИ131„ 113КА,1.ЕО— привело бы к построению зигзагообразного дерева, что ничуть не сокращает время поиска (постройте его сами — и убедитесь).
С другой стороны, для успешного пояска по дереву, изображенному на рис. 10, требуется в среднем всего 3 — „сравнений; это лишь ненамного превышает мини- 2 мально возможное количество 3, которое достигается при поиске по наилучшему из возможных бинарных деревьев. При работе с хорошо сбалансированным деревом время поиска примерно пропорционально )ой Ф; однако в случае вырожденного дерева время поиска становится пропорциональным Ф. В упр. 2.3.4.5-5 доказывается„что среднее время поиска пропорционально ~/Х в предположении равновероятности всех бинарных деревьев с Ф узлами, Чего же нам следует ожидать от алгоритма Т? К счастью, можно доказать, что поиск по дереву требует лишь около 21п Ж ж 1.386)ЕХ сравнений, если ключи вставляются в дерево в случайном порядке. На практике в основном встречак~тся хорошо сбалансированные деревья, в то время как вырожденные деревья появляются редко.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
