Лабораторная работа № 9. "СОРТИРОВКА С ПОМОЩЬЮ ДЕРЕВА"

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

Цель работы: исследовать и изучить методы сортировки с помощью дерева.


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


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

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

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

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

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

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

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

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

При обработке данных в ЭВМ важно знать и информационное поле элемента, и его размещение в памяти машины. Для этих целей используется сортировка . Итак, сортировка - это расположение данных в памяти в регулярном виде по их ключам. Регулярность рассматривают как возрастание значения ключа от начала к концу в массиве.

Различают следующие типы сортировок:

• 
  внутренняя сортировка - это сортировка, происходящая в оперативной памяти машины

• 
  внешняя сортировка - сортировка во внешней памяти.

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





Существует множество способов упорядочивания дерева. Рассмотрим один из них :

" Левый " сын имеет ключ меньше, чем ключ " Отца "

" Правый " сын имеет ключ больше, чем ключ " Отца "

Получили бинарное упорядоченное дерево с минимальным числом уровней.

Строго сбалансированное дерево : дерево, в котором левое и правое поддерево имеют уровни , отличающиеся не более, чем на единицу.

Рассмотрим принцип построения дерева при занесении элементов в массив :

Пусть в первоначально пустой массив заносятся последовательно поступающие элементы : 70, 60, 85, 87, 90, 45, 30, 88, 35, 20, 86 ; Т.к. это еще пустое дерево, то ссылки left и right равны nil( left - указатель на левого сына (элемент), right - указатель на правого сына (элемент)).

Четвертый из поступающих элементов 87. Об этом говорит сайт https://intellect.icu . Т.к. этот ключ больше ключа 70 ( корень ), то новая вершина должна размещаться на правой ветви дерева. Чтобы определить ее место, спускаемся по правой стрелке к очередной вершине ( с ключом 85 ), и если поступивший ключ больше 85, то новую вершину делаем правым сыном вершины с ключом 85 .





В рассмотренном примере ПРИНЦИП ПОСТРОЕНИЯ ДЕРЕВА имеет следующий вид : если поступает очередной элемент массива, то начиная с корня дерева (в зависимости от сравнения текущего элемента с очередной вершиной) идем влево или вправо от нее до тех пор, пока не найдем подходящую вершину, к которой можно подключить новую вершину с текущим ключом. В зависимости от результата сравнения ключей, новую вершину делаем левой или правой для найденной вершины.

 

Алгоритм

Для создания дерева необходимо создать в памяти элемент следующего типа :





Тип на ПАСКАЛе : 

type

pelem = ^elem;

elem = record

left : pointer;

right : pointer;

K : integer;

end;

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

В процедуре создания дерева бинарного поиска будут использованы следующие указатели :

tree - указатель на корень дерева;

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

q - указатель отстающий на шаг от p;

key - новый элемент массива;

Создание дерева бинарного поиска :

(псевдокод)


writeln(' Введите элемент массива ');

readln(key);

tree:=maketree(key);

p:=tree;

while not eof do

begin

readln(key);

v:=maketree(key);

while p<>nil do

begin

q:=p;

if key<k(p) then="" p:="left(p)<br"> 
else p:=right(p);

end;

if p=nil then 

begin

writeln('Это корень');

tree:=v;

end

else 

if key<k(q) then="" left(p):="v<br"> 
else right(p):=v;

end;


При обходе дерева слева - направо получаем отсортированный массив 20, 30, 35, 45, 60, 70, 82, 85, 86, 87, 88, 90. Элемент дерева заносится в массив при втором заходе в него (на рисунке вторые заходы показаны зелеными стрелками).

Обход дерева слева - направо

procedure InTree(tree);

begin

if Tree = nil then write('Дерево пусто')

else 

with Tree^ do

begin

if left<>nil then InTree(left);

if right<>nil then InTree(right); 

end;

end;

Задания

Вариант 1: На заводе выпустили детали со следующими серийными номерами : 45, 56, 13, 75, 14, 18, 43, 11, 52, 12, 10, 36, 47, 9. Детали с четными номерами поступают на склад №1, а с нечетными на слад №2. Требуется отсортировать детали на складе №1.


Вариант 2 : Угнали автомобиль. Свидетель запомнил, что первой цифрой номера была 4. В базе угнанных автомобилей в этот день были следующие номера : 456, 124, 786, 435, 788, 444, 565, 127, 458, 322, 411, 531, 400, 546, 410. Нужно составить список номеров начинающихся на 4 и упорядочить его по возрастанию.


Вариант 3 : За неделю езды в транспорте накопились билеты с номерами 124512, 342351, 765891, 453122, 431350, 876432, 734626, 238651, 455734, 234987. Нужно отобрать "счастливые" билеты и расположить их по возрастанию.


Вариант 4 : Дан список людей с указанием их возраста. Для составления графика ухода сотрудников на пенсию требуется составить новый список новый список в том порядке, в каком они будут уходить на пенсию.


Вариант 5 : Студенты сдали пять экзаменов. Нужно отсортировать список студентов по возрастанию общего балла по результатам сданных экзаменов.


Вариант 6 : В городе был один автобусный парк, куда приезжали автобусы с номерами : 11, 32, 23, 12, 6, 52, 47, 63, 69, 50, 43, 28, 35, 33, 42, 56, 55, 101. После строительства второго автопарка решили перевести туда автобусы с нечетными номерами. Для того чтобы составить расписание их движения нужно организовать список номеров автобусов второго парка, упорядочив их по убыванию.


Вариант 7 : Была составлена ведомость по зарплате, представленная в виде : Иванов - 166000, Сидоров - 180000, ... Требуется упорядочить этот список таким образом, чтобы размер зарплаты уменьшался.


Вариант 8 : На стоянке стоят автомобили со следующими номерами : 1212, 3451, 7694, 4512, 4352, 8732, 7326, 2350, 4536, 2387, 5746, 6776, 4316, 1324. Для статистики необходимо составить список автомобилей с такими номерами, сумма первых двух цифр которых равна сумме двух последних цифр, так чтобы каждый следующий номер был меньше предыдущего. 


Вариант 9 : Выпустили лотерейные билеты с четырехзначными номерами. Выигрышными считаются те билеты, сумма цифр которых делится на 4. Составить список выигрышных билетов, упорядоченных по убыванию.


Вариант 10 : Молодой человек взял номер телефона у своей знакомой, но забыл его. Он смог вспомнить только первые три цифры : 469***. В его записной книжке были следующие номера телефонов : 456765, 469465, 469321, 616312, 576567, 469563, 567564, 469129, 675665, 469873, 569090, 469999, 564321, 469010. Составить список номеров начинающихся с цифр 469 и упорядочить их по убыванию.


Вариант 11 : Студенты сдали пять экзаменов. Нужно отсортировать список студентов по убыванию общего балла по результатам сданных экзаменов.


Вариант 12 : Выпустили лотерейные билеты с четырехзначными номерами. Выигрышными считаются те билеты, сумма первых трех цифр которых равна 8. Составить список выигрышных билетов, упорядоченных по возрастанию.

 

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

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