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