Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 44
Текст из файла (страница 44)
р2 .Ьа!; р1,.ь1Е1ьь ь= р2",,1еХс; р21.1«17;= р11 р,",7«1«:= р2",.«1ЗЬЬ; р2Ь~.ьь''1ьь к= рь 1Г И =- — 1 кЪеп рТ,Ьа1: = +1 е1аер ь.Ьа1 ь= О; М Ь2 = +1 КЪеп р1Ь,Ьа1 ь= -1 е1аер11.Ьа1;= О; р:= р2; р2;.Ьа1:=- О епй епй епй епй 1Ьа1апсе23; ркосейаге «7е1(как ть те1; как Ь; Ьоо1еаи); Ъерп ~Ь =- 3а1~е) 11 т"Ь.тьеььк че пИ 1Ъеп Ъерп «7ефф.щ1ьОЬ); 11 Ь 1Ъеп Ьа1аььсе2(т, Ь) епй е1ае Ъерп ф~.7сеу ь= «, 7«еу; дЬ.свинь: «1.соип11 т:= «1.1«7'ь; Ь:= 1«ие ° й епй; Ъейьп 7ь7е1«ье) ьТр =-.
пП!Ъеп Ъерп ьи!ье!п Окет ьь кот ььь тйее)1 Ь 4=,Й7ав епй е1ае 26ч 4. Динамические инфор.иаиионнме структуры И х ( р)Лсеуйеп Ьея)п йе!его(х,р1ЛеЯД; 11 й 1Ьеп Ьа!ансе1 (р, Б» епй е)ае 11 х > р1./сеу йеп Ьея)п Ие1еге(х,р~.гуйййй)1 И й йеп Ьа1апсе2(р,й) епй е)ае Ьейй (уйаление р1 ) а:- р; Е д~,щ1м пИ йеп Ьей)п р:= й~Ле~~; й:== геле епй е)ае (4.64) Ы дТЛеу) = пИ йеп ЬеРп р:- с1~ж1йЫ; 1г:=-. 1гие епй е)ае Ьейап Ие)(д') ЛеЯ Я; 12 й йеп Ьа1алсе1(р„й) евй; (6Ьраее(1)» епй епй (йе1еге» Очевидно, что удаление элемента в сбалансированном дереве может также быть выполнено за (в худшем случае) 0(!она) шагов, Тем не менее не следует упускать нз виду существенную разницу в выполнении процедур включения и удаления.
В то время как включение одного ключа может вызнать самое большее один поворот (двух или трех узлов), удаление может потребовать поворота в каждом узле вдоль пути поиска. Рассмотрим, например, удаление самого правого узла в дереве Фибоначчи. Удаление любого узла в дереве Фибоначчи вызывает уменьшение его высоты, а удаление само~о правого узла требует максимального числа поворотов. Таким образом, мы получилп самое неудачное сочетание: наихудший выбор узла в наиболее плохом варианте сбалансированного дерева! Но насколько вообще вероятны поворотыр Удивительный результат эмпирических проверок показал, что в то время как один поворот вызывается приблизительно каждыми двумя включениями, тем не менее при удалении мы имеем дело с одним поворотом на целых пять удалений.
Поэтому удаление из сбалансированного дерева примерно так же просто — илн так же трудно, — как и включение. 4А.т. Оптимальные деревья поиска До сих пор в наших рассуждениях об организации деревьев поиска мы исходили из предположения, что частота обращения ко всем узлам одинакова, т. е, что все ключи 4.4. Древовидные структуры а61 с равной вероятностью становятся аргументами поиска. Повидимому, это — наилучшее допущение, если нет сведений о рсспредгяснии частоты обращений.
Но существуют случаи (скорее исключение, чем правило), когда имеется ннформа. цпя о вероятности обращений к отдельным ключам. Длн таких случаев обычно характерно, что ключи остаются постоянными, т. с. дерево поиска не подвергается ни включениям, нн удалениям, а сохраняет постоянную структуру. Типичным примером служит сканер транслятора, который для каждого слова (ндентификатора) определяет, является ли оно [а) 66 (с) Рй Рис. 4.36. Деревья понска с тремя узлами. (е) зарезервированным (ключевым) словом, Статистические измерения, проведенные па сотнях транслируемых программ, могут в этом случае дать точные сведении о частоте появления отдельных ключей и, следовательно, о вероятности обращения к ним.
Йредположим, что р, — вероятность обращения к узлу г в дереве поиска: Рг (х= й,) = р„',г',р, = 1. (4.65) Теперь мы хотим организовать дерево поиска так, чтобы Обгцее число (1(агов пбиска, подсчитанное для достаточно большого количества опыФов, было минимальным. Для этого припшцем каждому узлу в определении длины пути (4.34) некоторый вес. Узлы, к которым часто обрагцаются, считаются тяжелыми, а посев(аемыс редко — легкими. Тогда взвешеннии Олггнв пути есть сумма всех путей от корня к каждому узлу, умноженных на вероятность обращения к этому узлу: Р, =- )' ргй„ (4.66) Е й,— уровень узла 1 (или его расстояние от корня +1). Наша цель — мггнимизировать взвешенную длину пути для даннпго распределения вероятностей. 4. Динатеинеские иефораакионные структуры В качестве примера рассмотрим множестно ключей 1, 2, 3 с вероятностями обращения р, = 1/7, р, = 2/7 и Ре = 4/7, Эти три ключа можно расположить в виде деревьев поиска пятью различными способами (см.
рис, 4.36), Взвешенные длины пути этих деревьев вычисляются в со. ответствии с (4.66): Р',и=- — (1 3+ 2 2+ 4 1)= —, Яме) = ~ (1 ° 2+ 2 ° 3+ 4 ° Ц=ф, Р(с~= — (1 ° 2+2 ° ! +4 2)=- 1З, 7 Р',е~= — (1. 1+2 3+4 2) = т РМ=-'(1 1+2 2+4 3)= — ". Итак, в этом примере оптимальным оказывается не идеально сбалансированное дерево, а вырожденное, Пример сканера в трансляторе сразу наводит на мысль, что эту проблему следует рассматривать при несколько более общем условии: слова, встречающиеся в исходном тексте, пе всегда явля|отся зарезервированными словами; в действительности это скорее исключение, чем правило. Выяснение того, что данное слово не является ключом в дереве поиска, можно рассматривать как обращение к гипотетическому «специальному узлу», вставленному между меньшим и большим ключами (см.
рис. 4.19) и имеющему соответствующую длину внешнего пУти. Если известна также веРовтность с1е того, что аргумент поиска х лежит между двумя ключами Ф; и й,, то это может существенно повлиять на структуру оптимального дерева поиска. Поэтому мы обобщим задачу, учитывая и неудачные поиски. Общая взвешенная длина имеет теперь следующий внии « Ш Р= БРА+ Хе(А' (4.67) ! т=е где Х Ре + Цс/1 = 1 К вЂ” уровень внутреннего узла е', Ь' — уровень внешнего узла 1.
Среднюю взвешенную длину пути можно назвать «ценойа дерева поиска, так как она является мерой ожидаемого количества затрат на поиск. Дерево поиска, структура которого дает мпщтмальную цену для всех деревьев с заданным мпо- 4.4. Древовидные структуры 263 жсством ключей а; и вероятностями р; и а! обращений, называется оптимальным деревом.
цля нахождения оптимального дерева нс обязательно, ччобы сумма всех р и д равнялась 1. На самом деле значений вероятностей обычно находятся с помощью экспериментов, в которых подсчитываются обращешгя к узлам. Вместо ве роятностей р; и д, мы в дальнейшем будем использовать показа шли частоты обращений, которые обозначим как а, = число поисков с аргументом х, равным йо 'э, = число поисков, когда аргумент х лежит между а, и вм По соглашению Ьо есть число поисков, когда х меньше йь а о,— частота поисков, когда х больше йв (см рис.
4.37), Ряс. 4.37. Дерево поиска с указанием частоты оаращскпк В дальнейшем мы будем через Р обозначать общую взвешец Ную длину пути вместо средней длины пути: в л Р = 4'„а,тт, + ~, 1т Ь'р (4.68) т!так, благодаря использованию э тпернментально измеренных частот мы не только избавились от необходимости вь„тис лять вероятность, но и получили возмо: ость иметь дело только с целыми числами при нашем поиске оптнмальцого дер:ва. Если учесть, что число возможных конфигураций из и узлов растет экспоценциально вместе с и, задача нахожденця оптимума прн больших и кажешься совершенно безнадежной, Однако оптимальные деревья имеют одно важное свойство, которое помогает нх находить: все их поддеревья тоже являкмся оптимальными, Например, если дерево на рцс 437 опта малько для данных а и Ь, то поддерево с ключами ьз 4.
Данама«еское ннсрарначианные структуры и йн как известно, также оптимально. Эта особенность предполагает алгоритм, который систематически находит все большие и ббльшие деревья, начиная с отдельных узлов как наименьших возможных поддеревьев. Таким образом, дерево растет «от листьев к корню», что является, поскольку мы привыклн рисовать деревья сверху вниз, направлением «снизу вверхе [4.61. Основой нашего алгоритма служит уравнение (4.69). Пусть Р— взвешенная длина пути дерева, а Р, и Рн — взвешенные длины левого и правого поддеревьев его корня. Понятно, что Р— это сумма Р» Рн и числа случаев, когда поп к проходит по единственному пути к корню, что является просто общим числом Ж' случаев поиска.
Р=Рт + йр+Рр и н )Р' = ~„а, + ~, Ь . (4.70) (4.69) Мы называем Ю' весом дерева. Тогда его средняя длина пуни будет Р/'йу. Из этих рассуждений видно, что необходимо обозначит, веса и длины пути поддеревьев, состоящих из какого-то числа ключей. Пусть юн обозначает вес, а ри — длину пути оптпмальнвго поддерева Ти, состоящего из узлов с ключамн Ьньь йское, ..., Ар Эти величины определяются рекуррентными соотношениями (4.71) н (4.72); жа — — Ь, (О < с < а), (4.71) юг — — шь ~,+а,+Ь! (О~~с <) ~~и), Ри == нЭ~ (О <с «~и), (4,72) Ры — — шн+ пнн (Ран, + рнг) (О ='с </<в).
!(н~г Последнее равенство непосредственно следует из (4.69) и определения оптимальности. Поскольку существует приблизительно (1/2)нз значений рп и так как (4.72) требует выбора среди 0 < 1 — с < л значений, поиск минимума займет приблизительно (1/6)тсз операций. Кнут показал, что при помощи следующих рассуждений можно избавиться от множители и и таким образом сохранить практическую ценность этого алгоритма.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
