Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 130
Текст из файла (страница 130)
Оставшаяся часть процедуры, включая вызовы чЕВ-Тккк-М1кпмпм и чЕВ-Тккк-Млх1мпм„выполняется за время 0(1). Следовательно, в наихудшем случае время работы процедуры чЕВ-Тккк-Япсскввок составляет О(!8 18 и). Процедура чЕВ-Тккк-Рккокссввок симметрична процедуре чЕВ-ТкккЯпссвввок, но с одним дополнительным ветвлением. ЧЕВ-Ткее-РкеоесеввОк(К х) 1 ИКи==2 2 !Т х == 1 и К тлвп == О 3 гегагп О 4 е1ве гегпгп нп.
5 еВеИ К тах 51 н1ь и х > К тах 6 гегпгв К тах 7 еВе твп-1ош = чЕВ-Тккк-Мпп!мпм(К с1ия1ет[Ы8Ь(х)[) 8 И тт-1ош ф мй. и 1оч (х) > тт-1ош 9 овале! = чЕВ-Тккк-Ркнпкскввок(К с1ия1ет[Ь!8Ь(х)[,1оьт(х)) 10 гегнгп !пс1ех(Ы8Ь(х), офе1) 11 е!ве ртес)-с1ия1ет = чЕВ-Тккк-Ркюкскввок(Кяиттату, Ь!8Ь(х)) 12 И' ртес(-с1ия1ет == нп. 13 ИКтт ф нп.
их > Ктт 14 гегпгп К тт 15 е!ве гегпгп нп. 16 е!ве оДве! = ЧЕВ-ТКЕЕ-МЛХ1МПМ(К с1ия1ет[ртес1-с1иягет[) 17 гевнгп 1пдех(ртес1-с1иягет, о((яе1 ) В строках !3 и 14 образуется дополнительное ветвление. Этот случай осуществляется„когда предшественник х, если таковой существует, располагается не в кластере х.
В процедуре чЕВ-Тккк-Япсскввок мы точно знали, что если преемник х находится вне кластера х, то он должен находиться в кластере с ббльшнм номером. Но если предшественник х является минимальным элементом чЕВ-дерева К, то этот предшественник вообще не находится в кластере. В строке 13 выполняется проверка этого условия, а в строке 14 при необходимости возвращается минимальное значение дерева. Этот дополнительный случай не оказывает влияния на асимптотическое время работы процедуры чЕВ-Тккк-Рккпксрввок по сравнению с процедурой чЕВТккк-Бпссрввок, так что в наихудшем случае время работы процедуры чЕВТкее-Ркепесе Явок составляет О(!8!8 и).
Вставка элемента Теперь рассмотрим вставку в дерево ван Эмде Бааса. Вспомним, что процедура Ркото-чЕВ-1нвккт делает два рекурсивных вызова: один для вставки элемента, второй — для вставки в резюме номера кластера элемента. Процедура чЕВТккк-!нвккт будет обходиться только одним рекурсивным вызовом. Как этого 5В9 /лава 2д деревья вам Эмде Боаса добиться? Когда мы вставляем элемент, кластер, в который он попадает, либо уже имеет другой элемент, либо не имеет. Если в кластере уже есть другой элемент, то номер этого кластера уже находится в резюме, так что выполнять этот рекурсивный вызов нет необходимости. Если же кластер не содержит никакого другого элемента, то этот вставляемый элемент становится единственным элементом кластера, и нам не нужна рекурсия для того, чтобы вставить элемент в пустое ЧЕВ- дерево.
ЧЕВ-ЕмРТЧ-Тккк-1мзккт(К х) 1 Ктт=х 2 Ктах=х Имея эту вспомогательную процедуру, можно записать псевдокод процедуры ЧЕВ-Тккк-1яккт(К х), предполагающей, что х не является элементом, уже находящимся в множестве, которое представлено чЕВ-деревом К. ЧЕВ-Тккк-1нзккт(К х) 1 !ТКт1п==мь 2 чЕВ-ЕмРтч-Ткее-1хзект(К х) 3 е!ае !! х < Кт1п 4 Обменять х с Ктгн 5 !ТКи>2 6 !! чЕВ-Ткее-М!м!мам(К с1иа1ег[Ь18Ь(х))) == !ч!ь 7 ЧЕВ-Тккк-!мзккт(К Ваттов, Ь18Ь(х)) 8 ЧЕВ-ЕМРтч-Тккк-1нзккт(К с1иа1ег[Ь!8Ь(х)), !оэг(х)) 9 еВе ЧЕВ-Тккк-1мзккт(К с(иа1ег[Ы8Ь(х)), 1ож(х)) 10 !Тх > Ктах 1! Ктах = х Эта процедура работает следующим образом.
В строке 1 выполняется проверка, не является ли К пустым ЧЕВ-деревом, и если это так, то этот простой случай обрабатывается строкой 2. В строках 3-11 предполагается, что К не пустое, а значит, некоторый элемент будет вставлен в один из кластеров К.
Но этот элемент не обязательно представляет собой элемент х, переданный процедуре ЧЕВ-Тккк-1нзккт. Если х < тт, что проверяется в строке 3, то х должен стать новым элементом тт. Однако мы не хотим потерять исходный элемент тэп, так что нужно вставить его в один из кластеров К. В этом случае в строке 4 выполняется обмен х и т1п, так что мы вставляем в один из кластеров К исходный элемент т1п. Строки 6-9 выполняются, только если К не является баювым ЧЕВ-деревом. В строке 6 выясняется, не является ли кластер для размещения элемента х в настоящее время пустым. Если это так, то строка 7 вставляет номер кластера х в резюме, а строка 8 обрабатывает простой случай вставки х в пустой кластер. Если кластер х в настоящее время не пустой, то строка 9 вставляет х в его кластер. В этом случае обновлять резюме не нужно, поскольку номер кластера х уже содержится в резюме.
Часть и Слажные структуры данных 5РО Наконец строки 10 и 1! заботятся об обновлении тах, если х > тах. Заметим, что если К представляет собой непустое чЕВ-дерево в базовом случае, то строки 3 и 4, а также 10 и 11 корректно обновляют атрибуты тт и тах. И вновь легко увидеть, как рекурреитное соотношение (20.4) описывает время работы рассматриваемой процедуры. В зависимости от результатов проверки в строке 6, выполняется либо рекурсивный вызов в строке 7 (для чЕВ-дерева с размером универсума 5е/ии), либо рекурсивный вызов в строке 9 (для чЕВ-дерева с размером универсума ~/и).
В любом случае выполняется один рекурсивный вызов для чЕВ-дерева с размером универсума не более ~~/й. Поскольку остальная часть процедуры ЧЕВ-Ткее-11чвект выполняется за время 0(1), применимо рекуррентное соотношение (20.4), и общее время работы составляет 0(18 18 и). Удаление элемента Наконец рассмотрим, как удалить элемент из дерева ван Эмде Бааса. В процедуре ЧЕВ-Ткее-Пееете(К х) предполагается, что х в настоящий момент является элементом множества, представленного чЕВ-деревом К. чЕВ-Ткее-)3ееете(1~, х) 1 1ТКт1п == Ктах 2 Ктпвп = 1ч1е 3 Ктах = 1ч!е 4 е!ве(Т К и == 2 5 !Гх==О 6 Ктеп = 1 7 е1ве Ктьп = 0 8 Ктах = Кт1п 9 е1ве 1Т х == К тт !О 11гвг-с(ивгет = ЧЕВ-Ткее-М11ч1мпм(К зиттагу) 11 х = 1пс)ех(Ятв1с1ив1ег, чЕВ-Ткее-М11ч1мОм(К с1изгетфтв1-с1ивгег[)) Ктвп = х чЕВ-ТЕЕЕ-13ЕЕЕТЕ(К с1ив1ет[ЫЕЦх)[, 1о5ч(х)) !Г ЧЕВ-Ткее-М! п1мпм(К с(иззет[ЫЕЦх)[) == 1ч1е ЧЕВ-ТкеЕ-13Ееете(К зиттагу, ЫЕЬ(х)) !Т х == К тах витптпату-тах = ЧЕВ-ТЕЕЕ-МАх1мпм(Кзиттату) 11 витптату-тах == 1Ч1Е Ктах = Ктт е!ве К тах = 1пс1ех(зиттату-тах, ЧЕВ-ТЕЕЕ-МАХ1мпм(К с1ив1ег[виттату-тах[)) 21 е1ве(Т х == К тах 22 К тах = 1пс!ех(Ы8п(х), ЧЕВ-ТКЕЕ-МЛХ1МОМ(К с1изгег[Ы8п(х)[)) Глава 5Д Деревья вая Эмде Баева 595 Процедура чЕВ-Ткее-Рееете работает следующим образом.
Если чЕВ- дерево (Г содержит толью один элемент, то удалить его так же просто, как и вставить в пустое чЕВ-дерево: просто нужно установить тт и тах равными нп.. Этот случай обрабатывается в строках 1-3. В противном случае Ъ' содержит как минимум два элемента. В строке 4 проверяется, представляет ли собой Ъ' базовый случай, и если представляет, то в строках 5 — 8 атрибуты тзп и тах устанавливаются равными одному остающемуся элементу. В строках 9-22 предполшается, что 1л содержит два или более элементов и что и ) 4. В этом случае необходимо удалить элемент из кластера.
Однако элемент, который удаляется из кластера, может не быть элементом х, поскольку если х равен тт, то, когда мы удалим х, новым твп станет некоторый другой элемент из кластеров Ъ', и потребуется удалить этот другой элемент из его кластера. Если проверка в строке 9 указывает на этот случай, строка 10 устанавливает 11гв1-с1ив1ег равным номеру кластера, который содержит наименьший элемент, отличный от тзп, а строка 11 устанавливает х равным значению наименьшего элемента в этом кластере.
Этот элемент становится новым атрибутом твп в строке 12, а поскольку мы присваиваем х его значение, то этот элемент и будет удален из своего кластера. Когда мы достигаем строки 13, мы знаем, что должны удалить элемент х из его кластера независимо от того, является ли х исходным переданным процедуре ЧЕВ-ТКЕЕ-РЕЕЕТЕ значением или х представляет собой элемент, который становится новым минимумом.
В строке 13 х удаляется из его кластера. Этот кластер может стать пустым, что и проверяется в строке 14, и если это так, то нужно удалить номер кластера х из резюме (что и происходит в строке 15). После обновления резюме может потребоваться обновить атрибут тах. В строке 16 проверяется, не удаляем ли мы максимальный элемент 1', и если зто так, то в строке 17 виттат у-тах получает номер непустого кластера с наибольшим номером.
(Вызов чЕВ-Ткее-Млх1мггм()л, виттагу) работает, поскольку мы должны были рекурсивно вызвать чЕВ-Ткее-Рееете для 1Г. виттагу, и, таким образом, )Г. виттагу. тах уже должен быть обновлен (если в этом есть необходимость).) Если все кластеры 1' пусгые, то единственный остаюшийся в )Г элемент — тт; этот случай проверяется в строке 18, а в строке 19 выполняется соответствующее обновление тах. В противном случае в строке 20 выполняется присваивание атрибуту тах максимального элемента в непустом кластере с наибольшим номером.
(Если элемент был удален из этого кластера, мы снова полагаемся на то, что рекурсивный вызов в строке 13 уже скорректировал атрибут тах этого кластера.) Наконец необходимо обработать случай, когда кластер х не стал пустым из-за удаления х. Хотя в этом случае обновлять резюме не нуясно„может потребоваться обновление тах. Этот случай проверяется в строке 21, и при необходимости обновить тах это делается в строке 22 (и вновь мы полагаемся на рекурсивный вызов для коррекции тах). Теперь покажем, что в наихудшем случае время работы процедуры чЕВ- ТКЕЕ-РН.ЕТЕ составляет 0(18 18 и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
