JceylT] := type-; кеу[2Щ := until; j(ey[29] := var-; key[30] := -while-;

with-; for i := 1 to 77 do

begin a\i] 0; b[i] := 0

end ;

b[0] 0; /г2 :== kJn;

.ftpocMomp входного текста и определение а и b] vyjiile eof (input) do \tegiaread(ch);

if сЛ in IA.. Z] then begin [идентификатор или служебное слово] kl : 0; Ш . repeat if kl < kin then begin kl kl+l; buf[kl] := cA

end ; read(ch)

until -icA in [A.. Z, 0.. 9]); if kl >: k2 then A:2 := A:l else repeat ; ;c2 := 2-1

until 2 = 1; pack(buf,l,id); i := l;j := щ repeat k := (f+j) div 2;

itkeylk] <. then г := A:+l; if key[k] > jrfthen / :== fc-l; until i > j;

i{key[k] = id then a[k] :== o[A:] + 1 else begin к := (i+j) div 2; end else

if cA = then

repeat read(ch) until ch - else if ch - { then

repeat read(ch) until cA } efid ;

Ше1п (keys and frequencies of occurrence

uma := 0; sumb ;== &[0]; fw I 1 to к do

gin suma := suma+ali\i sumb sumb+b{i\; writeh(b[i~ll a\il , кеуЩ)

teln(b[n\

writelnC - - -

writeln(sumb, шпа); [определение w изаиЪ] for / := О to и do begin w[i,i\ := Щ;

iotj := /+1 to n do w[i,j\x~ [i,j~Ц + ф-j 4, end ; .

Wn7e(AVERAGE PATH LENGTH OF BALANCED TREE= );

writeln(baltree(0,n)/w[0,n]:6:3); printtree; opttree;

WnVe(AVERAGE PATH LENGTH OF OPTIMAL TREE= );

writeln(p[0,nyyф,n]-.6:3); printtree; [uccvie&emnue/ibKo служебттбгхгглов, установив & = 0) for i := 0 to и do begin w[i,q := 0;

for / := j+1 to Й do xiiij] := w[ij-l] + ф] end ; opttree;

WritelhdoPTMAL TREE CONSIDERING KEYS ONLY);

prmttree end

Программа 4.6. Построение оптимального дерева поиска.

На третьем этапе вызывается процедура opttree, которая строит оптимальное дерево поиска; затем последнее изображается. И наконец, те же процедуры используются для построения и изображения оптимального дерева с учетом лишь частот обращений к ытючам.

В табл. 4.5 и на рис. 4.40-4.42 приведены результаты, полученные программой 4.6 при обработке ее собственного текста. Различия трех рисунков показывают, что сбалансированное дерево нельзя считать даже близким к оптимальному и что частоты поиска незарезервированных слов сильно влияют на выбор оптимальной структуры.

4.5. сильно ветвящиеся деревья

До сих пор мы ограничивали наши рассуждения деревьЯ' мн, в которых каждый узел имеет самое большее двух потомков, т. е. бинарными деревьями. Этого вполне достаточН. если, например, мы хотим представить родственные отноше ния с предпочтением восходящей линии , т. е. когда д' каждого человека указываются его родители..В конце конн ни у кого не бывает более двух родителей. Но как быть tow

предпочитает изображать нисходящую линию ? Ему при- сЯ столкнуться с тем фактом, что некоторые люди имеют ее двух детей, поэтому его деревья будут содержать узлы многими ветвями. За неимением лучшего термина мы бу-V называть их сильно ветвящимися деревьями. разумеется, в таких структурах нет ничего необычного, J уже встречали все средства программирования и описания

------------------ --- --- --------------- -------

ддыл, нужные для того, чтобы справиться с такими ситуа-йЯМИ- Если, например, задана абсолютная верхняя граница одичества детей (что, по-видимому, является неким футури-лческим предположением), то можно представить детей виде компоненты-массива в записи, представляющей чело-

,ga. Но если число детей у разных людей сильно варьируется, то это может привести к неэкономному расходу памяти. В этом случае намного правильнее расположить потом-в виде линейного списка со ссылкой в записи родителей на самого младшего (или самого старшего) отпрыска. Возможное описание типа для такого случая показано в (4.80),

возможная структура данных приведена на рис. 4.43.

iyjjeperson ~ record name; alfa; sibling; liperson; (4.80)

I offspring; \ per son

Мы замечаем, что при повороте этого рисунка на 45° он будет выглядеть как идеальное бинарное дерево*). Но это неверная точка зрения, поскольку функционально эти две ссылки имеют совершенно различное значение. Обычно нельзя обращаться с братом, как с сыном, поэтому так не следует поступать даже при описании данных. Этот пример легко можно было бы распространить и на более сложные структуры данных, включив еще какие-то компоненты в запись для каждого лица; таким образом можно было бы изображать другие родственные связи. Одна из таких связей, которую №льзя в принципе вывести из отношений братства и потомства,- это связь между мужем и женой или обратное отно-11ение отцовства и материнства. Такая структура быстро разрастается в сложный, реляционный банк данных , который ожет отображаться в несколько деревьев. Алгоритмы, рабо-ающие с такими структурами, тесно связаны с их описа- иями; поэтому не имеет смысла определять для них какие- йбо общие правила или методы работы.

Однако имеется практически очень важная область при- Нения сильно ветвящихся деревьев, которая представляет

. *) О бинарности скорее, свидетельствует наличие двух ссылок. - Прим.