Алгоритмы и структуры данныхНовая версия для Оберона cdмосква, 2010Никлаус ВиртПеревод с английского под редакцией
 Скачать 2.67 Mb.
|
До сих пор наше обсуждение ограничивалось двоичными деревьями, то есть таки% ми, где каждый узел имеет не более двух потомков. Этого вполне достаточно, если, например, мы хотим представить семейные связи, подчеркивая происхож% дение, то есть указывая для каждого человека его двух родителей. Ведь ни у кого не бывает больше двух родителей. Но что, если возникнет необходимость указы% вать потомков каждого человека? Тогда придется учесть, что у некоторых людей больше двух детей, и тогда деревья будут содержать узлы со многими ветвями. Будем называть такие деревья сильно ветвящимися. Разумеется, в подобных структурах нет ничего особенного, и мы уже знакомы со всеми средствами программирования и определения данных, чтобы справиться с такими ситуациями. Например, если задан абсолютный верхний предел на число детей (такое предположение, конечно, немного футуристично), то можно представ% лять детей полем%массивом в записи, представляющей человека. Но если число де% тей сильно зависит от конкретного индивида, то это может привести к плохому ис% пользованию имеющейся памяти. В этом случае гораздо разумнее организовать потомство с помощью линейного списка, причем указатель на младшего (или стар% шего) потомка хранится в записи родителя. Возможное определение типа для этого случая приводится ниже, а возможная структура данных показана на рис. 4.40. TYPE Person = POINTER TO RECORD name: alfa; sibling, offspring: Person END Б<деревья (B Динамические структуры данных 228 При наклоне картинки на 45 градусов она будет выглядеть как обычное дво% ичное дерево. Но такой вид вводит в заблуждение, так как функциональный смысл двух структур совершенно разный. Обычно нельзя безнаказанно обра% щаться с братом как с сыном и не следует так поступать даже при определении структур данных. Структуру данных в этом примере можно усложнить еще больше, вводя в запись для каждого индивида дополнительные компоненты, представляющие другие семейные связи, например супружеские отношения между мужем и женой или даже информацию о родителях, ведь подобную ин% формацию не всегда можно получить из ссылок от родителей к детям и к брать% ям%сестрам. Подобная структура быстро вырастает в сложную реляционную базу данных, на которую можно отобразить несколько деревьев. Алгоритмы, ра% ботающие с такими структурами, тесно связаны с соответствующими определе% ниями данных, так что не имеет смысла указывать ни какие%либо общие прави% ла, ни общеприменимые приемы. Однако есть очень полезная область применения сильно ветвящихся деревьев, представляющая общий интерес. Это построение и поддержка больших деревьев поиска, в которых нужно выполнять вставки и удаления элементов, но опера% тивная память компьютера либо недостаточна по размеру, либо слишком дорога, чтобы использовать ее для длительного хранения данных. Итак, предположим, что узлы дерева должны храниться на внешних устрой% ствах хранения данных, таких как диски. Динамические структуры данных, введенные в этой главе, особенно удобны для того, чтобы использовать внешние носители. Главная новация будет просто в том, что роль указателей теперь будут играть дисковые адреса, а не адреса в оперативной памяти. При использовании двоичного дерева для набора данных из, скажем, миллиона элементов потребу% ется в среднем примерно ln 10 6 (то есть около 20) шагов поиска. Поскольку здесь каждый шаг требует обращения к диску (с неизбежной задержкой), то крайне желательно организовать хранение так, чтобы уменьшить число таких обраще% ний. Сильно ветвящееся дерево – идеальное решение проблемы. Если имеет мес% то обращение к элементу на внешнем носителе, то без особых усилий становится доступной целая группа элементов. Отсюда идея разделить дерево на поддеревья таким образом, чтобы эти поддеревья представлялись блоками, которые доступ% Рис. 4.40. Сильно ветвящееся дерево, представленное как двоичное дерево 229 ны сразу целиком. Назовем такие поддеревья страницами. На рис. 4.41 показано двоичное дерево, разделенное на страницы по 7 узлов на каждой. Рис. 4.41. Двоичное дерево, разделенное на страницы Экономия на числе обращений к диску – теперь обращение к диску соответ% ствует обращению к странице – может быть значительной. Предположим, что на каждой странице решено размещать по 100 узлов (это разумное число); тогда де% рево поиска из миллиона элементов потребует в среднем только log 100 (10 6 ) (то есть около 3) обращений к страницам вместо 20. Правда, при случайном росте де% рева это число все равно может достигать 10 4 в наихудшем случае. Ясно, что рос% том сильно ветвящихся деревьев почти обязательно нужно как%то управлять. 4.7.1. Сильно ветвящиеся Б=деревья Если искать способ управления ростом дерева, то следует сразу исключить требо% вание идеальной сбалансированности, так как здесь понадобятся слишком боль% шие накладные расходы на балансировку. Ясно, что нужно несколько ослабить требования. Весьма разумный критерий был предложен Бэйером и Маккрейтом в 1970 г. [4.2]: каждая страница (кроме одной) содержит от n до 2n узлов, где n – некоторая заданная константа. Поэтому для дерева из N элементов и с максималь% ным размером страницы в 2n узлов потребуется в худшем случае log n N обраще% ний к страницам; а именно на обращения к страницам приходятся основные уси% лия в подобном поиске. Более того, важный коэффициент использования памяти будет не меньше 50%, так как страницы всегда будут заполнены по крайней мере наполовину. Причем при всех этих достоинствах описываемая схема требует сравнительно простых алгоритмов для поиска, вставки и удаления элементов. В дальнейшем мы подробно изучим их. Такую структуру данных называют Б деревом (также B%дерево; B%tree), число n – его порядком, и при этом предполагаются следующие свойства: 1. Каждая страница содержит не более 2n элементов (ключей). 2. Каждая страница, кроме корневой, содержит не менее n элементов. Б<деревья (B Динамические структуры данных 230 3. Каждая страница либо является концевой, то есть не имеет потомков, либо имеет m+1 потомков, где m – число ключей на этой странице. 4. Все концевые страницы находятся на одном уровне. Рисунок 4.42 показывает Б%дерево порядка 2, имеющее 3 уровня. На всех стра% ницах – 2, 3 или 4 элемента; исключением является корень, где разрешено иметь только один элемент. Все концевые страницы – на уровне 3. Ключи будут стоять в порядке возрастания слева направо, если Б%дерево «сплющить» в один слой так, чтобы потомки вставали между ключами соответствующих страниц%предков. Та% кая организация является естественным развитием идеи двоичных деревьев поис% ка и предопределяет способ поиска элемента с заданным ключом. Рассмотрим страницу, показанную на рис. 4.43, и пусть задан аргумент поиска x . Предполагая, что страница уже считана в оперативную память, можно использовать обычные методы поиска среди ключей k 0 ... k m–1 . Если m велико, то можно применить по% иск делением пополам; если оно мало, то будет достаточно обычного последова% тельного поиска. (Заметим, что время поиска в оперативной памяти будет, веро% ятно, пренебрежимо мало по сравнению со временем считывания страницы в оперативную память из внешней.) Если поиск завершился неудачей, то возника% ет одна из следующих ситуаций: 1. k i < x < k i+1 для 0 < i < m–1 Поиск продолжается на странице p i ^ 2. k m–1 < x Поиск продолжается на странице p m–1 ^ 3. x < k 0 Поиск продолжается на странице p –1 ^ Рис. 4.42. Б:дерево порядка 2 Рис. 4.43. Б:дерево с m ключами 231 Если в каком%то случае указатель оказался равен NIL , то есть страница%пото% мок отсутствует, то это значит, что элемента с ключом x во всем дереве нет, и по% иск заканчивается. Удивительно, но вставка в Б%дерево тоже сравнительно проста. Если элемент нужно вставить на странице с m < 2n элементами, то вставка затрагивает только содержимое этой страницы. И только вставка в уже заполненную страницу затро% нет структуру дерева и может привести к размещению новых страниц. Чтобы по% нять, что случится в этом случае, рассмотрим рис. 4.44, который показывает вставку ключа 22 в Б%дерево порядка 2. Здесь выполняются следующие шаги: 1. Обнаруживается, что ключа 22 в дереве нет; вставка на странице C невоз% можна, так как C уже полна. 2. Страница C разбивается на две (то есть размещается новая страница D ). 3. 2n+1 ключей поровну распределяются между страницами C и D , а средний ключ перемещается на один уровень вверх на страницу%предок A Рис. 4.44. Вставка ключа 22 в Б:дерево Эта очень изящная схема сохраняет все характеристические свойства Б%дере% вьев. В частности, разбиваемые страницы содержат в точности n элементов. Разу% меется, вставка элемента на странице%предке тоже может вызвать переполнение, так что снова нужно выполнять разбиение, и т. д. В крайнем случае, процесс раз% биений достигнет корня. И это единственный способ увеличить высоту Б%дерева. Странная манера расти у Б%деревьев: вверх от листьев к корню. Разработаем теперь подробную программу на основе этих набросков. Уже ясно, что самой удобной будет рекурсивная формулировка, так как процесс раз% биения может распространяться в обратном направлении по пути поиска. Поэто% му по общей структуре программа получится похожей на вставку в сбалансиро% ванное дерево, хотя в деталях будут отличия. Прежде всего нужно определить структуру страниц. Выберем представление элементов с помощью массива: TYPE Page = POINTER TO PageDescriptor; Item = RECORD key: INTEGER; p: Page; count: INTEGER (* *) END; PageDescriptor = RECORD m: INTEGER; (* 0 .. 2n *) p0: Page; e: ARRAY 2*n OF Item END Б<деревья (B Динамические структуры данных 232 Поле count представляет любую информацию, которая может быть связана с элементом, но оно никак не участвует собственно в поиске. Заметим, что каждая страница предоставляет место для 2n элементов. Поле m указывает реальное чис% ло элементов на данной странице. Так как m ≥ n (кроме корневой страницы), то гарантируется, что память будет использована по меньшей мере на 50%. Алгоритм поиска и вставки в Б%дерево сформулирован ниже в виде процедуры search . Его основная структура бесхитростна и подобна поиску в сбалансирован% ном двоичном дереве, за исключением того факта, что выбор ветви не ограничен двумя вариантами. Вместо этого поиск внутри страницы реализован как поиск делением пополам в массиве e. Алгоритм вставки для ясности сформулирован как отдельная процедура. Она вызывается, когда поиск показал, что нужно передать элемент вверх по дереву (в направлении корня). Это обстоятельство указывается булевским параметром% переменной h ; его использование аналогично случаю алгоритма вставки в сбалан% сированное дерево, где h сообщал, что поддерево выросло. Если h истинно, то вто% рой параметр%переменная u содержит элемент, передаваемый наверх. Заметим, что вставки начинаются в виртуальных страницах, а именно в так называемых дополнительных узлах (см. рис. 4.19); при этом новый элемент сразу передается через параметр u вверх на концевую страницу для реальной вставки. Вот набро% сок этой схемы: PROCEDURE search (x: INTEGER; a: Page; VAR h: BOOLEAN; VAR u: Item); BEGIN IF a = NIL THEN (*x , *) x u, h TRUE, , u ELSE x a.e; IF THEN ELSE search(x, descendant, h, u); IF h THEN (* *) IF a^ < 2n THEN u a^ h FALSE ELSE END END END END END search Если h равен TRUE после вызова процедуры search в главной программе, зна% чит, требуется разбить корневую страницу. Так как корневая страница играет осо% бую роль, то это действие следует запрограммировать отдельно. Оно состоит про% сто в размещении новой корневой страницы и вставке единственного элемента, 233 задаваемого параметром u . В результате новая корневая страница содержит единственный элемент. Полный текст программы приведен ниже, а рис. 4.45 по% казывает, как она строит Б%дерево при вставке ключей из следующей последова% тельности: 20; 40 10 30 15; 35 7 26 18 22; 5; 42 13 46 27 8 32; 38 24 45 25; Точки с запятой отмечают моменты, когда сделаны «снимки», – после каждого размещения страниц. Вставка последнего ключа вызывает два разбиения и разме% щение трех новых страниц. Рис. 4.45. Рост Б:дерева порядка 2 Поскольку каждый вызов процедуры поиска подразумевает одно копирование страницы в оперативную память, то понадобится не более k = log n (N) рекурсив% ных вызовов для дерева из N элементов. Поэтому нужно иметь возможность раз% местить k страниц в оперативной памяти. Это первое ограничение на размер стра% ницы 2n . На самом деле нужно размещать больше, чем k страниц, так как вставка может вызвать разбиение. Отсюда следует, что корневую страницу лучше посто% Б<деревья (B Динамические структуры данных 234 янно держать в оперативной памяти, так как каждый запрос обязательно прохо% дит через корневую страницу. Другое достоинство организации данных с помощью Б%деревьев – удобство и экономичность чисто последовательного обновления всей базы данных. Каждая страница загружается в оперативную память в точности один раз. Операция удаления элементов из Б%дерева по идее довольно проста, но в дета% лях возникают усложнения. Следует различать две разные ситуации: 1. Удаляемый элемент находится на концевой странице; здесь алгоритм уда% ления прост и понятен. 2. Элемент находится на странице, не являющейся концевой; его нужно заме% нить одним из двух соседних в лексикографическом смысле элементов, ко% торые оказываются на концевых страницах и могут быть легко удалены. В случае 2 нахождение соседнего ключа аналогично соответствующему алго% ритму при удалении из двоичного дерева. Мы спускаемся по крайним правым указателям вниз до концевой страницы P , заменяем удаляемый элемент крайним правым элементом на P и затем уменьшаем размер страницы P на 1 . В любом слу% чае за уменьшением размера должна следовать проверка числа элементов m на уменьшившейся странице, так как m < n нарушает характеристическое свойство Б%деревьев. Здесь нужно предпринять дополнительные действия; это условие не достаточной заполненности (underflow) указывается булевским параметром h Единственный выход – позаимствовать элемент с одной из соседних страниц, скажем Q . Поскольку это требует считывания страницы Q в оперативную память, – что относительно дорого, – есть соблазн извлечь максимальную пользу из этой нежелательной ситуации и позаимствовать за один раз больше одного элемента. Обычная стратегия – распределить элементы на страницах P и Q поровну на обеих страницах. Это называется балансировкой страниц (page balancing). Разумеется, может случиться, что элементов для заимствования не осталось, поскольку страница Q достигла минимального размера n . В этом случае общее число элементов на страницах P и Q равно 2n–1 , и можно объединить обе страни% цы в одну, добавив средний элемент со страницы%предка для P и Q , а затем пол% ностью избавиться от страницы Q . Эта операция является в точности обраще% нием разбиения страницы. Целиком процесс проиллюстрирован удалением ключа 22 на рис. 4.44. И здесь снова удаление среднего ключа со страницы%пред% ка может уменьшить размер последней ниже разрешенного предела n , тем са% мым требуя выполнения специальных действий (балансировки или слияния) на следующем уровне. В крайнем случае, слияние страниц может распространять% ся вверх до самого корня. Если корень уменьшается до размера 0, следует уда% лить сам корень, что вызывает уменьшение высоты Б%дерева. На самом деле это единственная ситуация, когда может уменьшиться высота Б%дерева. Рисунок 4.46 показывает постепенное уменьшение Б%дерева с рис. 4.45 при последова% тельном удалении ключей 25 45 24; 38 32; 8 27 46 13 42; 5 22 18 26; 7 35 15; 235 Здесь, как и раньше, точки с запятой отмечают места, где делаются «снимки», то есть там, где удаляются страницы. Следует особо подчеркнуть сходство струк% туры алгоритма удаления с соответствующей процедурой для сбалансированного дерева. Рис. 4.46. Удаление элементов из Б:дерева порядка 2 TYPE Page = POINTER TO PageRec; (* ADruS471_Btrees *) Entry = RECORD key: INTEGER; p: Page END; PageRec = RECORD m: INTEGER; (* *) p0: Page; e: ARRAY 2*N OF Entry END; VAR root: Page; W: Texts.Writer; Б<деревья (B Динамические структуры данных 236 PROCEDURE search (x: INTEGER; VAR p: Page; VAR k: INTEGER); VAR i, L, R: INTEGER; found: BOOLEAN; a: Page; BEGIN a := root; found := FALSE; WHILE (a # NIL) & found DO L := 0; R := a.m; (* *) WHILE L < R DO i := (L+R) DIV 2; IF x <= a.e[i].key THEN R := i ELSE L := i+1 END END; IF (R < a.m) & (a.e[R].key = x) THEN found := TRUE ELSIF R = 0 THEN a := a.p0 ELSE a := a.e[R–1].p END END; p := a; k := R END search; PROCEDURE insert (x: INTEGER; a: Page; VAR h: BOOLEAN; VAR v: Entry); (*a # NIL. x – a; (* x. (* , # v. (* h := " "*) VAR i, L, R: INTEGER; b: Page; u: Entry; BEGIN (* h *) IF a = NIL THEN v.key := x; v.p := NIL; h := TRUE ELSE L := 0; R := a.m; (* *) WHILE L < R DO i := (L+R) DIV 2; IF x <= a.e[i].key THEN R := i ELSE L := i+1 END END; IF (R < a.m) & (a.e[R].key = x) THEN (* v, #*) ELSE (* *) IF R = 0 THEN b := a.p0 ELSE b := a.e[R–1].p END; insert(x, b, h, u); IF h THEN (* u a.e[R]*) IF a.m < 2*N THEN h := FALSE; FOR i := a.m TO R+1 BY –1 DO a.e[i] := a.e[i–1] END; a.e[R] := u; INC(a.m) ELSE (* ; a a, b v*) NEW(b); IF R < N THEN (* a*) 237 v := a.e[N–1]; FOR i := N–1 TO R+1 BY –1 DO a.e[i] := a.e[i–1] END; a.e[R] := u; FOR i := 0 TO N–1 DO b.e[i] := a.e[i+N] END ELSE (* b*) DEC(R, N); IF R = 0 THEN v := u ELSE v := a.e[N]; FOR i := 0 TO R–2 DO b.e[i] := a.e[i+N+1] END; b.e[R–1] := u END; FOR i := R TO N–1 DO b.e[i] := a.e[i+N] END END; a.m := N; b.m := N; b.p0 := v.p; v.p := b END END END END END insert; PROCEDURE underflow (c, a: Page; s: INTEGER; VAR h: BOOLEAN); (*a = , # v (underflow), (* c = – , (* s = # c*) VAR b: Page; i, k: INTEGER; BEGIN (*h & (a.m = N–1) & (c.e[s–1].p = a) *) IF s < c.m THEN (*b := a*) b := c.e[s].p; k := (b.m–N+1) DIV 2; (*k = b*) a.e[N–1] := c.e[s]; a.e[N–1].p := b.p0; IF k > 0 THEN (* k–1 b a*) FOR i := 0 TO k–2 DO a.e[i+N] := b.e[i] END; c.e[s] := b.e[k–1]; b.p0 := c.e[s].p; c.e[s].p := b; DEC(b.m, k); FOR i := 0 TO b.m–1 DO b.e[i] := b.e[i+k] END; a.m := N–1+k; h := FALSE ELSE (* a b, b v *) FOR i := 0 TO N–1 DO a.e[i+N] := b.e[i] END; DEC(c.m); FOR i := s TO c.m–1 DO c.e[i] := c.e[i+1] END; a.m := 2*N; h := c.m < N END ELSE (*b := a*) DEC(s); IF s = 0 THEN b := c.p0 ELSE b := c.e[s–1].p END; k := (b.m–N+1) DIV 2; (*k = b*) Б<деревья (B Динамические структуры данных 238 IF k > 0 THEN FOR i := N–2 TO 0 BY –1 DO a.e[i+k] := a.e[i] END; a.e[k–1] := c.e[s]; a.e[k–1].p := a.p0; (* k–1 b a, c*) DEC(b.m, k); FOR i := k–2 TO 0 BY –1 DO a.e[i] := b.e[i+b.m+1] END; c.e[s] := b.e[b.m]; a.p0 := c.e[s].p; c.e[s].p := a; a.m := N–1+k; h := FALSE ELSE (* a b, a v *) c.e[s].p := a.p0; b.e[N] := c.e[s]; FOR i := 0 TO N–2 DO b.e[i+N+1] := a.e[i] END; b.m := 2*N; DEC(c.m); h := c.m < N END END END underflow; PROCEDURE delete (x: INTEGER; a: Page; VAR h: BOOLEAN); (* x – a; (* v , (* ; (* h := " v "*) VAR i, L, R: INTEGER; q: Page; PROCEDURE del (p: Page; VAR h: BOOLEAN); VAR k: INTEGER; q: Page; (*# a, R*) BEGIN k := p.m–1; q := p.e[k].p; IF q # NIL THEN del(q, h); IF h THEN underflow(p, q, p.m, h) END ELSE p.e[k].p := a.e[R].p; a.e[R] := p.e[k]; DEC(p.m); h := p.m < N END END del; BEGIN IF a # NIL THEN L := 0; R := a.m; (* *) WHILE L < R DO i := (L+R) DIV 2; IF x <= a.e[i].key THEN R := i ELSE L := i+1 END END; IF R = 0 THEN q := a.p0 ELSE q := a.e[R–1].p END; IF (R < a.m) & (a.e[R].key = x) THEN (* v*) IF q = NIL THEN (*a — *) DEC(a.m); h := a.m < N; FOR i := R TO a.m–1 DO a.e[i] := a.e[i+1] END ELSE del(q, h); IF h THEN underflow(a, q, R, h) END END ELSE 239 delete(x, q, h); IF h THEN underflow(a, q, R, h) END END END END delete; PROCEDURE ShowTree (VAR W: Texts.Writer; p: Page; level: INTEGER); VAR i: INTEGER; BEGIN IF p # NIL THEN FOR i := 1 TO level DO Texts.Write(W, 9X) END; FOR i := 0 TO p.m–1 DO Texts.WriteInt(W, p.e[i].key, 4) END; Texts.WriteLn(W); IF p.m > 0 THEN ShowTree(W, p.p0, level+1) END; FOR i := 0 TO p.m–1 DO ShowTree(W, p.e[i].p, level+1) END END END ShowTree; Эффективность Б%деревьев изучалась весьма подробно, результаты можно найти в упомянутой статье Бэйера и Маккрейта. В частности, там обсуждается вопрос оптимального размера страницы, который сильно зависит от характерис% тик используемой вычислительной системы и памяти. Вариации на тему Б%деревьев обсуждаются у Кнута ([2.7], с. 521–525 перево% да). Заслуживает внимания наблюдение, что разбиение страницы следует откла% дывать, как следует откладывать и слияние страниц, и сначала пытаться сбалан% сировать соседние страницы. В остальном похоже, что выгода от предлагавшихся улучшений незначительна. Весьма полный обзор Б%деревьев можно найти в [4.8]. |