Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 65
Текст из файла (страница 65)
Разработайте рекурсивные версии процедур Ткее М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.
12.3-4. Предположим, что указатель на узел у бинарного дерева поиска хранится в некоторой внешней структуре данных и что предшествующий ему узел а удаляется из дерева с помощью процедуры Тквк РБ.втк Какая проблема при этом может возникнуть? Каким образом следует переписать процедуру Тквк Веьете, чтобы ее избежать? Является ли операция удаления "коммутативной*' в том смысле, что уда- ление х с последующим удалением у из бинарного дерева поиска приво- дит к тому же результирующему дереву, что и удаление у с последующим удалением х? Обоснуйте свой ответ.
12.3-5. 12.3-6. Если узел а в процедуре Тквк 1)кьктп имеет два дочерних узла, то можно воспользоваться не последующим за ним узлом, а предшествующим. Утверждается, что стратегия, которая состоит в равновероятном выборе узла). Затем в строках 4-6 х присваивается указатель на дочерний узел узла у либо значение яь, если у у нет дочерних узлов. Затем узел у убирается из дерева в строках 7 — 13 путем изменения указателей в р [у] и к. Это удаление усложняется необходимостью корректной отработки граничных условий (когда х равно мш или когда у — корневой узел). И наконец, в строках 14-16, если удаленный узел у был следующим за а, мы перезаписываем ключ л и сопутствующие данные ключом и сопутствующими данными у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
