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

Поиск со вставкой (с включением)


Для вставки элемента в дерево, сначало нужно осуществить поиск в дереве по заданному ключу. Если такой ключ имеется, то программа завершается, если нет, то происходит вставка.

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



Содержание раздела