Лабораторная работа №6 (4 часа). Поиск по дереву с включением и исключением

Цель работы:

 - исследовать и изучить методы поиска элемента в дереве по заданному ключу со вставкой (включением) и удалением (исключением);

 - овладеть умениями и навыками написания на С++ программ поиска по дереву с включением и исключением.

Порядок выполнения работы

 - ознакомиться с краткой теорией и примерами решения задач, относящихся к поиску по дереву с включением и исключением;

 - ответить на контрольные вопросы и получить оценку по знанию теории;

 - получить задание на выполнение конкретного варианта лабораторной работы и выполнить его;

 - написать и отладить программу решения задачи на языке С++;

 - составить отчет по лабораторной работе и защитить его у преподавателя.

Содержание отчета по ЛР

- наименование ЛР и ее цель;

 - задание на ЛР согласно варианту;

 - листинг приложения, обеспечивающей успешное решение студентом полученного варианта задачи;

 - результаты работы программы.

Краткая теория

В лабораторной работе № 3 были рассмотрены основные понятия, касающиеся сбалансированных бинарных деревьев, и представлены алгоритмы создания и возможных обходов бинарных деревьев. В данной работе будут рассмотрены случаи, когда дерево уже создано и необходимо осуществить поиск элемента по ключу в уже имеющемся бинарном дереве. На практике часто может возникать необходимость вначале осуществить поиск элемента в структуре, а затем, в случае, если элемент найден, либо информировать пользователя об этом, либо удалить его. В случае, если элемент не найден, пользователя необходимо либо об этом проинформировать, либо вставить в структуру элемент с ненайденным ключом.

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

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

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

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

Алгоитмы

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

Опишем процедуру поиска в псевдокоде. Переменной search будет присваиваться указатель на найденное звено:

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 = right(p)

   endif

endwhile

search = nil

return

Включение элемента в дерево

Для включения новой записи в дерево, прежде всего, нужно найти тот узел, к которому можно "подвесить" (присоединить) новый элемент. Алгоритм поиска нужного узла тот же самый, что и при поиске узла с заданным ключом. Этот узел будет найден в тот момент, когда в качестве очередной ссылки, определяющий ветвь дерева, в которое надо продолжить поиск, окажется ссылка NIL.

Однако непосредственно использовать процедуру поиска нельзя, потому что по окончанию вычисления ее значение не фиксирует тот узел, из которого была выбрана ссылка NIL. Модифицируем описание процедуры поиска так, чтобы в качестве ее побочного эффекта фиксировалась ссылка на узел, в котором был найден заданный ключ (в случае успешного поиска), или ссылка на узел, после обработки которого, поиск прекращен (в случае неуспешного поиска).

Алгоритм поиска по бинарному дереву с включением (вставкой) в псевдокоде.

p = tree

q = nil

while 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

   Вспомогательный указатель q здесь отстает на один шаг от рабочего p.