Алгоритмы - построение и анализ (1021735), страница 62
Текст из файла (страница 62)
Бинарные деревья поиска 317 12.1 Что такое бинарное дерево поиска Как следует из названия, бинарное дерево поиска в первую очередь является бинарным деревом, как показано на рис. 12.! . Такое дерево может быть представлено при помощи связанной структуры данных, в которой каждый узел является обьектом. В дополнение к полям ключа кеу и сопутствующих данных, каждый узел содержит поля 1е~Г, гздМ и р, которые указывают на левый и правый дочерние узлы и на родительский узел соответственно. Если дочерний или родительский узел отсутствуют, соответствующее поле содержит значение )чй..
Единственный узел, указатель р которого равен )чи., — это корневой узел дерева. Ключи в бинарном дереве поиска хранятся таким образом, чтобы в любой момент удовлетворять следующему свойству бинарного дерева ноисна. Если х — узел бинарного дерева поиска, а узел у находится в левом поддереве х, то йеу [у] < кеу [х]. Если узел у находится в правом поддереве х, то Йеу[х] < Йеу[у].
Так, на рис. 12.1а ключ корня равен 5, ключи 2, 3 и 5, которые не превышают значение ключа в корне, находятся в его левом поддереве, а ключи 7 и 8, которые не меньше, чем ключ 5, — в его правом поддереве. То же свойство, как легко убедиться, выполняется для каждого другого узла дерева. На рис. 12.1б показано дерево с теми же узлами и обладающее тем же свойством, однако менее эффективное в работе, поскольку его высота равна 4, в отличие от дерева на рис. 12.!а, высота которого равна 2.
Свойство бинарного дерева поиска позволяет нам вывести все ключи, находящиеся в дереве, в отсортированном порядке с помощью простого рекурсивного алгоритма, называемого центрированнмм (симметричным) обходим дерева (шоп1ег 1гее ча)к). Этот алгоритм получил данное название в связи с тем, что ключ в корне поддерева выводится между значениями ключей левого поддерева а) Рис.
12.1. Бинарные деревья поиска Часть П1. Структуры данных 318 и правого поддерева. Имеются и другие способы обхода, а именно — обход е прямом яорядке (ргеоп1ег ггее ва1к), при котором сначала выводится корень, а потом — значения левого и правого поддерева, и обход е обратном порядке (розГоп1ег 1гее и а1К), когда первыми выводятся значения левого и правого поддерева, а уже затем — корня. Центрированный обход дерева Т реализуется процедурой 1ХОКОЕК ТКЕЕ ууЛ~.К(гоо1 [Т]): 1МОкпек Ткее уулек(х) 1 !1х ~ ып. 2 Феп 1мокПЕК ТКЕЕ %М.К(1е1г[х]) 3 рпп1 Еед[х] 4 1нокпек Ткее %л1к(пдМ[х]) В качестве примера рассмотрите центрированный обход деревьев, показанных на рис.
12.1, — вы получите в обоих случаях один и тот же порядок ключей, а именно 2, 3, 5, 5, 7, 8. Корректность описанного алгоритма следует непосредственно из свойства бинарного дерева поиска. Для обхода дерева требуется время 9 (и), поскольку после начального вызова процедура вызывается ровно два раза для каждого узла дерева: один раз для его левого дочернего узла, и один раз — для правого. Приведенная далее теорема дает нам более формальное доказательство линейности времени центрированного обхода дерева. Теорема 12.1.
Если х — корень поддерева, в котором имеется и узлов, то проце- дура 1нокпек Ткее %лек(х) выполняется за время 9 (и). Доказатеяьстео. Обозначим через Т (и) время, необходимое процедуре 1нокпек Ткее %лыс в случае вызова с параметром, представляющим собой корень дерева с и узлами. При получении в качестве параметра пустого поддерева, процедуре требуется небольшое постоянное время для выполнения проверки х ф нп., так что Т (0) = с, где с — некоторая положительная константа.
В случае и > 0 будем считать, что процедура 1нокпек Ткее %м.к вызывается один раз для поддерева с Й узлами, а второй — для поддерева с и — Й вЂ” 1 узлами. Таким образом, время работы процедуры составляет Т(и) = Т(1с) + + Т (и — lс — 1) + П, где П вЂ” некоторая положительная константа, в которой отражается время, необходимое для выполнения процедуры без учета рекурсивных вызовов. Воспользуемся методом подстановки, чтобы показать, что Т (и) = 9 (и), путем доказательства того, что Т(и) = (с+ 0) и + с. При и = 0 получаем Глава 12.
Бинарные деревья поиска 319 Т (0) = (с+ Н) 0+ с = с. Если п ) О, то т(п) = т(й)+т(п- й- 1)+~(= = ((с + Н) /с + с) + ((с + с() (и — й — 1) + с) + И = = (с + с() п + с — (с + Н) + с + с( = (с + Н) п + с, что и завершает доказательство. Упражнения 12.1-1. Начертите бинарные деревья поиска высотой 2, 3, 4, 5 и б для множества ключей (1, 4, 5, 10, 16, 17, 2 Ц.
12.1-2. В чем заключается отличие свойства бинарного дерева поиска от свойства неубывающей пирамиды (раздел 6.1)? Можно ли использовать свойство неубывающей пирамиды для вывода ключей дерева с и узлами в отсортированном порядке за время О (и)? Поясните свой ответ. 12.1-3. Разработайте нерекурсивный алгоритм, осуществляющий обход дерева в симметричном порядке. (Указание: имеется простое решение, которое использует вспомогательный стек, и более сложное (и более элегантное) решение, которое обходится без стека, но предполагает возможность проверки равенства двух указателей).
12.1-4. Разработайте рекурсивный алгоритм, который осуществляет прямой и обратный обход дерева с и узлами за время с (и). 12.1-5. Покажите, что, поскольку сортировка и элементов требует в модели сортировки сравнением в худшем случае 1) (п!я и) времени, любой алгоритм построения бинарного дерева поиска нз произвольного списка, содержащего и элементов, также требует в худшем случае й (и 1я п) времени. 12.2 Работа с бинарным деревом поиска Наиболее распространенной операцией, выполняемой с бинарным деревом поиска, является поиск в нем определенного ключа. Кроме того, бинарные деревья поиска поддерживают такие запросы, как поиск минимального и максимального элемента, а также предшествующего и последующего. В данном разделе мы рассмотрим все эти операции и покажем, что все они могут быть выполнены в бинарном дереве поиска высотой Ь за время О (Ь).
Часть П1. Структуры данных 320 Поиск Для поиска узла с заданным ключом в бинарном дереве поиска используется следующая процедура Ткее ЯеАксн, которая получает в качестве параметров указатель на корень бинарного дерева и ключ й, а возвращает указатель на узел с этим ключом (если таковой существует; в противном случае возвращается значение ьлс). ТКЕЕ ЯЕАКСН(х, /с) 1 Их = Мщили Й = йеу[х] 2 сЬеп гетпгп х 3 И Iс < 1сеу[х] 4 тпеп гетпгп ткее БеАксн(1е7с[х], Й) 5 е)яе геспгп Ткее БеАксн(пдйс[х], 1с) Процедура поиска начинается с корня дерева и проходит вниз по дереву.
Для каждого узла х на пути вниз его ключ Йеу [х] сравнивается с переданным в качестве параметра ключом 1с. Если ключи одинаковы, поиск завершается. Если й меньше Йеу [х], поиск продолжается в левом поддереве х; если больше — то поиск переходит в правое поддерево. Так, на рис. 12.2 для поиска ключа 13 мы должны пройти следующий путь от корня: 15 — 6 — 7 — 13.
Узлы, которые мы посещаем при рекурсивном поиске, образуют нисходящий путь от корня дерева, так что время работы процедуры Ткее ЗеАксн равно О (Ь), где Ь вЂ” высота дерева. Ту же процедуру можно записать итеративно, "разворачивая" оконечную рекурсию в цикл еЫ)е. На большинстве компьютеров такая версия оказывается более эффективной. Рнс.
12.2. Запросы в бинарном дереве поиска (пояснения в тексте) Глава 12. бинарные деревья поиска 321 1текАт!че Ткее ЗеАксн(х, Й) 1 иЬНе х ф !чп. и Й ф Йеу[х) 2 йо И Й ( Йед[х] 3 Феп х — 1е!с[х] 4 е!ае х — г1дй1[х] 5 ге1пгп х Поиск минимума и максимума Элемент с минимальным значением ключа легко найти, следуя по указателям 1е3т от корневого узла до тех пор, пока не встретится значение !ча.. Так, на рис. 12.2, следуя по указателям 1е22, мы пройдем путь 16 — 6 — 3 — 2 до минимального ключа в дереве, равного 2.
Вот как выглядит реализация описанного алгоритма: Ткее Мпч!м!3м(х) 1 зтййе 1е2с[х] ф яь 2 йо х — 1ефх] 3 ге1пгп х Свойство бинарного дерева поиска гарантирует корректность процедуры Ткее Мпч!м!Зм. Если у узла х нет левого поддерева, то поскольку все ключи в правом поддереве х не меньше ключа Йеу [х], минимальный ключ поддерева с корнем в узле х находится в этом узле.
Если же у узла есть левое поддерево, то, поскольку в правом поддереве не может быть узла с ключом, меньшим Йеу [х), а все ключи в узлах левого поддерева не превышают Йеу [х], узел с минимальным значением ключа находится в поддереве, корнем которого является узел 1е2с [х). Алгоритм поиска максимального элемента дерева симметричен алгоритму поиска минимального элемента: ТКЕЕ МАХ!М!!М(х) 1 иййе гздй1[х) ф !ч!е 2 до х — гздй1[х] 3 ге1пгп х Обе представленные процедуры находят минимальный (максимальный) элемент дерева за время 0(Ь), где Ь вЂ” высота дерева, поскольку, как и в процедуре Ткее БеАксн, последовательность проверяемых узлов образует нисходяший путь от корня дерева.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
