Лабораторная работа № 12. "ПОИСК ПО ДЕРЕВУ С ВКЛЮЧЕНИЕМ"

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

Цель работы: освоить алгоритм и метод вставки элементов бинарного дерева.


Задача работы: овладеть навыками написания программ по исследованию методов вставки элементов бинарного дерева на языке программирования ПАСКАЛЬ .


Порядок работы :

• 
  изучить описание лабораторной работы;

• 
  по заданию, данному преподавателем, разработать алгоритм программы решения задачи;

• 
  написать программу на языке ПАСКАЛЬ;

• 
  отладить программу;

• 
  решить задачу;

• 
  оформить отчет.

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

ПОИСК ПО БИНАРНОМУ ДЕРЕВУ 

Для вставки элемента в дерево сначала нужно осуществить поиск в дереве по заданному ключу. Если такой ключ имеется, то программа завершается, если нет то происходит вставка. Длительность операции поиска (число узлов, которые надо перебрать для этой цели) зависит от структуры дерева. Действительно, деревом может быть вырождено в однонаправленный список (иметь единственную ветвь) - такое дерево может возникнуть, если элементы поступали в дерево в порядке возрастания (убывания) их, ключей. В этом случае время поиска будет такое же, как и однонаправленном списке, т.е. в среднем придется перебрать N/2 элементов. Наибольший эффект использования дерева достигается в том случае, когда дерево "сбалансировано". Об этом говорит сайт https://intellect.icu . В этом случае для поиска придется перебрать не более log₂N.


ВКЛЮЧЕНИЕ ЭЛЕМЕНТА В ДЕРЕВО 

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

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

Алгоритм

Рассмотрим алгоритм вставки узла в бинарное дерево. 

Вставим узел с номером 150, тогда он станет правым сыном узла с номером 120, т.к. он является большим по значению узла с номером 120, но меньше значения узла головы дерева.

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

Q - указатель отстающий от Р на один шаг 

V - указатель на элемент, который будет вставлен в бинарное дерево .





Иллюстрация процесса вставки узла 150, в соответствии с вышеприведенным алгоритмом (красным цветом выделены новые связи в дереве).





Конечный вариант дерева после вставки :





Программа

Псевдокод Паскаль

Q=nil Q=nil

P=Tree P=Tree

While (P<>nil) do While (P<>nil) do

Q=P Begin

If key=k(P) then Q=P;

search=P If key=P^.k then

return Begin

EndIf search:=P;

If key<k(p) then="" exit;<br=""> 
P=left(P) End;

else If key

P=right(P) P:=P^.left;

EndIf else

EndWhile P:=P^.right;

V=maketree(key,rec) End;

If key<k(q) then="" v="maketree(key,rec)<br"> 
else If key<q^.k then<br=""> 
Right(Q)=V Q^.left:=V

EndIf else

search=V Q^.right:=V;

Return search:=V

Задания

Используя генератор случайных чисел сформировать бинарное дерево, состоящее из 5 элементов (предусмотреть ручной ввод элементов). Причем числа должны лежать в диапазоне от -99 до 99. Произвести поиск с вставкой элементов в соответствии со следующими вариантами заданий: 


1. Числа кратные N. 

2. Нечетные числа. 

3. Числа > N. 

4. Простые числа. 

5. Числа по выбору. 

6. Случайное число. 

7. Составные числа. 

8. Числа в интервале от X до Y. 

9. Числа, сумма цифр (по модулю) которого > N. 

10. Числа, сумма цифр (по модулю) которого < N. 

11. Числа, сумма цифр (по модулю) которого лежит в интервале от X до Y. 

12. Числа, взятые по модулю, квадратный корень которых целое число. 

где: N, X, Y - задается преподавателем.

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

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