Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 69

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 69)

Процедура поддерживает также замыкающийуказаюезь (!га!1!пй ро!и!ег) у, который представляет собой указатель на родительский ло отношению к х узел. После инициализации цикл зеЫ1е в строках 3-7 перемещает эти указатели вниз по дереву, перемещаясь влево или вправо в зависимости ст результата сравнения ключей з.неу и х.кеу, до тех пор, пока х не станет равным мп.. Это значение находится именно в той позиции, в которую следует поместить элемент г. Замыкающий указатель у нужен для того, чтобы знать, какой узел должен быть изменен.

В строках 8 — 13 выполняется установка значений указателей, обеспечивающая вставку элемента з. Часть тл. Структуры данныт Рис. 12.3. Вставка элемента с ключом 13 в бинарное лерево поиска. Светлые узлы указывают простой путь от корня внэп по дереву в позицию, в которую должен быть вставлен новый элемент. Пунктирная линия указывает добавляемую в дерево связь, обеспечивающую вставку элемента.

Так же, как и другие примитивные операции над бинарным деревам поиска, процедура ТКВВ-1НЗВКт выполнается за время О(Ь) в дереве высотой Ь. Удаление Стратегия удаления узла э из бинарного дерева поиска Т имеет три основные ситуации; как мы увидим, одна из ситуаций оказывается достаточно сложной. ° Если у к нет дочерних узлов, то мы просто удаляем его, внося изменения в его родительский узел, а именно — заменяя дочерний узел г на Н11..

Если у г только один дочерний узел, то мы удаляем узел г, создавая новую связь между родительским и дочерним узлами узла ж ° Если у узла г два дочерних узла, то мы находим следующий за ним узел у, который должен находиться в правом поддереве л и который занимает в дереве место л. Остаток исходного правого поддерева г становится новым поддеревом у, а левое поддерево г становится новым левым поддеревом р. Это самый сложный случай, поскольку, как мы увидим, здесь играет роль, является ли у правым дочерним узлом г.

Процедура удаления данного узла а из бинарного дерева поиска Т получает в качестве аргумента указатели на Т и на а. Она организована несколько иначе, чем описано ранее, и рассматривает не три, а четыре случая, показанные на рис. 12.4. Если л не имеет левого дочернего узла (см. рис. 12.4, (а)), то мы заменяем э его правым дочерним узлом, который может быть (или не быть) 1чц.. Если правый дочерний узел а представляет собой нно то мы оказываемся в ситуации, когда у узла а нет дочерних узлов. Если правый дочерний узел к отличен от мин то мы оказываемся в ситуации, когда у узла г имеется единственный дочерний узел, являющийся правым дочерним узлом.

° Если а имеет только один дочерний узел, являющийся его левым дочерним узлом (см. рис. 12.4, (б)), то мы заменяем а его левым дочерним узлом. ° В противном случае э имеет и левый, и правый дочерние узлы. Мы находим узел у, следующий за а. Этот узел располагается в правом поддереве э и не Глава 12 Бинарные деревья поиска (ь) ~*;;» г - ° вв ° Г,.„::~ г нп. (,".,) г ''у (ь) гмр )";.) у 1(!':) ь")) я ге г )-": з ~:,':- Рве.

12.4. Удаление узла х из бинарного дерева поиска. Узел х может быль корнем, левым дочерним узлом узла ь) или правым дочерним узлом о. (а) Узел г не имеет левого дочернего уэлл. Мы заменяем я его правым дочерним узлом г, который может быть (а мажет и не быть) значением нп.. (6) Узел х имеет левый дочерний узел 1, но не имеет правого дочернего узла.

Мы заменяем я на 1. (в) Узел х имеет два дочерних узла; его левый дочерний узел — 1, а правый дочерний узел и является следующим за х узлам дерева; правый лочерний по отношению к и узел — х. Мы заменяем х на и, обновляем левый дочерний узел р (им становится 1), но оставляем х правым дочерним узлом р. (г) Узел х имеет два дочерних узла (левый дочерний узел 1 и правый дочерний узел г), а следующий за х узел р эь г находится в поддереве, корнем которого кажется г. Мы заменяем р его собственным правым дочерним узлом х и устанавливаем и в качесгве рошпельского по отношению к г узла.

