Поиск со вставкой (с включением)
Для вставки элемента в дерево, сначало нужно осуществить поиск в дереве по заданному ключу. Если такой ключ имеется, то программа завершается, если нет, то происходит вставка.
Для включения новой записи в дерево, прежде всего нужно найти тот узел, к которому можно присоединить новый элемент. Алгоритм поиска нужного узла тот же самый, что и при поиске узла с заданным ключом. Однако непосредственно использовать процедуру поиска нельзя, потому что по ее окончании не фиксирует тот узел, из которого была выбрана ссылка 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; |
