Алгоритмы и структуры данныхНовая версия для Оберона cdмосква, 2010Никлаус ВиртПеревод с английского под редакцией
 Скачать 2.67 Mb.
|
Наш опыт с удалением из деревьев подсказывает, что и в случае сбалансиро% ванных деревьев удаление будет более сложной операцией, чем вставка. Это на самом деле так, хотя операция балансировки остается в сущности такой же, как и для вставки. В частности, здесь балансировка тоже состоит из одиночных или двойных ротаций узлов. Процедура удаления из сбалансированного дерева строится на основе алго% ритма удаления из обычного дерева. Простые случаи – концевые узлы и узлы с единственным потомком. Если удаляемый узел имеет два поддерева, мы снова будет заменять его самым правым узлом его левого поддерева. Как и в случае вставки, добавляется булевский параметр%переменная h со значением v . Необходимость в балансировке может возникнуть, только если h истинно. Это случается при обнаружении и удалении узла, или если сама балансировка уменьшает высоту поддерева. Здесь мы введем две процедуры для (симметричных) операций балансировки, так как их нужно вызывать из более чем одной точки алгоритма удаления. Заметим, что процедуры balanceL или balanceR вызываются после того, как уменьшилась высота левой или правой вет% ви соответственно. Работа процедуры проиллюстрирована на рис. 4.35. Если дано сбалансирован% ное дерево (a), то последовательное удаление узлов с ключами 4, 8, 6, 5, 2, 1, и 7 приводит к деревьям (b)...(h). Удаление ключа 4 само по себе просто, так как соот% ветствующий узел концевой. Но это приводит к несбалансированному узлу 3. Его балансировка требует одиночной LL%ротации. Балансировка опять нужна после удаления узла 6. На этот раз правое поддерево для корня (7) балансируется оди% ночной RR%ротацией. Удаление узла 2, само по себе бесхитростное, так как узел имеет лишь одного потомка, требует применения сложной двойной RL%ротации. Наконец, четвертый случай, двойная LR%ротация, вызывается после удаления 217 узла 7, который сначала замещается крайним правым элементом своего левого поддерева, то есть узлом 3. PROCEDURE balanceL (VAR p: Node; VAR h: BOOLEAN); (*ADruS45_AVL*) VAR p1, p2: Node; BEGIN (*h; v *) IF p.bal = –1 THEN p.bal := 0 Рис. 4.35. Удаления из сбалансированного дерева Сбалансированные деревья Динамические структуры данных 218 ELSIF p.bal = 0 THEN p.bal := 1; h := FALSE ELSE (*bal = 1, *) p1 := p.right; IF p1.bal >= 0 THEN (* RR– *) p.right := p1.left; p1.left := p; IF p1.bal = 0 THEN p.bal := 1; p1.bal := –1; h := FALSE ELSE p.bal := 0; p1.bal := 0 END; p := p1 ELSE (* RL– *) p2 := p1.left; p1.left := p2.right; p2.right := p1; p.right := p2.left; p2.left := p; IF p2.bal = +1 THEN p.bal := –1 ELSE p.bal := 0 END; IF p2.bal = –1 THEN p1.bal := 1 ELSE p1.bal := 0 END; p := p2; p2.bal := 0 END END END balanceL; PROCEDURE balanceR (VAR p: Node; VAR h: BOOLEAN); VAR p1, p2: Node; BEGIN (*h; v *) IF p.bal = 1 THEN p.bal := 0 ELSIF p.bal = 0 THEN p.bal := –1; h := FALSE ELSE (*bal = –1, rebalance*) p1 := p.left; IF p1.bal <= 0 THEN (* LL– *) p.left := p1.right; p1.right := p; IF p1.bal = 0 THEN p.bal := –1; p1.bal := 1; h := FALSE ELSE p.bal := 0; p1.bal := 0 END; p := p1 ELSE (* LR– *) p2 := p1.right; p1.right := p2.left; p2.left := p1; p.left := p2.right; p2.right := p; IF p2.bal = –1 THEN p.bal := 1 ELSE p.bal := 0 END; IF p2.bal = +1 THEN p1.bal := –1 ELSE p1.bal := 0 END; p := p2; p2.bal := 0 END END END balanceR; PROCEDURE delete (x: INTEGER; VAR p: Node; VAR h: BOOLEAN); VAR q: Node; PROCEDURE del (VAR r: Node; VAR h: BOOLEAN); BEGIN 219 (*h*) IF r.right # NIL THEN del(r.right, h); IF h THEN balanceR(r, h) END ELSE q.key := r.key; q.count := r.count; q := r; r := r.left; h := TRUE END END del; BEGIN (*h*) IF p = NIL THEN (* *) ELSIF p.key > x THEN delete(x, p.left, h); IF h THEN balanceL(p, h) END ELSIF p.key < x THEN delete(x, p.right, h); IF h THEN balanceR(p, h) END ELSE (* p^*) q := p; IF q.right = NIL THEN p := q.left; h := TRUE ELSIF q.left = NIL THEN p := q.right; h := TRUE ELSE del(q.left, h); IF h THEN balanceL(p, h) END END END END delete К счастью, удаление элемента из сбалансированного дерева тоже может быть выполнено – в худшем случае – за O(log n) операций. Однако нельзя игнориро% вать существенную разницу в поведении процедур вставки и удаления. В то время как вставка единственного ключа может потребовать самое большее одной рота% ции (двух или трех узлов), удаление может потребовать ротации в каждом узле пути поиска. Например, рассмотрим удаление крайнего правого узла дерева Фи% боначчи. В этом случае удаление любого одного узла приводит к уменьшению высоты дерева; кроме того, удаление крайнего правого узла требует максималь% ного числа ротаций. Здесь имеет место весьма неудачная комбинация – наихуд% ший выбор узла в наихудшей конфигурации сбалансированного дерева. А на% сколько вероятны ротации в общем случае? Удивительный результат эмпирических тестов состоит в том, что хотя одна ротация требуется примерно на каждые две вставки, лишь одна ротация потре% буется на пять удалений. Поэтому в сбалансированных деревьях удаление элемента является столь же легкой (или столь же трудоемкой) операцией, как и вставка. Сбалансированные деревья Динамические структуры данных 220 4.6. Оптимальные деревья поиска До сих пор наш анализ организации деревьев поиска опирался на предположение, что частота обращений ко всем узлам одинакова, то есть что все ключи с равной вероятностью могут встретиться в качестве аргумента поиска. Вероятно, это луч% шая гипотеза, если о распределении вероятностей обращений к ключам ничего не известно. Однако бывают случаи (хотя они, скорее, исключения, чем правило), когда такая информация есть. Для подобных случаев характерно, что ключи все% гда одни и те же, то есть структура дерева поиска не меняется, то есть не выпол% няются ни вставки, ни удаления. Типичный пример – лексический анализатор (сканер) компилятора, который для каждого слова (идентификатора) определя% ет, является ли оно ключевым (зарезервированным) словом. В этом случае стати% стическое исследование сотен компилируемых программ может дать точную ин% формацию об относительных частотах появления таких слов и, следовательно, обращений к ним в дереве поиска. Предположим, что в дереве поиска вероятность обращения к ключу i равна Pr {x = k i } = p i , (S S S S Si: 1 ≤ i ≤ n : p i ) = 1 Мы сейчас хотим организовать дерево поиска так, чтобы полное число шагов по% иска – для достаточно большого числа попыток – было минимальным. Для этого изменим определение длины пути, (1) приписывая каждому узлу некоторый вес и (2) считая, что корень находится на уровне 1 (а не 0), поскольку с ним связано первое сравнение на пути поиска. Узлы, к которым обращений много, становятся тяжелыми, а те, которые посещаются редко, – легкими. Тогда взвешенная длина путей (внутренних) равна сумме всех путей из корня до каждого узла, взвешен% ных с вероятностью обращения к этому узлу: P = S S S S Si: 1 ≤ i ≤ n : p i * h i h i – уровень узла i . Теперь наша цель – минимизировать взвешенную длину путей для заданного распределения вероятностей. Например, рассмотрим набор клю% чей 1, 2, 3 с вероятностями обращения p1 = 1/7 , p2 = 2/7 и p3 = 4/7 . Из этих трех ключей дерево поиска можно составить пятью разными способами (см. рис. 4.36). Из определения можно вычислить взвешенные длины путей деревьев (a)–(e): P(a) = 11/7, P(b) = 12/7, P(c) = 12/7, P(d) = 15/7, P(e) = 17/7 Рис. 4.36. Деревья поиска с 3 узлами 221 Таким образом, в этом примере оптимальным оказывается не идеально сбалан% сированное дерево (c), а вырожденное дерево (a). Пример сканера компилятора сразу наводит на мысль, что задачу нужно не% много обобщить: слова, встречающиеся в исходном тексте, не всегда являются ключевыми; на самом деле ключевые слова – скорее исключения. Обнаружение того факта, что некое слово k не является ключом в дереве поиска, можно рассма% тривать как обращение к так называемому дополнительному узлу, вставленному между ближайшими меньшим и большим ключами (см. рис. 4.19), для которого определена длина внешнего пути. Если вероятность q i того, что аргумент поиска x лежит между этими двумя ключами k i и k i+1 , тоже известна, то эта информация может существенно изменить структуру оптимального дерева поиска. Поэтому, обобщая задачу, будем учитывать также и безуспешные попытки поиска. Теперь общая взвешенная длина путей равна P = (S S S S Si: 1 ≤ i ≤ n : p i *h i ) + (S S S S Si: 1 ≤ i ≤ m : q i *h' i ) где (S S S S Si: 1 ≤ i ≤ n : p i ) + (S S S S Si: 1 ≤ i ≤ m : q i ) = 1 и где h i – уровень (внутреннего) узла i , а h' j – уровень внешнего узла j . Тогда сред% нюю взвешенную длину пути можно назвать ценой дерева поиска, поскольку она является мерой ожидаемых затрат на поиск. Дерево поиска с минимальной ценой среди всех деревьев с заданным набором ключей k i и вероятностей p i и q i называ% ется оптимальным деревом. Чтобы найти оптимальное дерево, не нужно требовать, чтобы сумма всех чисел p или q равнялась 1. На самом деле эти вероятности обычно определяются из экс% периментов, где подсчитывается число обращений к каждому узлу. В дальнейшем Рис. 4.37. Дерево поиска с частотами обращений Оптимальные деревья поиска Динамические структуры данных 222 вместо вероятностей p i и q j мы будем использовать такие счетчики и обозначать их следующим образом: a i = сколько раз агрумент поиска x был равен k i b j = сколько раз агрумент поиска x оказался между k j и k j+1 По определению, b 0 – число случаев, когда x оказался меньше k 1 , а b n – когда x был больше k n (см. рис. 4.37). В дальнейшем мы будем использовать P для обозна% чения полной взвешенной длины путей вместо средней длины пути: P = (S S S S Si: 1 ≤ i ≤ n : a i *h i ) + (S S S S Si: 1 ≤ i ≤ m : b i *h' i ) Таким образом, в дополнение к тому, что уже не нужно вычислять вероятности по измеренным частотам, получаем дополнительный бонус: при поиске оптималь% ного дерева можно работать с целыми числами вместо дробных. Учитывая, что число возможных конфигураций n узлов растет экспоненци% ально с n , задача нахождения оптимума для больших n кажется безнадежной. Од% нако оптимальные деревья обладают одним важным свойством, которое помогает в их отыскании: все их поддеревья также оптимальны. Например, если дерево на рис. 4.37 оптимально, то поддерево с ключами k 3 и k 4 также оптимально. Это свойство подсказывает алгоритм, который систематически строит все большие деревья, начиная с отдельных узлов в качестве наименьших возможных подде% ревьев. При этом дерево растет от листьев к корню, то есть, учитывая, что мы ри% суем деревья вверх ногами, в направлении снизу вверх [4.6]. Уравнение, представляющее собой ключ к этому алгоритму, выводится так. Пусть P будет взвешенной длиной путей некоторого дерева, и пусть P L и P R – соот% ветствующие длины для левого и правого поддеревьев его корня. Ясно, что P рав% на сумме P L , P R , а также количества проходов поиска по ребру, ведущему к корню, что просто равно полному числу попыток поиска W . Будем называть W весом дере% ва. Тогда его средняя длина путей равна P/W : P = P L + W + P R W = (S S S S Si: 1 ≤ i ≤ n : a i ) + (S S S S Si: 1 ≤ i ≤ m : b i ) Эти соображения показывают, что нужно как%то обозначить веса и длины пу% тей поддеревьев, состоящих из некоторого числа смежных ключей. Пусть T ij – оптимальное поддерево, состоящее из узлов с ключами k i+1 , k i+2 , ... , k j . Тогда пусть w ij обозначает вес, а p ij – длину путей поддерева T ij . Ясно, что P = p 0,n и W = w 0,n Все эти величины определяются следующими рекуррентными соотношениями: w ii = b i (0 ≤ i ≤ n) w ij = w i,j–1 + a j + b j (0 ≤ i < j ≤ n) p ii = w ii (0 ≤ i ≤ n) p ij = w ij + MIN k: i < k ≤ j : (p i,k–1 + p kj ) (0 ≤ i < j ≤ n) Последнее уравнение прямо следует из определений величины P и оптималь% ности. Так как имеется примерно n 2 /2 значений p ij , а операция минимизации в правой части требует выбора из 0 < j–i ≤ n значений, то полная минимизация потребует примерно n 3 /6 операций. Кнут указал способ сэкономить один фактор 223 n (см. ниже), и только благодаря этой экономии данный алгоритм становится ин% тересным для практических целей. Пусть r ij – то значение величины k , в котором достигается минимум p ij . Оказы% вается, поиск r ij можно ограничить гораздо меньшим интервалом, то есть умень% шить число j–i шагов вычисления. Ключевым здесь является наблюдение, что если мы нашли корень r ij оптимального поддерева T ij , то ни расширение дерева добавлением какого%нибудь узла справа, ни уменьшение дерева удалением край% него левого узла не могут сдвинуть оптимальный корень влево. Это выражается соотношением r i,j–1 ≤ r ij ≤ r i+1,j , которое ограничивает поиск решения для r ij интервалом r i,j–1 ... r i+1,j . Это приво% дит к полному числу элементарных шагов порядка n 2 Мы готовы теперь построить алгоритм оптимизации в деталях. Вспомним следующие определения для оптимальных деревьев T ij , состоящих из узлов с клю% чами k i+1 ... k j : 1. a i : частота поиска ключа k i 2. b j : частота случаев, когда аргумент поиска x оказывается между k j и k j+1 3. w ij : вес T ij 4. p ij : взвешенная длина путей поддерева T ij 5. r ij : индекс корня поддерева T ij Объявим следующие массивы: a: ARRAY n+1 OF INTEGER; (*a[0] *) b: ARRAY n+1 OF INTEGER; p,w,r: ARRAY n+1, n+1 OF INTEGER; Предположим, что веса w ij вычислены из a и b простейшим способом. Будем счи% тать w аргументом процедуры OptTree , которую нужно разработать, а r – ее резуль% татом, так как r полностью описывает структуру де% рева. Массив p можно считать промежуточным результатом. Начиная с наименьших возможных деревьев, то есть вообще не имеющих узлов, мы пере% ходим ко все большим деревьям. Обозначим ширину j–i поддерева T ij как h . Тогда можно легко определить значения p ii для всех деревьев с h = 0 в соответствии с определением величин p ij : FOR i := 0 TO n DO p[i,i] := b[i] END В случае h = 1 речь идет о деревьях с одним узлом, который, очевидно, и является корнем (см. рис. 4.38): FOR i := 0 TO n–1 DO j := i+1; p[i,j] := w[i,j] + p[i,i] + p[j,j]; r[i,j] := j END Рис. 4.38. Оптимальное дерево поиска с единственным узлом Оптимальные деревья поиска Динамические структуры данных 224 Заметим, что i и j обозначают левый и правый пределы значений индекса в рас% сматриваемом дереве T ij . Для случаев h > 1 используем цикл с h от 2 до n , причем случай h = n соответствует всему дереву T 0,n . В каждом случае минимальная дли% на путей p ij и соответствующий индекс корня r ij определяются простым циклом, в котором индекс k пробегает интервал для r ij : FOR h := 2 TO n DO FOR i := 0 TO n–h DO j := i+h; k min = MIN k: i < k < j : (p i,k–1 + p kj ), r i,j–1 < k < r i+1,j ; p[i,j] := min + w[i,j]; r[i,j] := k END END Детали того, как уточняется предложение, набранное курсивом, можно найти в программе, приводимой ниже. Теперь средняя длина пути дерева T 0,n дается от% ношением p 0,n /w 0,n , а его корнем является узел с индексом r 0,n Опишем теперь структуру проектируемой программы. Ее двумя главными компонентами являются процедура для нахождения оптимального дерева поиска при заданном распределении весов w , а также прцедура для печати дерева при заданных индексах r . Сначала вводятся частоты a и b , а также ключи. Ключи на самом деле не нужны для вычисления структуры дерева; они просто используют% ся при распечатке дерева. После печати статистики частот программа вычисляет длину путей идеально сбалансированного дерева, заодно определяя и корни его поддеревьев. Затем печатается средняя взвешенная длина пути и распечатывает% ся само дерево. В третьей части вызывается процедура OptTree , чтобы вычислить оптималь% ное дерево поиска; затем это дерево распечатывается. Наконец, те же процедуры используются для вычисления и печати оптимального дерева с учетом частот только ключей, игнорируя частоты значений, не являющихся ключами. Все это можно суммировать так, как показано ниже, начиная с объявлений глобальных констант и переменных: CONST N = 100; (* . *) (* ADruS46_OptTree *) WordLen = 16; (* . *) VAR key: ARRAY N+1, WordLen OF CHAR; a, b: ARRAY N+1 OF INTEGER; p, w, r: ARRAY N+1, N+1 OF INTEGER; PROCEDURE BalTree (i, j: INTEGER): INTEGER; VAR k, res: INTEGER; BEGIN k := (i+j+1) DIV 2; r[i, j] := k; IF i >= j THEN res := 0 ELSE res := BalTree(i, k–1) + BalTree(k, j) + w[i, j] END; RETURN res END BalTree; 225 PROCEDURE ComputeOptTree (n: INTEGER); VAR x, min, tmp: INTEGER; i, j, k, h, m: INTEGER; BEGIN (* # : w, : p, r*) FOR i := 0 TO n DO p[i, i] := 0 END; FOR i := 0 TO n–1 DO j := i+1; p[i, j] := w[i, j]; r[i, j] := j END; FOR h := 2 TO n DO FOR i := 0 TO n–h DO j := i+h; m := r[i, j–1]; min := p[i, m–1] + p[m, j]; FOR k := m+1 TO r[i+1, j] DO tmp := p[i, k–1]; x := p[k, j] + tmp; IF x < min THEN m := k; min := x END END; p[i, j] := min + w[i, j]; r[i, j] := m END END END ComputeOptTree; PROCEDURE WriteTree (i, j, level: INTEGER); VAR k: INTEGER; (* # W*) BEGIN IF i < j THEN WriteTree(i, r[i, j]–1, level+1); FOR k := 1 TO level DO Texts.Write(W, TAB) END; Texts.WriteString(W, key[r[i, j]]); Texts.WriteLn(W); WriteTree(r[i, j], j, level+1) END END WriteTree; PROCEDURE Find (VAR S: Texts.Scanner); VAR i, j, n: INTEGER; (* # W*) BEGIN Texts.Scan(S); b[0] := SHORT(S.i); n := 0; Texts.Scan(S); (*: a, , b*) WHILE S.class = Texts.Int DO INC(n); a[n] := SHORT(S.i); Texts.Scan(S); COPY(S.s, key[n]); Texts.Scan(S); b[n] := SHORT(S.i); Texts.Scan(S) END; (* w a b*) FOR i := 0 TO n DO w[i, i] := b[i]; FOR j := i+1 TO n DO w[i, j] := w[i, j–1] + a[j] + b[j] END END; Оптимальные деревья поиска Динамические структуры данных 226 Texts.WriteString(W, " = "); Texts.WriteInt(W, w[0, n], 6); Texts.WriteLn(W); Texts.WriteString(W, " # = "); Texts.WriteInt(W, BalTree(0, n), 6); Texts.WriteLn(W); WriteTree(0, n, 0); Texts.WriteLn(W); ComputeOptTree(n); Texts.WriteString(W, " # = "); Texts.WriteInt(W, p[0, n], 6); Texts.WriteLn(W); WriteTree(0, n, 0); Texts.WriteLn(W); FOR i := 0 TO n DO w[i, i] := 0; FOR j := i+1 TO n DO w[i, j] := w[i, j–1] + a[j] END END; ComputeOptTree(n); Texts.WriteString(W, " b"); Texts.WriteLn(W); WriteTree(0, n, 0); Texts.WriteLn(W) END Find; В качестве примера рассмотрим следующие входные данные для дерева с тре% мя ключами: 20 1 Albert 10 2 Ernst 1 5 Peter 1 b 0 = 20 a 1 = 1 key 1 = Albert b 1 = 10 a 2 = 2 key 2 = Ernst b 2 = 1 a 3 = 4 key 3 = Peter b 3 = 1 Результаты работы процедуры Find показаны на рис. 4.39; видно, что структу% ры, полученные в трех случаях, могут сильно отличаться. Полный вес равен 40, длина путей сбалансированного дерева равна 78, а для оптимального дерева – 66. Рис. 4.39. Три дерева, построенные процедурой ComputeOptTree Из этого алгоритма очевидно, что затраты на определение оптимальной струк% туры имеют порядок n 2 ; к тому же и объем требуемой памяти имеет порядок n 2 Это неприемлемо для очень больших n . Поэтому весьма желательно найти более эффективные алгоритмы. Один из них был разработан Ху и Такером [4.5]; их алго% ритм требует памяти порядка O(n) и вычислительных затрат порядка O(n*log(n)) Однако в нем рассматривается только случай, когда частоты ключей равны нулю, то есть учитываются только безуспешные попытки поиска ключей. Другой алго% 227 ритм, также требующий O(n) элементов памяти и O(n*log(n)) вычислительных операций, описан Уокером и Готлибом [4.7]. Вместо поиска оптимума этот алго% ритм пытается найти почти оптимальное дерево. Поэтому его можно построить на использовании эвристик. Основная идея такова. Представим себе, что узлы (реальные и дополнительные) распределены на ли% нейной шкале и что каждому узлу приписан вес, равный соответствующей часто% те (или вероятности) обращений. Затем найдем узел, ближайший к их центру тя% жести. Этот узел называется центроидом, а его индекс равен величине (S S S S Si: 1 ≤ i ≤ n : i*a i ) + (S S S S Si: 1 ≤ i ≤ m : i*b i ) / W , округленной до ближайшего целого. Если вес всех узлов одинаков, то корень ис% комого оптимального дерева, очевидно, совпадает с центроидом. В противном случае – рассуждают авторы алгоритма – он будет в большинстве случаев на% ходиться вблизи центроида. Тогда выполняется ограниченный поиск для на% хождения локального оптимума, после чего та же процедура применяется к двум получающимся поддеревьям. Вероятность того, что корень лежит очень близко к центроиду, растет вместе с объемом дерева n . Как только поддеревья становятся достаточно малыми, оптимум для них может быть найден посредством точного алгоритма, приведенного выше. |