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

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

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

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

Удаление узла не должно нарушить упорядоченности дерева. Возможны три варианта:

1) Найденный узел является листом. Тогда он просто удаляется и все.

2) Найденный узел имеет только одного сына. Тогда сын перемещается на место отца.

3) У удаляемого узла два сына. В этом случае нужно найти подходящее звено поддерева, которое можно было бы вставить на место удаляемого. Такое звено всегда существует:

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

- либо самый левый элемент правого поддерева (для достижения этого звена необходимо перейти в следующую вершину по правой ветви, а затем переходить в очередные вершины только по левой ветви до тех пор, пока очередная ссылка не будет равна NIL

Предшественником удаляемого узла называют самый правый узел левого поддерева (для 12 - 11). Преемником - самый левый узел правого поддерева (для 12 - 13).

Будем разрабатывать алгоритм для преемника (рис.5.9).

p - рабочий указатель;

q - отстает от р на один шаг;

v - указывает на приемника удаляемого узла;

t - отстает от v на один шаг;

s - на один шаг впереди v (указывает на левого сына или пустое место).

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

На узел 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) else if right(p) = nil then v = left(p) else ‘У nod(p) - два сына’ ‘Введем два указателя (t отстает от v на 1 ‘шаг, s - опережает) t = p v = right(p) s = left(v) while s <> nil do t = v v = s s = left(v) endwhile if t <> p then ‘v не является сыном p’ left(t) = right(v) right(v) = right(p) endif left(v) = left(p) endif endif if q = nil then ‘p - корень’ tree = v else if p = left(q) then left(q) = v else right(q) = v endif endif freenode(p) return

Паскаль: q := nil; p := tree; while (p <> nil) and (p^.k <> key) do begin q := p; if key < p^.k then p := p^.left else p := p^.right; end; if p = nil then WriteLn(‘Ключ не найден’); exit; end; if p^.left = nil then v := p^.right else if p^.right = nil then v := p^.left else begin {Введем два указателя (t отстает от v на 1 шаг, s - опережает)} t := p; v := p^.right; s := v^.left; while s <> nil do begin t := v; v := s; s := v^.left; end; if t <> p then begin WriteLn(‘v не является сыном p’); t^.left := v^.right; v^.right := p^.right; end; v^.left := p^.left; end; end; if p = q^.left then q^.left := v else q^.right := v; end; dispose(p); end;

Контрольные вопросы

1. В чем состоит назначение поиска ?

2. Что такое уникальный ключ ?

3. Какая операция производится в случае отсутствия заданного ключа в списке ?

4. В чем разница между последовательным и индексно-последовательным поиском ?

5. Какой из них более эффективный и почему ?

6. Какие способы переупорядочивания таблицы вы знаете ?

7. Основные отличия метода перестановки в начало от метода транспозиции .

8. Где они будут работать быстрее, в массиве или списке ?

9. В каких списках они работают, упорядоченных или нет ?

10. В чем суть бинарного поиска?

11. Как можно обойти бинарное дерево?