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

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

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

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

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

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

Удаление узла не должно нарушить упорядоченности дерева. Об этом говорит сайт https://intellect.icu . Возможны три варианта:

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. 
    Если удалить корень в непустом бинарном дереве, какой элемент станет на его место ?

На этом все! Теперь вы знаете все про поиск со вставкой с включением поиск с удалением, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое поиск со вставкой с включением поиск с удалением и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Структуры данных

Из статьи мы узнали кратко, но содержательно про поиск со вставкой с включением поиск с удалением

Ответы на вопросы для самопроверки пишите в комментариях, мы проверим, или же задавайте свой вопрос по данной теме.