ptocedme search(x: integer; var p: ref; var h: integer);

var pl,p2: ref; [begin

if p = nil tlien

begin [слова нет в дереве, вставить его] 1 new(p); И := 2; with р] do

--- begin key := х; count := 1; /e/f :== nil;

right :- nil; Jh := /яЬе; r/i := false

end end else if X < p\.key then be&nsearch(x,p].left,h);

if h Ф 0 then

if p].lh then

fV begin i l := p].left; h := 2; p].lh /a&e;

if />1. г then ; begin [LL] p].left := рЦ.right;

I - pll.right :== ;7; := /ofce; p := /71

j! end else

; if pAj-h then

; begin [LR] p2 := pi].right; pl].rh := false;

pl].right := p2].left; р2\.1ф := pi; p\.left := p2\.right; p2\.right := p; p := p2 end end else

begin h := h-\; if h Ф 0 then ij- true end end else

if x > p\.key then begin jeafc/;(x,p.ng/;/,/j);

if h Ф 0 then

if p\.rh then

begin /)1 :== p].right; h 2; p].rh := false; if /)1.гА then

begin [RR] p\.right := /Ц./е/л;

p\\.left := ;>; /Ц.-й false; p := ;j1 end else

ifp\].lh then

begin {RL} p2 := plt,/e/if; /If./A := false;

p\ \.left p2\.right; p2\.righfiJl;

p1i.right: 2. ; ti2\Jeftl pi p := /2 end

end else

begin А := А-1, if А 56 О then p\.rh := true end end else

begin p],count := p].count + 1; A :== 0 end end {search}

(4.87)

Рис. 4.БЗ. Формирование кустарниковых деревьев при последовате^

ностях включений (4.85).

евидно, что в памяти ЭВМ к каждому элементу в конце шнцов обращаются с помощью его адреса а в памяти. Сле-Шательно, поставленная задача - это в сущности задача ахождения подходящего отображения Я ключей (К) в адреса (Л).

В предыдущих разделах это отображение было реализовано в виде алгоритмов поиска по спискам и деревьям, осно-анных на различных способах их организации. Здесь мы предлагаем другой, более простой и во многих случаях очень эффективный подход. Тот факт, что он также имеет некоторые .Достатки, будет обсуждаться позже.

В этом методе используется организация данных в виде массива. Поэтому Я - это отображение, которое преобразует лючи в индексы массива, что дало термин преобразование ключей, обычно применяемый для обозначения этого приема -Ледует заметить, что нам не придется использовать какие-Ибо процедуры динамического размещения, поскольку мас-йв - одна из базовых, статических структур. Таким образом, Ст раздел несколько чужероден в главе о динамических

дерево (4) на рис. 4.53. С другой стороны, в кустар-!й'ковЬ1Х деревьях перестройка узлов будет происходить реже. ([дэгоыу сбалансированные деревья предпочтительны в тех дучаях, когда поиск ключей происходит намного чаще, чем включение (или удаление). Если это соотношение умеренное, njoHCHO предпочесть схему кустарниковых деревьев.

Очень трудно сказать, где проходит граница. Это во мно-рт(-за*исит не только от соотношения между частотой поиска I, частотой изменения структуры, но и от особенностей реализации. В частности, записи узлов могут иметь плотно упакованное представление, следовательно, обращение к полям по-фсбует выборки части слова. Во многих реализациях работа j булевскими полями [Ih, rh в случае кустарниковых деревьев) может быть более эффективной, чем с полями из трех значений (bal в случае сбалансированных деревьев).

1.6. преобразования ключа [расстановка]

Сформулируем основную задачу, к которой мы обращаемся в последнем разделе, в дополнение к задачам, демонстрирующим методы динамического размещения данных:

Задано множество S элементов, характеризующихся значениями ключей, на которых задано отношение порядка. Как организовать S, чтобы поиск элемента с заданным ключом k требовал как можно меньше затрат?