Алгоритмы - построение и анализ (1021735), страница 63
Текст из файла (страница 63)
Предшествующий и последующий элементы Иногда, имея узел в бинарном дереве поиска, требуется определить, какой узел следует за ним в отсортированной последовательности, определяемой порядком Часть 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. Разработайте рекурсивные версии процедур Ткее М1ьлмом и Ткее МАх1мим. 12.2-3. Разработайте процедуру Ткее Ркепесеззок. 12.2-4. Разбираясь с бинарными деревьями поиска, студент решил, что обнаружил их новое замечательное свойство. Предположим, что поиск ключа )с в бинарном дереве поиска завершается в листе. Рассмотрим три множества: множество ключей слева от пути поиска А, множество ключей на пути поиска В и множество ключей справа от пути поиска С. Студент считает, что любые три ключа а е А, 6 е В и с е С должны удовлетворять неравенству а < б < с. Приведите наименьший возможный контрпример, опровергающий предположение студента. Покажите, что если узел в бинарном дереве поиска имеет два дочерних узла, то последующий за ним узел не имеет левого дочернего узла, а предшествующий ему — правого. Рассмотрим бинарное дерево поиска Т, все ключи которого различны.
Покажите, что если правое поддерево узла х в бинарном дереве поиска Т пустое и у х есть следующий за ним элемент у, то у является самым нижним предком х, чей левый дочерний узел также является предком х. (Вспомните, что каждый узел является своим собственным предком.) Центрированный обход бинарного дерева поиска с п узлами можно осуществить путем поиска минимального элемента дерева при помощи процедуры Ткее М1ьлмим с последующим и — 1 вызовом процедуры Ткее Биссеззок. Докажите„что время работы такого алгоритма равно О (и).
Докажите, что какой бы узел ни был взят в качестве исходного в бинарном дереве поиска высотой Ь, на Й последовательных вызовов процедуры ТКЕЕ 8ОССЕЗЗОК потребуется время О (1с + Л). 12.2-5. 12.2-6. 12.2-7. 12.2-8. Упражнения 12.2-1. Пусть у нас имеется ряд чисел от 1 до 1000, организованных в виде 324 Часть !П. Структуры данных 12.2-9. Пусть Т вЂ” бинарное дерево поиска с различными ключами, х — лист этого дерева, а у — его родительский узел.
Покажите, что йеу [у] либо является наименьшим ключом в дереве Т, превышающим ключ йеу [х], либо наибольшим ключом в Т, меньшим ключа йеу [х]. 12.3 Вставка и удаление Операции вставки и удаления приводят к внесению изменений в динамическое множество, представленное бинарным деревом поиска. Структура данных должна быть изменена таким образом, чтобы отражать эти изменения, но при этом сохранить свойство бинарных деревьев поиска.
Как мы увидим в этом разделе, вставка нового элемента в бинарное дерево поиска выполняется относительно просто, однако с удалением придется повозиться. Вставка ТКЕЕ 1!48ЕКТ(Т, х) 1 у <- !чп. 2 х — гоо![Т] 3 исае х 7~ ЫП. 4 йоу — х 5 11' Йеу[г] ( Йеу[х] 6 !пеп х — 1егг[х] 7 е!яе х — тздЫ[х] 8 р[з] — у 9 1!у=!4н. 1О Изеп тоог[Т] +- г 1! еве Ы Йеу[з] < Йеу[у] 12 !Ьеп 1е7т[у] !3 е!зе пд6![у] — я г> Дерево Т вЂ” пустое На рис. 12.3 показана работа процедуры ткее 1!чзект. Подобно процедурам Ткее ЯеАксн н 1текАТ!Уе Ткее ЗеАксн, процедура ткее 1!чзект начинает работу с корневого узла дерева и проходит по нисходящему пути. Указатель х отмечает проходимый путь, а указатель у указывает на родительский по отношению к х Для вставки нового значения о в бинарное дерево поиска Т мы воспользуемся процедурой Ткее 1!48ект.
Процедура получает в качестве параметра узел з, у которого йеу [з] = с, 1егг [х] = !ч!е и яда! [з] = мп„после чего она таким образом изменяет Т и некоторые поля з, что х оказывается вставленным в соответствующую позицию в дереве. Глава 12. Бинарные деревья поиска 325 Ц~) «2)7 6" «'~ 'Ю фт) Рпс. 12.3. Вставка элемента с ключом 13 в бинарное дерево поиска. Светлые узлы указывают путь от корня к позиции вставки; пунктиром указана связь, добавляемая при вставке нового элемента узел. После инициализации цикл иЬИе в строках 3-7 перемещает этн указатели вниз по дереву, перемещаясь влево или вправо в зависимости от результата сравнения ключей Йеу [х] и Йеу [г], до тех пор пока х не станет равным нй.. Это значение находится именно в той позиции, куда следует поместить элемент я.
В строках 8-13 выполняется установка значений указателей для вставки ж Так же, как и другие примитивные операции над бинарным деревом поиска, процедура Ткее 1нзект выполняется за время О (6) в дереве высотой Ь. Удаление Процедура удаления данного узла з из бинарного дерева поиска получает в качестве аргумента указатель на ж Процедура рассматривает три возможные ситуации, показанные на рис. 12.4. Если у узла з нет дочерних узлов (рис. 12.4п), то мы просто изменяем его родительский узел р [с], заменяя в нем указатель на з значением мп . Если у узла г только один дочерний узел (рис.
12.46), то мы удаляем узел з, создавая новую связь между родительским и дочерним узлом узла з. И наконец, если у узла г два дочерних узла (рис. 12.4в), то мы находим следующий за ним узел у, у которого нет левого дочернего узла (см. упражнение 12.2-5), убираем его из позиции, где он находился ранее, путем создания новой связи между его родителем и потомком, и заменяем им узел ж Код процедуры Ткее Пн.ете реализует эти действия немного не так, как они описаны. ТКЕЕ 1)ЕьЕТЕ(Т, з) 1 и 1е72[з] = хп. или гздл1[з] = ьль 2 Фадее у — з 3 е1ае у — Ткее 8иссеззок(г) 4 '1Р 1е71[у] ф ьл~.
326 Часть 111. Структуры данных ф Щ ~', ф Рис. 12.4. Удаление узла г из бинарного дерева поиска 5 Спел х - 1еф[у] 6 е1яе х — пдЛ1 [у] 7 11 х Ф ы11. 8 Спел р[х) + — р[у] 9 !1'р[у] = ни. 10 1Ьеп гоо1 ~Т] — х 11 е!зе 1Г у = 1етг[р[у)] 12 Слеп 1еГг[р[у)) — х 13 е!зе гъдЛ1[р[у]] — х !4 11' у ф г 15 тпеп Леу[а] — Лсу[у] 16 Копирование сопутствующих данных в г 17 ге1пгп у В строках 1-3 алгоритм определяет убираемый путем "склейки" родителя и потомка узел у. Этот узел представляет собой либо узел я (если у узла з не более одного дочернего узла), либо узел, следующий за узлом х (если у х два дочерних Глава 12. Бинарные деревья поиска 327 Теорема 12.3.
Операции вставки и удаления в бинарном дереве поиска высоты Ь могут быть выполнены за время О (Ь). Упражнения 12.3-1. 12.3-2. Приведите рекурсивную версию процедуры Тккк 1мзект. Предположим, что бинарное дерево поиска строится путем многократ- ной вставки в дерево различных значений. Покажите, что количество узлов, проверяемых при поиске некоторого значения в дереве, на один больше, чем количество узлов, проверявшихся при вставке этого значе- ния в дерево. Отсортировать множество из п чисел можно следующим образом: сначала построить бинарное дерево поиска, содержащее эти числа (вызывая процедуру Тккл 1мзккт для вставки чисел в дерево одно за другим), а затем выполнить центрированный обход получившегося дерева. Чему равно время работы такого алгоритма в наилучшем и наихудшем случае? 12.3-3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
