Главная » Просмотр файлов » Алгоритмы - построение и анализ

Алгоритмы - построение и анализ (1021735), страница 63

Файл №1021735 Алгоритмы - построение и анализ (Алгоритмы - построение и анализ) 63 страницаАлгоритмы - построение и анализ (1021735) страница 632017-07-10СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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.

Характеристики

Тип файла
DJVU-файл
Размер
18,3 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6521
Авторов
на СтудИзбе
302
Средний доход
с одного платного файла
Обучение Подробнее