Затем мы устанавливаем р в качестве дочернего узла о и родительского узла 1. Часть Ш. Структуры даккык 330 имеет левого дочернего узла (см. упр. 12.2.5). Мы хотим вырезать у из его текущего положения и заменить им в дереве узел г. ° Если у является правым дочерним узлом г (см. рис. 12.4, (в)), то мы заменяем г на у, оставляя нетронутым правый дочерний по отношению к у узел. ° В противном случае у находится в правом поддереве узла г, но не является правым дочерним узлом г (см.

рис. 12.4,(г)). В этом случае мы сначала заменяем у его собственным правым дочерним узлом, а затем заменяем г на у. Для перемещения поддеревьев в бинарном дереве поиска мы определяем подпрограмму ТКАмяч.АР!т, которая заменяет одно поддерево, являющееся дочерним по отношению к своему родителю, другим поддеревом. Когда ТКА!Чзрьлнт заменяет поддерево с корнем в узле и поддеревом с корнем в узле и, родитель узла и становится родителем узла и, который становится соответствующим дочерним узлом родительского по отношению к и узла. Тклхзрьлхт(Т, и, и) ! П'и.р ыы НП. 2 Т.гоо! = и 3 е!ее!1 и == и.р.

!е1г 4 и.р,!е7с = и 5 е!яе и.р.яда! = и 6 1!и~ь!и. 7 и.р = и.р В строках 1 и 2 обрабатывается случай, когда и является корнем Т. В противном случае и является либо левым, либо правым дочерним узлом своего родителя. В строках 3 и 4 выполняется обновление и.р, 1е7с, если и является левым дочерним узлом, в строке 5 обновляется и.р.

пдЬ1, если и является правым дочерним узлом. Мы допускаем значение нп. для узла и, и строки 6 и 7 обновляют и.р, если и не нп.. Заметим, что ТКАизи.лмт не пытается обновлять и. !е7г и и. ~дбг; выполнение этих действий (или их не выполнение) находится в зоне ответственности вызывающей подпрограмму ТКАМЗРЬАнт процедуры. Имея подпрограмму Тклыз~.лмт, мы можем реализовать процедуру удаления узла г из бинарного дерева поиска Т следующим образом. зо! Глава !2.

Бинарные деревья поиска Ткее-!3еьете(Т, г) 1 1! г. 1е2г == мп. 2 Тклмзрьлмт(Т, г, г. пдЫ) 3 е1зе1! г. гьдМ == мп 4 ТКАМЗРЕАКТ(Т, г, г. 1е11) 5 е1зе у = ткее-м1м!мпм(г. г1ды) 6 1Турфг 7 Тклмзрелмт(Т, у, у. гздИ) 8 у.пдЫ = г.г1дМ 9 у.гедЫ.р = у 1О Тклмзрьлхт(Т, г, у) 1! у.1е11 = г.1е11 12 у.1е!Г.р = у Процедура Ткее-!3н.ете работает следующим образом. Строки 1 и 2 обрабатывают случай, когда у узла г нет левого дочернего узла, а строки 3 и 4 — когда у г есть левый дочерний узел, но нет правого. Строки 5-12 работают с оставшимися двумя случаями, когда у г есть два дочерних узла.

Строка 5 находит узел у, следующий за г. Поскольку г имеет непустое правое поддерево, следующий за г узел должен быть узлом этого поддерева с наименьшим ключом; поэтому поиск узла у осуществляется вызовом Ткее-Мипм!!м(г. пдЫ). Как отмечалось ранее, у у нет левого дочернего узла. Мы хотим вырезать у из его текущего положения, после чего этот узел должен заменить в дереве узел г. Если у является правым дочерним узлом г, то строки 10-12 заменяют г как дочерний узел его родителя на у к заменяют левый дочерний узел у левым дочерним узлом г.

