9.4.7. Вспомогательные алгоритмы для дерева сортировки

Алгоритмы трех предыдущих разделов используют вспомогательные функции, описанные здесь.

1. Поиск узла — функция Find.

Вход: дерево сортировки Т, заданное указателем на корень; ключ а.

Выход: р — указатель на найденный узел или nil, если в дереве нет такого ключа; q — указатель на отца узла р; s — способ подцепления узла q к узлу р (s = -1, если р слева от q; s = +1, если р справа от q; s = 0, если р — корень).

p: = T;q: = nil; s: = 0 { инициализация }

while p  nil do

if p.i = a then

return p, q, s

end if

q: = p { сохранение значения р }

if a < p.i then

p: = p.l; s : = - 1 { поиск слева }

else

p: =p.r; s : = +1 { поиск справа }

end if

end while

ОТСТУПЛЕНИЕ

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

2. Удаление узла - процедура Delete.

Вход: р1 — указатель на удаляемый узел; р2 — указатель на подцепляющий узел; рЗ —

указатель на подцепляемый узел; s — способ подцепления.

Выход: преобразованное дерево.

if s = -1 then

p2.l : =рЗ { подцепляем слева }

end if

if s = +1 then

p2.r : = рЗ { подцепляем справа }

end if

dispose(p1) { удаляем узел }

3. Создание нового узла — конструктор NewNode.

Вход: ключ а.

Выход: указатель р на созданный узел.

new(p);p.i: = a;p.l:=nil; p.r : = nil

return p