Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 67
Текст из файла (страница 67)
На практике мы не всегда можем гарантировать случайность построения бинарного дерева поиска, однако имеются версии деревьев, в которых гарантируется хорошее время работы в наихудшем случае. В главе 13 будет представлена одна из таких версий, а именно — красно-черные деревья, высота которых составляет 0(18п). В главе 18 вы познакомитесь с В-деревьями, которые особенно хорошо подходят для баз данных, храшпцихся во вторичной памяти с произвольным доступом (на дисках). После знакомства с основными свойствами деревьев поиска в последующих разделах главы будет показано, как осуществляется обход дерева поиска для вывода его элементов в отсортированном порядке, как выполняется поиск минимального и максимального элементов, а также предшествующего данному элементу и следующего за ним, как вставлять элементы в дерево поиска и удалять их оттуда.
Основные математические свойства деревьев описаны в приложении Б. 12.1. Что такое бинарное дерево поиска Как следует из названия, бинарное дерево поиска, в первую очередь, является бинарным деревом, как показано на рис. 12.1. Такое дерево может быть представлено с помощью связанной структуры данных, в которой каждый узел является Часть гдзь. Смруяевры долныз 320 (6) (а) Рис.
12.1. Бинарные деревья поиска. Длл любого узла х ключи в левом поддереве х не превышают х.кер, а ключи в правом поддереве х — не меньше х. (ит(. Одно и то же множество значений могут представлять различные бинарные деревья поиска. Время работы в наихудшем случае для большинства операций в дереве поиска пропорционально его высоте. (а) Бинарное дерево поиска с б узлами высотой 2. (б) Менее эффективное бинарное дерево поиска с высотой 4, содержащее те же узлы. объектом. В дополнение к атрибуту ключа lсеу и сопутствующим данным каждый узел содержит атрибуты 1еу(, пдйг и р, которые указывают на левый и правый дочерние узлы и на родительский узап соответственно.
Если дочерний или родительский узел отсутствуют, соответствующее поле содержит значение нп.. Единственный узел, указатель р которого равен ып., — зто корневой узел дерева. Ключи в бинарном дереве поиска хранятся таким образом, чтобы в любой момент удовлетворять следующему саойстау бинарного дерева поиска. Пусть х представляет собой узел бинарного дерева поиска. Если у является узлом в левом поддереве х, то у.
Йеу < х.)сеу. Если у является узлом в правом поддереве х, то у. )сеу > х. )сеу. Таким образом, на рис. 12.1, (а) ключом корня является значение 6, ключи 2, 5 и 5 в его левом поддереве не превосходят значение 6, а ключи 7 и 8 в его правом поддереве не меньше 6. То же свойспю выполняется для каждого узла дерева. Например, ключ 5 в левом дочернем по отношению к корню узле не меньше ключа 2 в его левом поддереве и не больше ключа 5 в его правом поддереве. Свойство бинарного дерева поиска позволяет вывести все ключи, находящиеся в дереве, в отсортированном порядке с помощью простого рекурсивного алгоритма, называемого центрироааннвзм (симметричньгм) обходом дерева ((пот()ег нее па))(). Этот алгоритм получил данное название в связи с тем, что ключ в корне полдерева выводится между значениями ключей левого поддерева и правого поддерева. Имеются и другие способы обхода, а именно — ойтод и прямом порядке (ргеоп1ег (гее тгайс), при котором сначала выводится корень, а затем — значения левого и правого поддеревьев, и обход в обратном порядке (роя1огбег ггее тсайс).
когда первыми выводятся значения левого и правого поддеревьев, а уже затем— корня. Центрированный обход бинарного дерева поиска Т реализуется вызовом процедуры 1ЫОй ОБК-ТКББ- тем К(Т. гоо(). Гаева БК Бинарные деревья наивна !ХОКОЕК-ТКЕЕ-%САЬК(х) 1 !1 х ф ньь 2 !МОкпек-Ткее-%Аьк(х, 1еТс) 3 рпп! х, /сер 4 1иокпек-Ткее-%Аьк(х.
ядМ) В качестве примера центрированный обход деревьев, показанных на рис. 12.1, выводит ключи в порядке 2, 5, 5, 6, 7, 8. Корректность описанного алгоритма следует по индукции непосредственно из свойства бинарного дерева поиска. Для обхода дерева с п узлами требуется время 9(п), поскольку после начального вызова процедура вызывается ровно два раза для кахсдого узла дерева: один раз — для его левого дочернего узла и один раз — для правого.
Приведенная далее теорема дает нам более формальное доказательство линейности времени центрированного обхода дерева. Теорема Л.1 Если х — корень поддерева с п узлами, то время работы вызова 1иокпек-Ткее%Аьк(х) составляет с!(п). Доказаавельсавво. Обозначим через Т(п) время, необходимое процедуре 1иокпек-Ткее-%Аьк в случае вызова с параметром, представляюшим собой корень дерева с п узлами. Поскольку процедура 1иокпек-Ткее-%Аьк посещает все п узлов поддерева, мы имеем Т(п) = П(п).
Остается показать, что Т(п) = 0(п). Поскольку 1нокпек-Ткее-%Аьк требует маленького, фиксированного количества времени для работы с пустым деревом (для выполнения проверки х ф и!ь), мы имеем Т(О) = с для некоторой константы с > О. В случае п > О будем считать, что процедура 1!чокпек-Ткее-%Аьк вызывается в узле х один раз для левого поддерева с к узлами, а второй — для правого поддерева с п — )с — 1 узлами. Таким образом, время работы процедуры !хокэек-ткее-зкАьк(х) ограничено т(п) < т(к) + т(п — к — 1) + с( для некоторой константы с( > О, которая отражает время, необходимое для выполнения тела процедуры без учета рекурсивных вызовов.
Воспользуемся методом подстановки, чтобы показать, что Т(п) = 0(п), путем доказательства того, что Т(п) < (с+ег)и+с. Для п = О мы имеем (с+с() О+с = с = Т(0). Для п > О мы имеем Т(п) < Т(к) + Т(п — )с — 1) + с( = ((с + с))М + с) + ((с + с() (п — lс — 1) + с) + Н = (с + Н)п + с — (с + Н) + с + с! = (с + сс)п + с, что и завершает доказательство. и зьк згзе Часть Ш. Структуры данныс 377 Упражнения 12.1.1 Начертите бинарные деревья поиска высотой 2, 3, 4, 5 и 6 для множества ключей 11, 4, 5, 10, 16, 17, 21) . 12.1.2 В чем заключается отличие свойства бинарного дерева поиска от свойства неубывающей пирамиды (с.
181)? Можно ли использовать свойство неубывающей пирамиды для вывода ключей дерева с и узлами в отсортированном порядке за время 0(п)? Поясните свой ответ. 12.1.3 Разработайте нерекурсивный алгоритм, осуществляющий обход дерева в симметричном порядке. (Указанвес имеется простое решение, которое использует вспомогательный стек, и более сложное, но более элегантное решение, которое обходится без стека, но предполагает возможность проверки равенства двух указателей.) 12.1.4 Разработайте рекурсивный алгоритм, который осуществляет прямой и обратный обходы дерева с и узлами за время 9(п). 12.1.5 Покажите, что, поскольку сортировка и элементов требует в модели сортировки сравнением в худшем случае времени П(п18 и), любой основанный на сравнениях алгоритм построения бинарного дерева поиска из произвольного списка, содержащего и элементов, также требует в худшем случае времени П(п 18 п).
12.2. Работа с бинарным деревом поиска Наиболее частой операцией, выполняемой с бинарным деревом поиска, является поиск в нем определенного ключа. Помимо операции Бпянсц, бинарные деревья поиска поддерживают такие запросы, как Мппмим, Млх1мим, Бисснззок и Ркнэнснззок. В данном разделе мы рассмотрим все эти операции и покажем, что все они могут быть выполнены в бинарном дереве поиска высотой Ь за время 0(Ь).
Поиск Для поиска узла с заданным ключом в бинарном дереве поиска используется приведенная ниже процедура Ткнн-ЯнАксн, которая получает в качестве параметров указатель на корень бинарного дерева и ключ к, а возвращает указатель на узел с этим ключом (если таковой существует; в противном случае возвращается значение мп.). Згз Глава »г.
Бинарные деревья яошка Рис. 12.2. Запросы к бинарному дереву поиска. Ддя поиска ключа 13 необходимо пройти путь 16 -+ 6 -+ 7 -+ 13 от корня. Минимальным в дереве лввяегса ключ 2, который находится при следовании по указателям »ег» от корня. Максимальный ключ 20 достигается при следовании от сория по указателям г»ра».
Последуюшим узлом после узла с ключом Ш является узел с ключом 17, посмюьку это минимальный юпоч в правом поддереве узла 16. Уюл с юпочом 13 не имеет правого по»Шарова, так что следуалпим за ним является наименьший предок, левый наследник юторого также явлаегся преююм данного узла. В нашем случае зто узел с юлочом 16. Ткее-беАксн(х, »с) 1 1» х == ХП. или Й == х. »сеу 2 ге$нги х 3 И /с ( х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