Если у не является правым дочерним узлом г, в строках 7-9 выполняется замена у как дочернего узла своего родителя правым дочерним по отношению к у узлом, и преобразование правого дочернего узла г в правый дочерний узел у, после чего строки 10-12 заменяют г как дочерний узел его родителя узлом у, а левым дочерним узлом у становится левый дочерний узел г. Каждая строка Ткее-Пи.ете, включая вызовы Тклмзи.лмт, выполняется за константное время, за исключением вызова Ткее-Мич!мг!м в строке 5. Таким образом, Ткее-!3еьете выполняется за время 0(Ь) в дереве высотой Ь. Таким образом, доказана следующая теорема.

Теорема 12.3 Операции над динамическим множеством !Мзект и Пекете можно реализовать таким образом, что каждая из них выполняется в бинарном дереве поиска высотой Ь за время 0(Ь). Упражнения 12.3.1 Приведите рекурсивную версию процедуры Ткее-!мзект. ззг Часть йт Структуры даннык 12.3.2 Предположим, что бинарное дерево поиска строится путем многократной вставки в дерево различных значений. Покажите, что количество узлов, проверяемых при поиске некоторого значения в дереве, на один больше, чем количество узлов, проверявшихся при вставке этого значения в дерево. 1г.з.з Отсортировать заданное множество из и чисел можно следукицим образом: сначала построить бинарное дерево поиска, содержащее эти числа (многократно вызывая процедуру Ткнн-1ызпкт для вставки чисел в дерево одно за другим), а затем выполнить центрированный обход полученного дерева.

Чему равно время работы такого алгоритма в наилучшем и наихудшем случаях? 12.3.4 Является ли операция удаления "коммутативной" в том смысле, что удаление х с последующим удалением у из бинарного дерева поиска приводит к тому же результирующему дереву, что и удаление у с последующим удалением х? Поясните, почему это так, или приведите контрпример.

12.3.5 Предположим, что вместо поддержки в каждом узле х атрибута х.р, указывающего на родительский узел х, поддерживается атрибут х. кисе, указывающий на узел, следующий за х. Запишите псевдокод процедур Бвлксн, 1мзнкт и Песете для бинарного дерева поиска, использующего такое представление. Эти процедуры должны выполняться за время 0(6), где Ь вЂ” высота дерева Т. (Указание: можно реализовать подпрограмму для поиска узла, родительского по отношению к данному.) 12.3. б Если узел з в процедуре Ткнн-Пньнтн имеет два дочерних узла, можно выбрать не следующий за ним узел у, а предшествующий ему.

Какие при этом следует внести изменения в процедуру Ткнн-Реьете? Есть также мнение, что стратегия, которая состоит в равновероятном выборе предшествующего или последующего узла, приводит к большей производительности. Каким образом следует изменить процедуру Ткнн-Рнсктн для реализации указанной стратегии? * 12.4. Случайное построение бинарных деревьев поиска Мы показали, что все базовые операции с бинарными деревьями поиска имеют время выполнения 0(Ь), где 6 — высота дерева. Однако при вставке и удалении элементов высота дерева меняется. Если, например, все элементы вставляются в дерево в строго возрастающей последовательности, то такое дерево вырождается в цепочку высотой и — 1. С другой стороны, как показано в упр. Б.5.4. (ь > ~!й пЗ. Как и в случае быстрой сортировки, можно показать, что поведение Глава ББ Бинарные деревья яоисяа алгоритма в среднем случае гораздо ближе к наилучшему случаю, чем к наихудшему. К сожалению, в ситуации, когда при формировании бинарного дерева поиска используются и вставки, и удаления, о средней высоте образующихся деревьев взвестно мало, так что мы ограничимся анализом ситуации, когда дерево строится только с использованием вставок, без удалений.

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

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