Алгоритмы и структуры данныхНовая версия для Оберона cdмосква, 2010Никлаус ВиртПеревод с английского под редакцией
 Скачать 2.67 Mb.
|
|
4.7.2. Двоичные Б=деревья На первый взгляд, Б%деревья первого порядка ( n = 1 ) – наименее интересная их разновидность. Но иногда стоит присмотреться к особому случаю. Ясно, однако, что Б%деревья первого порядка не могут быть полезны для представления боль% ших упорядоченных индексированных наборов данных с использованием вне% шних устройств хранения. Поэтому мы теперь забудем про внешнюю память и снова рассмотрим деревья поиска, предполагая работу в оперативной памяти. Двоичное Б дерево (ДБ%дерево; BB%tree) состоит из узлов (страниц) с одним или двумя элементами. Поэтому страница содержит два или три указателя на по% томков; этим объясняется термин 2–3 дерево. В соответствии с определением Б%деревьев все концевые страницы находятся на одном уровне, а все неконцевые страницы ДБ%деревьев имеют двух или трех потомков (включая корень). Так как мы теперь имеем дело только с оперативной памятью, то нужно подумать об опти% мальном использовании памяти, так что представление элементов в узле с помо% щью массива не кажется подходящим. Альтернативой будет динамическое, связ% ное размещение; то есть в каждом узле есть связный список элементов длины 1 или 2. Так как у каждого узла не больше трех потомков и поэтому в нем нужно хранить не более трех указателей, соблазнительно объединить указатели на по% Б<деревья (B Динамические структуры данных 240 томков с указателями в списке элементов, как показано на рис. 4.47. Тогда узел Б%дерева теряет свою специфику и начинает играть роль узла обычного двоично% го дерева. Однако все%таки нужно отличать указатели на потомков (вертикальные стрелки) от указателей на «братьев» на той же странице (горизонтальные стрел% ки). Поскольку горизонтальными могут быть только указатели, направленные вправо, достаточно одного бита, чтобы отмечать эту разницу. Поэтому введем бу% левское поле h со значением «горизонтальный». Определение узла дерева для та% кого представления приводится ниже. Его предложил и исследовал в 1971 г. Бэй% ер (R. Bayer [4.3]); такая организация дерева поиска гарантирует максимальную длину пути p = 2*log(N) TYPE Node = POINTER TO RECORD key: INTEGER; left, right: Node; h: BOOLEAN (* # *) END Рис. 4.47. Представление узлов ДБ:деревьев Рассматривая вставку ключа, следует различать четыре возможных случая, возникающие при росте левых или правых поддеревьев. Эти четыре случая пока% заны на рис. 4.48. Напомним, что для Б%деревьев характерен рост снизу вверх к корню и что для них нужно обеспечивать, чтобы все концевые страницы были на одном уровне. Простейший случай (1) имеет место, когда растет правое поддерево узла A , причем A является единственным ключом на своей (виртуальной) странице. Тогда потомок B просто становится «братом» для A , то есть вертикальный указатель становится горизонтальным. Такое простое «поднимание руки» невозможно, если у A уже есть «брат». Тогда получается страница с 3 узлами, и ее нужно разбивать (случай 2). Ее средний узел B нужно передать на следующий уровень вверх. Теперь предположим, что увеличилась высота левого поддерева узла B . Если снова узел B на странице один (случай 3), то есть его правый указатель ссылается 241 на потомка, то левому поддереву ( A ) разрешается стать «братом» для B . (Так как левый указатель не может быть горизонтальным, то здесь нужна простая ротация указателей.) Но если у B уже есть «брат», то поднятие A создает страницу с тремя указателями, требующую разбиения. Это разбиение выполняется самым простым cпособом: C становится потомком B , который, в свою очередь, поднимается на сле% дующий уровень вверх (случай 4). Рис. 4.48. Вставка узлов в ДБ:дереве Б<деревья (B Динамические структуры данных 242 Нужно заметить, что при поиске ключей в сущности безразлично, идем ли мы по горизонтальному или по вертикальному указателю. Поэтому кажется неесте% ственным, что нужно беспокоиться о том, что левый указатель в случае 3 стано% вится горизонтальным, хотя его страница по%прежнему содержит не более двух членов. В самом деле, алгоритм вставки являет странную асимметрию для случа% ев роста левого или правого поддеревьев, так что ДБ%деревья кажутся довольно искусственной конструкцией. Не существует доказательства того, что это непра% вильно; но здоровая интуиция подсказывает, что здесь что%то неладно и что эту асимметрию следует устранить. Это приводит к понятию симметричного двоично го Б дерева (СДБ%дерево; SBB%tree), которое тоже было исследовано Бэйером в 1972 г. [4.4]. В среднем оно приводит к чуть более эффективному поиску, но при этом слегка усложняются алгоритмы вставки и удаления. Кроме того, в каждом узле теперь нужны два бита (булевские переменные lh и rh ), чтобы указать приро% ду двух его указателей. Мы ограничимся детальным рассмотрением задачи о вставках, и здесь нам снова нужно различать четыре случая роста поддеревьев. Они показаны на рис. 4.49, где очевидна симметрия, к которой мы стремились. Заметим, что каждый раз, когда растет поддерево узла A , не имеющего «брата», корень этого поддерева становится «братом» узла A . Этот случай можно в дальнейшем не рассматривать. Во всех четырех случаях, рассмотренных на рис. 4.49, возникает переполнение страницы с последующим ее разбиением. Случаи обозначены в соответствии с направлениями горизонтальных указателей, связывающих трех «братьев» в средних рисунках. Исходное положение показано в левом столбце; средний столбец иллюстрирует тот факт, что был поднят узел с более низкого уровня, ког% да выросло его поддерево; рисунки в правом столбце показывают окончательный результат перегруппировки узлов. Больше нет смысла сохранять понятие страниц, из которого эволюционировал этот способ организации дерева, поскольку мы только хотели бы ограничить макси% мальную длину пути величиной 2*log(N) . Для этого достаточно обеспечить, чтобы два горизонтальных указателя никогда не могли встречаться подряд ни на каком пути поиска. Однако нет резона запрещать узлы с горизонтальными указателями, направленными влево и вправо, то есть по%разному трактовать левое и правое. По% этому определим симметричное двоичное Б%дерево следующими свойствами: 1. Каждый узел содержит один ключ и не более двух поддеревьев (точнее, ука% зателей на них). 2. Каждый указатель является либо горизонтальным, либо вертикальным. Ни на каком пути поиска не могут идти подряд два горизонтальных указателя. 3. Все концевые узлы (узлы без потомков) находятся на одном уровне. Из этого определения следует, что самый длинный путь поиска не может более чем вдвое превышать по длине высоту дерева. Поскольку никакое СДБ%дерево с N узлами не может иметь высоту больше, чем log(N) , то немедленно получаем, что 2*log(N) – верхний предел на длину пути поиска. Наглядное представление о том, как растут такие деревья, дает рис. 4.50. Ниже приведены последователь% 243 ности вставляемых ключей, причем каждой точке с запятой соответствует кар% тинка, показывающая состояние дерева в данный момент. (1) 1 2; 3; 4 5 6; 7; (2) 5 4; 3; 1 2 7 6; (3) 6 2; 4; 1 7 3 5; (4) 4 2 6; 1 7; 3 5; Рис. 4.49. Вставка в СДБ:деревьях Б<деревья (B Динамические структуры данных 244 Эти картинки делают особенно очевидным третье свойство Б%деревьев: все концевые узлы находятся на одном уровне. Напрашивается сравнение со свеже% подстриженными садовыми оградами из кустарника. Алгоритм построения СДБ%деревьев показан ниже. Он основан на определе% нии типа Node с двумя компонентами lh и rh , указывающими соответственно, яв% ляется ли горизонтальным левый и правый указатель. TYPE Node = RECORD key, count: INTEGER; left, right: POINTER TO Node; lh, rh: BOOLEAN END Схема рекурсивной процедуры search снова повторяет основной алгоритм вставки в двоичное дерево. В нее введен третий параметр, указывающий, измени% лось ли поддерево с корнем p , и соответствующий параметру h программы поиска для Б%дерева. Однако нужно отметить одно следствие представления страниц связными списками: страница обходится за один или два вызова процедуры поис% ка. Поэтому следует различать случай выросшего поддерева (на который указы% Рис. 4.50. Вставки ключей с 1 по 7 245 вает вертикальная ссылка) от «братского» узла (на который указывает горизон% тальная ссылка), который получил нового «брата», так что требуется разбиение страницы. Проблема легко решается введением трехзначного параметра h со сле% дующими значениями: 1. h = 0 : поддерево p не требует изменений структуры дерева. 2. h = 1 : узел p получил «брата». 3. h = 2 : увеличилась высота поддерева p PROCEDURE search (VAR p: Node; x: INTEGER; VAR h: INTEGER); VAR q, r: Node; (* ADruS472_BBtrees *) BEGIN (*h=0*) IF p = NIL THEN (* *) NEW(p); p.key := x; p.L := NIL; p.R := NIL; p.lh := FALSE; p.rh := FALSE; h := 2 ELSIF x < p.key THEN search(p.L, x, h); IF h > 0 THEN (* " "*) q := p.L; IF p.lh THEN h := 2; p.lh := FALSE; IF q.lh THEN (*LL*) p.L := q.R; q.lh := FALSE; q.R := p; p := q ELSE (*q.rh, LR*) r := q.R; q.R := r.L; q.rh := FALSE; r.L := p.L; p.L := r.R; r.R := p; p := r END ELSE DEC(h); IF h = 1 THEN p.lh := TRUE END END END ELSIF x > p.key THEN search(p.R, x, h); IF h > 0 THEN (* " "*) q := p.R; IF p.rh THEN h := 2; p.rh := FALSE; IF q.rh THEN (*RR*) p.R := q.L; q.rh := FALSE; q.L := p; p := q ELSE (*q.lh, RL*) r := q.L; q.L := r.R; q.lh := FALSE; r.R := p.R; p.R := r.L; r.L := p; p := r END ELSE DEC(h); IF h = 1 THEN p.rh := TRUE END END END END END search; Б<деревья (B Динамические структуры данных 246 Заметим, что действия, выполняемые здесь для реорганизации узлов, очень похожи на то, что делается в алгоритме поиска для сбалансированных АВЛ%дере% вьев. Очевидно, что все четыре случая можно реализовать простыми ротациями указателей: простые ротации в случаях LL и RR , двойные ротации в случаях LR и RL . На самом деле процедура search оказывается здесь чуть более простой, чем для АВЛ%деревьев. Ясно, что схему СДБ%деревьев можно рассматривать как альтер% нативу идее АВЛ%балансировки. Поэтому разумно и полезно сравнить произво% дительность в двух случаях. Мы воздержимся от сложного математического анализа и сосредоточимся на некоторых основных отличиях. Можно доказать, что АВЛ%сбалансированные де% ревья составляют подмножество СДБ%деревьев. Так что множество последних шире. Следовательно, длина путей у них в среднем больше, чем у АВЛ%деревьев. В этой связи отметим реализующее наихудший случай дерево (4) на рис. 4.50. С другой стороны, реорганизовывать ключи здесь нужно реже. Поэтому сбалан% сированные деревья следует предпочесть в тех задачах, где поиск ключей выпол% няется гораздо чаще, чем вставки (или удаления); если эти частоты сравнимы, то предпочтительными могут стать СДБ%деревья. Очень трудно сказать, где прохо% дит граница. Здесь все сильно зависит не только от отношения частот поиска и реорганизации, но еще и от особенностей реализации. Это прежде всего касается тех случаев, когда для записи в узле используют плотно упакованное представ% ление, так что доступ к полям требует извлечения частей слова. СДБ%деревья позднее возродились под названием красно черных деревьев (red%black tree). Разница в том, что у симметричного двоичного Б%дерева каждый узел содержит два h %поля, которые сообщают, являются ли хранящиеся в узле указатели горизонтальными, а у красно%черного дерева каждый узел содержит единственное h %поле, сообщающее, является ли горизонтальным указатель, ссылающийся на этот узел. Название отражает идею считать узел черным или красным в зависимости от того, является ли указатель, ссылающийся на него, вертикальным или горизонтальным. Два красных узла никогда не могут идти под% ряд ни на каком пути. Поэтому, как и в случаях ДБ% и СДБ%деревьев, длина любо% го пути поиска превосходит высоту дерева не более чем вдвое. Существует кано% ническое отображение двоичных Б%деревьев на красно%черные. 4.8. Приоритетные деревья поиска Деревья, особенно двоичные, представляют собой очень эффективные способы организации данных, допускающих линейное упорядочение. В предыдущих гла% вах были показаны чаще всего используемые изобретательные схемы для эффективного поиска и обслуживания таких деревьев (вставки, удаления). Одна% ко не похоже, чтобы деревья были полезны в задачах, где данные располагаются не в одномерном, а в многомерном пространстве. На самом деле эффективный поиск в многомерных пространствах все еще остается одной из наиболее трудных проблем информатики, причем для многих приложений особенно важен случай двух измерений. 247 Присмотревшись к проблеме, можно обнаружить, что деревья все еще могут быть полезны, по крайней мере в двумерном случае. В конце концов, мы изобра% жаем деревья на бумаге в двумерном пространстве. Поэтому вспомним вкратце главные свойства двух основных видов деревьев, рассмотренных до сих пор. 1. Дерево поиска подчиняется следующим инвариантам: p.left ≠ NIL подразумевает p.left.x < p.x, p.right ≠ NIL подразумевает p.x < p.right.x, которые выполняются для всех узлов p с ключом x . Очевидно, что эти инва% рианты ограничивают только горизонтальное положение узлов и что их вертикальные позиции могут быть выбраны произвольно, чтобы миними% зировать время доступа при поиске (то есть длины путей). 2. Куча (heap), или приоритетное дерево (priority tree), подчиняется следую% щим инвариантам: p.left ≠ NIL подразумевает p.y ≤ p.left.y, p.right ≠ NIL подразумевает p.y ≤ p.right.y, и оба свойства выполняются для всех узлов p с ключом y . Очевидно, эти инварианты ограничивают только положение узлов по вертикали. Можно объединить две эти пары условий в одном определении способа дре% весной организации в двумерном пространстве, подразумевая, что каждый узел имеет два ключа x и y , которые можно считать координатами узла. Такое дерево представляет собой набор точек в плоскости, то есть в двумерном декартовом про% странстве; поэтому его называют декартовым деревом [4.9]. Мы предпочитаем название приоритетное дерево поиска, так как оно показывает, что эта структура возникла из комбинации приоритетного дерева и дерева поиска. Определяющими здесь являются следующие инварианты, выполняющиеся для каждого узла p : p.left ≠ NIL подразумевает (p.left.x < p.x) & (p.y ≤ p.left.y) p.right ≠ NIL подразумевает (p.x < p.right.x) & (p.y ≤ p.right.y) Однако не должно сильно удивлять, что эффективность поиска в таких дере% вьях не особо впечатляющая. Ведь здесь гораздо меньше свободы для выбора расположения узлов, которое могло бы обеспечить короткие пути поиска. По% этому не удается гарантировать логарифмические ограничения на вычисли% тельные затраты при поиске, вставке или удалении элементов. Хотя в отличие от обычных несбалансированных деревьев поиска, где ситуация была такой же, здесь шансы на хорошее поведение в среднем невелики. Хуже того, операции вставки и удаления могут быть весьма громоздкими. Например, рассмотрим де% рево на рис. 4.51a. Если координаты нового узла C таковы, что он должен нахо% диться над и между узлами A и B , то потребуются серьезные усилия для преобра% зования (a) в (b). МакКрейт нашел схему, похожую на балансировку, которая гарантирует лога% рифмические временные ограничения для операций вставки и удаления за счет их усложнения. Он назвал свою схему приоритетным деревом поиска [4.10]; одна% Приоритетные деревья поиска Динамические структуры данных 248 ко в нашей классификации ее нужно называть сбалансированным приоритетным деревом поиска. Мы воздержимся от обсуждения этой схемы, так как она очень сложна и вряд ли используется на практике. Решая несколько более ограничен% ную, но не менее полезную для приложений задачу, МакКрейт нашел еще одну древесную структуру, которую мы рассмотрим полностью. Вместо бесконечного пространства поиска он рассмотрел пространство данных, ограниченное с двух сторон. Обозначим граничные значения для координаты x как x min и x max В вышеописанной схеме (несбалансированных) приоритетных деревьев по% иска каждый узел p делит плоскость на две части линией x = p.x . Все узлы лево% го подддерева лежат слева от p , а все узлы правого – справа. Для эффективного поиска такой выбор, вероятно, плох. К счастью, можно выбрать разделительную линию по%другому. Свяжем с каждым узлом p интервал [p.L .. p.R) , состоящий из всех значений x от (и включая) p.L и до (но исключая) p.R . В этом интервале разрешено находиться значению координаты x узла p . Затем потребуем, чтобы левый потомок (если он есть) лежал в левой половине, а правый – в правой по% ловине этого интервала. Поэтому разделительная линия – это не p.x , а (p.L+p.R)/2 Для каждого потомка интервал делится пополам, так что высота дерева ограни% чивается величиной log(x max –x min ) . Этот результат выполняется, только если нет ни одной пары узлов с одинаковым значением x ; впрочем, это условие гаран% тировано инвариантом. Если координаты – целые числа, то этот предел не мо% жет превышать длину компьютерного слова. В сущности, поиск протекает как в алгоритме деления пополам или в поиске по остаткам (radix search), и поэтому такие деревья называют приоритетными деревьями поиска по остаткам (radix priority search trees, [4.10]). Для них имеют место логарифмические ограниче% ния на число операций, необходимых для поиска, вставки и удаления элемента, и для них также справедливы следующие инварианты, выполняющиеся для каждого узла p : p.left ≠ NIL влечет (p.L ≤ p.left.x < p.M) & (p.y ≤ p.left.y) p.right ≠ NIL влечет (p.M ≤ p.right.x < p.R) & (p.y ≤ p.right.y) Рис. 4.51. Вставка в приоритетное дерево поиска 249 где p.M = (p.L + p.R) DIV 2 p.left.L = p.L p.left.R = p.M p.right.L = p.M p.right.R = p.R для всех узлов p, причем root.L = x min , root.R = x max Решающее достоинство такой схемы – в том, что операции обслуживания при вставке и удалении (сохраняющие инварианты) действуют в пределах одного «отростка» дерева между двумя разделительными линиями, так как положение последних по координате x фиксировано независимо от значений x у вставляе% мых узлов. Типичные операции с приоритетными деревьями поиска – вставка, удаление, поиск элемента с наименьшим (наибольшим) значением x (или y ), большим (меньшим) заданного предела, а также перечисление точек, лежащих в заданном прямоугольнике. Ниже приведены процедуры для вставки и перечисления. Они основаны на следующих объявлениях типов: TYPE Node = POINTER TO RECORD x, y: INTEGER; left, right: Node END Заметим, что необязательно хранить атрибуты x L и x R в самих узлах. Их можно вычислять каждый раз в процессе поиска. Однако для этого в рекурсивной проце% дуре insert нужны два дополнительных параметра. В первом вызове (с p = root ) их значения равны x min и x max соответственно. В остальном поиск протекает как в обычном дереве поиска. Если встречается пустой узел, то элемент вставляется. Если у вставляемого узла значение y меньше, чем у проверяемого в данный мо% мент, новый узел меняется местами с проверяемым. Наконец, узел вставляется в левое поддерево, если его значение x меньше, чем среднее значение интервала, и в правое поддерево в противном случае. PROCEDURE insert (VAR p: Node; X, Y, xL, xR: INTEGER); VAR xm, t: INTEGER; (* ADruS48_PrioritySearchTrees *) BEGIN IF p = NIL THEN (* , *) NEW(p); p.x := X; p.y := Y; p.left := NIL; p.right := NIL ELSIF p.x = X THEN (* ; *) ELSE IF p.y > Y THEN t := p.x; p.x := X; X := t; t := p.y; p.y := Y; Y := t END; xm := (xL + xR) DIV 2; IF X < xm THEN insert(p.left, X, Y, xL, xm) Приоритетные деревья поиска Динамические структуры данных 250 ELSE insert(p.right, X, Y, xm, xR) END END END insert Задача перечисления всех точек x , y , лежащих в заданном прямоугольнике, то есть удовлетворяющих условиям x0 ≤ x < x1 y ≤ y1 , решается с помощью приво% димой ниже процедуры enumerate . Она вызывает процедуру report(x,y) для каж% дой найденной точки. Заметим, что одна сторона прямоугольника лежит на оси, то есть нижняя граница для y равна 0. Этим гарантируется, что перечисление тре% бует не более O(log(N) + s) операций, где N – мощность пространства поиска по x , а s – число перечисляемых узлов. PROCEDURE enumerate (p: Ptr; x0, x1, y1, xL, xR: INTEGER); VAR xm: INTEGER; (* ADruS48_PrioritySearchTrees *) BEGIN IF p # NIL THEN IF (p.y <= y1) & (x0 <= p.x) & (p.x < x1) THEN report(p.x, p.y) END; xm := (xL + xR) DIV 2; IF x0 < xm THEN enumerate(p.left, x0, x1, y1, xL, xm) END; IF xm < x1 THEN enumerate(p.right, x0, x1, y1, xm, xR) END END END enumerate Упражнения 4.1. Введем понятие рекурсивного типа, объявляемого следующим образом: RECTYPE T = T0 и обозначающего множество значений, определенное типом T0 и расширен% ное единственным значением NONE . Например, определение типа person можно тогда упростить до RECTYPE person = RECORD name: Name; father, mother: person END Какова схема организации памяти для рекурсивной структуры, соответству% ющей рис. 4.2? Надо полагать, реализация такого средства должна основы% ваться на динамической схеме распределения памяти, и поля father и mother в приведенном примере должны содержать указатели, порождаемые автома% тически, но недоступные программисту. Какие трудности возникнут при реа% лизации такой схемы? 4.2. Определите структуру данных, описанную в последнем абзаце раздела 4.2, в терминах записей и указателей. Можно ли представить такую семейную груп% пу с помощью рекурсивных типов, предложенных в предыдущем упражнении? 251 4.3. Предположим, что очередь Q , устроенная по принципу «первый вошел – пер% вый вышел» (first%in%first%out = fifo), с элементами типа T0 реализована как связный список. Напишите модуль с подходящей структурой данных, проце% дурами для вставки и извлечения элемента из Q , а также функцию проверки, пуста очередь или нет. Процедуры должны иметь собственный механизм, обеспечивающий экономное использование памяти. 4.4. Предположим, что записи в связном списке имеют поле ключа типа INTEGER Напишите программу сортировки списка по возрастанию ключа. Затем пост% ройте процедуру обращения списка. 4.5. Для организации циклических списков (см. рис. 4.52) обычно используют та% к называемый заголовок списка. Зачем вводят такой заголовок? Напишите процедуры вставки, удаления и поиска элемента по заданному ключу. Сде% лайте это один раз, предполагая наличие заголовка, и другой раз при его от% сутствии. Рис. 4.52. Циклический список 4.6. Двунаправленный список – это список элементов, связанных в обоих направ% лениях (см. рис. 4.53). Обе цепочки ссылок начинаются в заголовке. Как и в предыдущем упражнении, постройте модуль с процедурами для поиска, вставки и удаления элементов. Рис. 4.53. Двунаправленный список 4.7. Будет ли правильно работать представленная программа топологической сортировки, если некоторая пара встречается во входных данных более одного раза? Упражнения Динамические структуры данных 252 4.8. В программе топологической сортировки сообщение " - " во многих случаях не слишком полезно. Усовер% шенствуйте программу так, чтобы она выдавала последовательность тех элементов, которые образуют цикл, если такая существует. 4.9. Напишите программу, которая читает программный текст, находит все определения и вызовы процедур и пытается топологически отсортировать процедуры. Пусть P 〈 Q означает, что процедура P вызывается процедурой Q 4.10. Нарисуйте дерево, построенное приведенной программой построения идеально сбалансированного дерева, если входные данные – натуральные числа 1, 2, 3, ... , n 4.11. Какие последовательности узлов получатся при обходе дерева на рис. 4.23 в прямом, центрированном и обратном порядке? 4.12. Найдите правило построения таких последовательностей n чисел, при пода% че которых на вход простейшей программе поиска и вставки (раздел 4.4.3) получались бы идеально сбалансированные деревья. 4.13. Рассмотрим следующие два порядка обхода двоичных деревьев: a1. Обойти правое поддерево. a2. Посетить корень. a3. Обойти левое поддерево. b1. Посетить корень. b2. Обойти правое поддерево. b3. Обойти левое поддерево. Есть ли какие%нибудь простые связи между последовательностями узлов, получающимися в этих двух случаях, и последовательностями, порождае% мыми тремя отношениями порядка, определенными в тексте? 4.14. Определите структуру данных для представления n %арных деревьев. Затем напишите процедуру, которая обходит n %арное дерево и порождает двоич% ное дерево, содержащее те же элементы. Предположите, что каждый ключ, хранимый в элементе, занимает k слов, а каждый указатель – одно слово оперативной памяти. Каков выигрыш по требуемой памяти при использова% нии двоичного дерева вместо n %арного? 4.15. Пусть дерево строится в соответствии с приводимым ниже определением рекурсивной структуры данных (см. упр. 4.1). Напишите процедуру поиска элемента с заданным ключом x и применения к этому элементу операции P : RECTYPE Tree = RECORD x: INTEGER; left, right: Tree END 4.16. В некоторой файловой системе директория всех файлов организована как упорядоченное двоичное дерево. Каждый узел соответствует файлу и хра% нит имя этого файла и, среди прочего, дату последнего обращения к нему, закодированную как целое. Напишите программу, которая обходит это де% рево и стирает все файлы, последнее обращение к которым произошло до некоторой даты. 253 4.17. В некоторой древесной структуре для каждого элемента эмпирически изме% ряется частота обращений, которая хранится в виде счетчика в соответству% ющем узле. В определенные моменты времени производится реорганизация дерева: выполняется обход дерева и строится новое дерево с помощью про% цедуры простого поиска и вставки, причем ключи вставляются в порядке уменьшающихся значений числа обращений. Напишите программу для вы% полнения такой реорганизации. Будет ли средняя длина пути в этом дереве равна, хуже или намного хуже, чем для оптимального дерева? 4.18. Описанный в разделе 4.5 метод анализа алгоритма вставки в дерево можно также использовать для вычисления среднего числа сравнений C n и средне% го числа пересылок (обменов) M n , которые делает алгоритм быстрой сорти% ровки при сортировке n элементов массива, предполагая равную вероят% ность всех n! перестановок n ключей 1, 2, ... n . Постройте соответствующее рассуждение и определите C n и M n 4.19. Нарисуйте сбалансированное дерево с 12 узлами, высота которого мини% мальна среди всех сбалансированных деревьев с 12 узлами. В какой последовательности должны вставляться узлы, чтобы процедура АВЛ%вста% вок порождала это дерево? 4.20. Найдите такую последовательность n ключей для вставки, чтобы процедура вставки в АВЛ%дерево выполнила каждый из четырех действий баланси% ровки ( LL , LR , RR , RL ) хотя бы один раз. Какова минимальная длина n такой последовательности? 4.21. Найдите сбалансированное дерево с ключами 1 ... n и перестановку этих ключей – такую, чтобы при подаче ее на вход процедуре удаления для АВЛ% деревьев каждая из четырех операций балансировки выполнилась хотя бы один раз. Найти такую последовательность минимальной длины. 4.22. Какова средняя длина пути дерева Фибоначчи T n ? 4.23. Напишите программу, которая порождает почти оптимальное дерево в соот% ветствии с алгоритмом, основанном на выборе центроида в качестве корня. 4.24. Пусть ключи 1, 2, 3, ... вставляются в пустое Б%дерево порядка 2. Какие ключи будут вызывать разбиения страниц? Какие ключи вызывают увели% чение высоты дерева? Если ключи стираются в том же порядке, какие клю% чи вызывают слияние страниц (и освобождение памяти) и какие ключи вызывают уменьшение высоты? Ответьте на вопрос (a) для схемы удале% ния, использующей балансировку, и (b) для схемы без балансировки (ког% да страница становится пустой, с соседней страницы забирается един% ственный элемент). 4.25. Напишите программу для поиска, вставки и удаления ключей из двоичного Б%дерева. Используйте тип узла и схему вставки для двоичного Б%дерева, показанную выше. 4.26. Найдите последовательность вставки ключей в пустое симметричное двоич% ное Б%дерево, которая заставляет представленную процедуру вставки вы% полнить все четыре операции балансировки (LL, LR, RR, RL) хотя бы по одному разу. Найдите кратчайшую такую последовательность. Упражнения Рекурсивные алгоритмы 254 4.27. Напишите процедуру удаления элементов для симметричного двоичного Б%дерева. Затем найдите дерево и короткую последовательность удалений – такие, чтобы все четыре ситуации, требующие балансировки, возникали хотя бы по разу. 4.28. Определите структуру данных и напишите процедуры вставки и удаления элемента для приоритетного дерева поиска. Процедуры должны обеспечи% вать сохранение указанных инвариантов. Сравните их производительность с приоритетными деревьями поиска по остаткам. 4.29. Спроектируйте модуль со следующими процедурами для работы с приори% тетными деревьями поиска по остаткам: – Вставить точку с координатами x, y – Перечислить все точки в заданном прямоугольнике. – Найти точку с наименьшей координатой x в заданном прямоугольнике. – Найти точку с наибольшей координатой y внутри заданного прямоуголь% ника. – Перечислить все точки, лежащие внутри двух (пересекающихся) прямо% угольников. Литература [4.1] Адельсон%Вельский Г. М., Ландис Е. М. Один алгоритм организации ин% формации // Доклады АН СССР, 146 (1962), 263–266. [4.2] Bayer R. and McCreight E. M. Organization and Maintenance of Large Ordered Indexes. Acta Informatica, 1, No. 3 (1972), 173–189. [4.3] Bayer R. and McCreight E. M. Binary B%trees for Virtual memory. Proc. 1971 ACM SIGFIDET Workshop, San Diego, Nov. 1971. Р. 219–235. [4.4] Bayer R. and McCreight E. M. Symmetric Binary B%trees: Data Structure and Maintenance Algorithms. Acta Informatica, 1, No. 4 (1972), 290–306. [4.5] Hu T. C. and Tucker A. C. SIAM J. Applied Math, 21, No. 4 (1971), 514–532. [4.6] Knuth D. E. Optimum Binary Search Trees. Acta Informatica, 1, No. 1 (1971), 14–25. [4.7] Walker W. A. and Gotlieb C. C. A Top%down Algorithm for Constructing Nearly Optimal Lexicographic Trees, in: Graph Theory and Computing (New York: Academic Press, 1972), Р. 303–323. [4.8] Comer D. The ubiquitous B%Tree. ACM Comp. Surveys, 11, 2 (June 1979), 121–137. [4.9] Vuillemin J. A unifying look at data structures. Comm. ACM, 23, 4 (April 1980), 229–239. [4.10] McCreight E. M. Priority search trees. SIAM J. of Comp. (May 1985). |