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

Поиск по бинарному дереву

Назначение его в том, чтобы по заданному ключу осу­ществить поиск узла дерева. Длительность операции зависит от структуры дерева. Действительно, дерево может быть вы­рождено в однонаправленный список, как правое на рис27.

рис. 27 – поиск по бинарному дереву

В этом случае время поиска будет такое же, как и в од­нонаправленном списке, т.е. придется перебирать N/2 эле­ментов.

Наибольшего эффекта использования дерева достигается в том случае, когда дерево сбалансировано.В этом случае для поиска придотся перебрать не больше hg₂N элементов.

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

Поиск элемента в бинарном дереве называется бинар­ным поиском по дереву.

Такое дерево называют деревом бинарного поиска.

Суть поиска заключается в следующем. Анализируем вершину очередного поддерева. Если ключ меньше инфор-

мационного поля вершины, то анализируем левое поддерево, больше - правое. Пусть задан аргумент key p = tree

whlie p <> nil do if key = k(p) then search = p return endif

if key <k(p)then p = left(p)

else p = righl(p)

endif endwhile search = nil return

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

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

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

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

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

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

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

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

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

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

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

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

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

рис. 28 - Удаление узлов дерева

На узел 13 в конечном итоге должен указывать v, а ука­затель s - на пустое место (как показано на рис, 5.9).