Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

Для включения новой записи в дерево, прежде всего нужно найти тот узел, к которому можно присоединить новый элемент. Алгоритм поиска нужного узла тот же самый, что и при поиске узла с заданным ключом. Однако непосредственно использовать процедуру поиска нельзя, потому что по ее окончании не фиксирует тот узел, из которого была выбрана ссылка NIL (search = nil).
Модифицируем описание процедуры поиска так, чтобы в качестве ее побочного эффекта фиксировалась ссылка на узел, в котором был найден заданный ключ (в случае успешного поиска), или ссылка на узел, после обработки которого поиск прекращается (в случае неуспешного поиска).

Псевдокод:
P = tree
Q = nil
Whlie p <> nil do
q = p
if key = k(p) then
search = p
return
endif
if key < k(p) then
p = left(p)
else
p = right(p)
endif
endwhile
v = maketree(key, rec)
if q = nil then
tree = v
else
if key < k(q) then
left(q) = v
else
right(q) = v
endif
endif
search = v
return
Паскаль:
p := tree;
q := nil;
whlie p <> nil do
begin
q := p;
if key = p^.k then
begin
search := p;
exit;
end;
if key < p^.k then
p := p^.left
else
p := p^.right;
end;
v := maketree(key, rec)
if q=nil then
tree:=v
else
if key < q^.k then
q^.left := v
else
q^.right := v;
search := v;

5.9  Поиск с удалением

Удаление узла не должно нарушить упорядоченности дерева. Возможны три варианта:
1) Найденный узел является листом. Тогда он просто удаляется и все.
2) Найденный узел имеет только одного сына. Тогда сын перемещается на место отца.
3) У удаляемого узла два сына. В этом случае нужно найти подходящее звено поддерева, которое можно было бы вставить на место удаляемого. Такое звено всегда существует:
— это либо самый правый элемент левого поддерева (для достижения этого звена необходимо перейти в следующую вершину по левой ветви, а затем переходить в очередные вершины только по правой ветви до тех пор, пока очередная ссылка не будет равна NIL.
— либо самый левый элемент правого поддерева (для достижения этого звена необходимо перейти в следующую вершину по правой ветви, а затем переходить в очередные вершины только по левой ветви до тех пор, пока очередная ссылка не будет равна NIL
Предшественником удаляемого узла называют самый правый узел левого поддерева (для 12 — 11). Преемником — самый левый узел правого поддерева (для 12 — 13).
Будем разрабатывать алгоритм для преемника (рис.5.9).
p — рабочий указатель;
q — отстает от р на один шаг;
v — указывает на приемника удаляемого узла;
t — отстает от v на один шаг;
s — на один шаг впереди v (указывает на левого сына или пустое место).

На узел 13 в конечном итоге должен указывать v, а указатель s — на пустое место (как  показано на рис. 5.9).

Псевдокод:

q = nil
p = tree
while (p <> nil) and (k(p) <> key) do
q = p
if key < k(p) then
p = left(p)
else
p = right(p)
endif
endwhile
if p = nil then ‘Ключ не найден’
return
endif
if left(p) = nil then  v = right(p)

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники