Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 64
Текст из файла (страница 64)
Структуры данных 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(Ь), где Ь вЂ” высота дерева, поскольку, как и в процедуре Ткее БеАксн, последовательность проверяемых узлов образует нисходяший путь от корня дерева.
Предшествующий и последующий элементы Иногда, имея узел в бинарном дереве поиска, требуется определить, какой узел следует за ним в отсортированной последовательности, определяемой порядком Часть 111. Структуры данных 322 центрированного обхода бинарного дерева, и какой узел предшествует данному.
Если все ключи различны, последующим по отношению к узлу х является узел с наименьшим ключом, большим ассу [х]. Структура бинарного дерева поиска позволяет нам найти этот узел даже не выполняя сравнение ключей. Приведенная далее процедура возвращает узел, следующий за узлом х в бинарном дереве поиска (если таковой существует) и м1ь, если х обладает наибольшим ключом в бинарном дереве.
ТКЕЕ ВОССЕББОК(х) 1 11' гтдМ[х] ф мп. 2 1иев гегцгп Ткее М1ямпм(тздлг[х]) 3 у — р[х] 4 зтЫ1е у ф хп. и х = ттдлт[у] 5 пох — у б у ~ — р[у] 7 геФнгп у Код процедуры Ткее ЗиссеББОК разбивается на две части. Если правое поддерево узла х непустое, то следующий за х элемент является крайним левым узлом в правом поддереве, который обнаруживается в строке 2 вызовом процедуры ткее мп имам(пдл1 [х]). например, на рис. 12.2 следующим за узлом с ключом 15 является узел с ключом 17.
С другой стороны, как требуется показать в упражнении 12.2-6, если правое поддерево узла х пустое, и у х имеется следующий за ним элемент у, то у является наименьшим предком х, чей левый наследник также является предком х. На рис. 12.2 следующим за узлом с ключом 13 является узел с ключом 15. Для того чтобы найти у, мы просто поднимаемся вверх по дереву до тех пор, пока не встретим узел, который является левым дочерним узлом своего родителя.
Это действие выполняется в строках 3-7 алгоритма. Время работы алгоритма Ткее Яиссеззок в дереве высотой 6 составляет 0(6), поскольку мы либо движемся по пути вниз от исходного узла, либо по пути вверх. Процедура поиска последующего узла в дереве Ткее РкепесеББОк симметрична процедуре Ткее ЕиссеББОК и также имеет время работы 0 (6).
Если в дереве имеются узлы с одинаковыми ключами, мы можем просто определить последующий и предшествующий узлы как те, что возвращаются процедурами Ткее ВпссеББОК и Ткее РкепесеББОК соответственно. Таким образом, в этом разделе мы доказали следующую теорему. Теорема 12.2. Операции поиска, определения минимального и максимального элемента, а также предшествующего и последующего, в бинарном дереве поиска высоты 6 могут быть выполнены за время 0 (Ь). Глава 12. Бинарные деревья поиска 323 бинарного дерева поиска, и мы выполняем поиск числа 363. Какая из следующих последовательностей не может быть последовательностью проверяемых узлов? а) 2, 252, 401, 398, 330, 344, 397, 363, б) 924, 220, 911, 244, 898, 258, 362, 363. в) 925, 202, 911, 240, 912, 245, 363. г) 2, 399, 387, 219, 266, 382, 381, 278, 363, д) 935, 278, 347, 621, 299, 392, 358, 363. 12.2-2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
