Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 125
Текст из файла (страница 125)
До сих пор параметр п использовался нами для двух разных целей: как количество элементов в динамическом множестве и как диапазон возможных значений. Во избежание дальнейших недоразумений с этого момента мы будем использовать п для обозначения количества элементов множества в данный момент, а и — для обозначения диапаюна возможных значений, так что каждая операция над деревом ван Эмде Боаса выполняется за время О(1л !ли).
Множество (О, 1, 2,..., и — 1) будем называть уннвеуеуман (ип!чегзе) или генеральной совокупностью значений, которые могут храниться в дереве, а и — развверавв универсума. В этой главе мы полагаем и равным точной степени 2, т.е. и = 2" для некоторого целого )е > 1. Раздел 20.1 начинается с рассмотрения некоторых простых подходов, которые укажут нам верное направление. Эти подходы будут усовершенствованы в разделе 20.2 путем введения рекурсивных протоструктур ван Эмде Боаса, которые не позволяют достичь нашей цели — выполнения операций за время 0(!к !я и).
В разделе 20.3 протоструктуры будут модифицированы для создания деревьев ван Эмде Боаса и будет показано, как реализовать каждую операцию так, чтобы она выполнялась за время 0(1я 1й и). 20.1. Предварительные подходы В этом разделе мы рассмотрим различные подходы к задаче хранения динамического множества. Хотя ни один из них не дает искомое время О(1к 1к и), мы получим необходимые знания, которые помогуг нам понять деревья ван Эмде Боаса, когда позже мы встретимся с ними в этой главе. Прямая адресации Прямая адресация, как мы видели в разделе 11.1, предоставляет простейший подход к хранению динамического множества.
Поскольку в этой главе нас интересует только хранение ключей, мы можем упростить подход прямой адресации для хранения динамического множества в виде битового вектора, как обсуждалось в упр. 11.1.2. Для хранения динамического множества значений из универсума (О, 1, 2,..., и — Ц мы поддерживаем массив А[0 .. и — 1) из и бит. Элемент А[х) хранит 1, если значение х находится в динамическом множестве, и 0 — в противном случае.
Хотя каждая из операций 1нзект, Пн.ете и Мемвек при использовании битового вектора выполняется за время О(1), каждая из операций М!Н!МОМ, МАХ!МОМ, ЯОССЕЗЗОК и РКЕПЕСЕЗЗОК выполняется за время вЭ(и) в наихудшем случае, поскольку нам может потребоваться просканировать гЭ[и) Часть и Сложные струюнуры данныл 510 элементов.2 Например, если множество содержит только значения 0 и и — 1, то для поиска последующего за 0 элемента необходимо просканировать элементы с 1 по и — 2, перед тем как будет найдено значение 1 в А[и — 1]. Наложение структуры бинарного дерева Можно сократить длинные сканирования битового вектора, если наложить на него бинарное дерево. Пример показан на рис. 20.1. Элементы битового вектора образуют листья бинарного дерева, и каждый внутренний узел содержит 1 тогда и только тогда, когда некоторый лист в его поддереве содержит 1.
Другими словами, бит, храшпцийся во внутреннем узле, представляет собой логическое ИЛИ его дочерних узлов. ф ',г 11~С ~~гЗ 7~1 ь 1 17 ~6':ь:Пуг7 з71)ть1гтьСь~д: -'.(~а"::~~~ О 1 2 3 4 5 б 7 8 9 1О 11 12 13 14 15 Рнс. 2ЕЛ. Бинарное дерево битов, налшкенное на битовый вектор, предстаюгяюший мнекество (2, 3, 4, б, 7, 14, 1Ц при и = 16. Каждый внутренний узел ащержит 1 тогда и только тогда, когда некоторый лист его поддерева содержит 1. Стрелки показывают путь, по которому определяется предшественник 14 в данном мнткестве. Операции, которые в простом битовом векторе в наихудшем случае выполнялись за время ст(и), теперь используют структуру дерева. Для поиска минимального значения множества следует начать работу с корня и двигаться к листьям, всегда выбирая крайний слева узел, содержащий 1.
Для поиска минимального значения множества следует начать работу с корня и двигаться к листьям, всегда выбирая крайний справа узел„содержащий 1. Для поиска преемника х следует начать работу с листа, индексированного х, и двигаться вверх к корню„пока не войдем слева в узел, правый дочерний узел которого 2 содержит 1. Затем нужно двигаться вниз через узел я, всегда выбирая крайний слева узел, содержащий 1 1т.е.
искать минимальное значение в поддереве с корнем в я). В зтой гладе ым счатым, что пренсдуры Мгнгмпм а Млхгмцм а сл1 час пустого месжеспм воза1защают юг, а пропедурм зпсскязок и Ркяпдсдяяок возвращают зго значение, тли заданный злемеиг ае имеет сеотдегстаеино последующего «лн предщеегьуююеш злемеата. Гжеа 20. Деревья яон Эмде Боааз 571 ° Для поиска предшественника к следует начать работу с листа, индексированного я, и двигаться вверх к корню, пока не войдем справа в узел„левый дочерний узел которого л содержит 1.
Затем следует двигаться вниз через узел л, всегда выбирая крайний справа узел, содержащий 1 (т.е. искать максимальное значение в поддереве с корнем в л). Наложение дерева постоянной высоты Что произойдет, если выполнить наложение дерева с большей степенью? Пусть размер универсума равен и = 2зь для некоторого целого зс, так что /м представляет собой целое число. Вместо наложения поверх битового вектора бинарного дерева выполним наложение дерева со степенью чуй. На рис. 20.2,(а) показано такое дерево для того же битоиого вектора, что и на рис. 20.1. Высота такого дерева всегда равна 2.
Как и ранее, каждый внутренний узел хранит результат логического ИЛИ битов в его поддереве, так что,/и внутренних узлов на глубине 1 подводят итог для каждой группы из ь/й значений, Как показано на рис. 20.2,(б), зги узлы можно рассматривать как массив литтагу[0 .. т/й — 1), где литпзагу[2) содерлснт 1 тогда О 1 З З м3м м3т,2733 З-'[Г1 '553,/я бит л)Ф)р!1) 3) зт(2)е(зча3го)р)о1с))2[21)З", О 1 2 3 4 5 б 7 В В Ю 31 12 32 14 35 л 1о[й) 5)-,зф [ 5)[о",Да [о3010$о (зз) зз(17) О 3 2 3 4 5 б 7 В В 30 13 12 12 и 35 м Рис. 20.2. (а) Дерево со степенью ОЯ~ наложенное на тот же битовый вектор, что и на рис.
20.1. Кюкдый внузренний узел хранит логическое ИЛИ битов своих поддеревьев. (6) Вид той же струк- туры, но с внутренними узлами на глубине 1, рассматриваемыми как массив янзлзлогу[0 ., ь3и — 1), где яизпглагр[В) представляетсобой логическое ИЛИ полмассива А[2233и..
(2+ 1)з/и — 1). На рис. 20.1 показан нуть, пройденный в поисках 7 — предшественника значения 14. Мы соответствующим образом расширяем также операции 1МЗбпт и ПН.йтб. При вставке значения мы сохраняем 1 в каждом узле на простом пути от соответствующего листа вверх до корня. При удалении мы также идем от соответствующего листа до корня, попутно заново вычисляя биты каждого внутреннего узла пути как логическое ИЛИ значений двух его дочерних узлов. Поскольку высота дерева равна )к и и каждая из перечисленных операций выполняет не более одного прохода вверх по дереву и не более одного прохода вниз, то в наихудшем случае каждая операция выполняется за время О(1я и). Этот подход лишь немногим лучше простого применения красно-черных деревьев.
Мы в состоянии выполнить операцию Мбмвбн за время О(1), в то время как в красно-черном дереве для этого потребовалось бы время О()яп). В то же время если количество п элементов множества гораздо меньше размера универсума и, красно-черное дерево окажется быстрее в случае всех прочих операций. 572 Часть и Снежные структуры ааннык и только тогда, когда подмассив А(гь2и .. (е+1) /й — Ц содержит 1. Мы называем этот,/и-битовый подмассив А 1-м «ласяеерам (с1ижег). Для данного значения к бит А(х) находится в кластере номер (х/~/и~.
Теперь процедура 1меект становится операцией со временем работы 0(1): для вставки х следует установить А(т] и аиттату(~х/,~иЦ равными 1. Можно использовать массив ьиттагу для выполнения каждой из операций М1ммим, Млх5мим, Яиссеззок, Ркепесеезок и 11ЕЕЕТЕ за время О( „Ги). Для поиска минимального (максимального) значения следует найти крайний слева (справа) элемент еипеепату, который содержит 1, скажем, аиттаеу~г), а затем выполнить линейный поиск в 1-м кластере крайней слева (справа) 1. Для поиска преемника (предшественника) х сначала следует выполнить поиск вправо (влево) в пределах его кластера. Если мы находим 1, ее позиция дает нам искомый результат. В противном случае положим 1 = (х/~/и~ и выполним поиск в массиве зиттлагу вправо (влево) от индекса ес Первая позиция, хранящая 1, дает индекс кластера.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
