Программирование. Структура деревьев

    1.2.3 Основные операции (алгоритмы) 

     Добавление элемента в дерево

    Алгоритм  добавления включает следующие шаги:

    -    выделение памяти для новой вершины

    -    формирование информационной составляющей

    -    формирование двух пустых ссылочных полей на будущих потомков

    -   формирование в родительской вершине левого или правого ссылочного поля – адреса новой вершины.

 Удаление элемента из дерева

    Удаление  реализуется более сложным алгоритмом:

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

Ситуация 2. Удаляемая вершина имеет только одного потомка. В этом случае удаляемая вершина вместе со своим потомком и родителем образуют фрагмент линейного списка. Удаление реализуется простым изменением указателя у родительского элемента.

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

Обход дерева

Обход в прямом направлении:

-   обработать корневую вершину текущего поддерева

-   перейти к обработке левого поддерева таким же образом

-   обработать правое поддерево таким же образом

 Cимметричный обход:

-   рекурсивно обработать левое поддерево текущего поддерева

-   обработать вершину текущего поддерева

-   рекурсивно обработать правое поддерево 

Обход в обратном направлении:

-   рекурсивно обработать левое поддерево текущего поддерева

-   рекурсивно обработать правое поддерево текущего поддерева

-   затем – вершину текущего поддерева

На рисунке 3 представлен обход в трех направлениях. 

 

Рисунок 3 – Обход в трех направлениях 

Поиск элементов в дереве

Алгоритм поиска в двоичное дерево очень прост. Начиная с корневой вершины для каждого текущего поддерева надо выполнить следующие шаги:

  -   сравнить ключ вершины с заданным значением х

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

  -   либо если найден искомый элемент

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

[1] Ахо А., Хопкрофт Дж., Ульман Дж, Структуры данных и алгоритмы. – М:Мир, 2000 – 256 с.

[7] http://www.rsdn.ru/ 

    1.3 Пирамида

    1.3.1 Определение. Основные понятия

    Пирамида  – это специальная разновидность  двоичного дерева, построенная по особым правилам и имеющая особые свойства.

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

    Можно отметить следующие полезные свойства пирамиды:

- на вершине пирамиды всегда находится наименьший элемент во всем массиве (элемент а₁), элемент а₂   является наименьшим для левого поддерева, элемент а₃  является наименьшим для правого поддерева и т.д.

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

 

    1.3.2 Сортировка на основе пирамиды

    1.3.2.1  Представление исходного массива в виде пирамиды

    -  Условно разделяем исходный массив на две половины: левую с индексами от 1 до [n/2], и правую с индексами от [n/2]+1  до  n (здесь [ ] обозначает целую часть); считаем пока, что левая половина образует верхнюю часть строящейся пирамиды, а правая – нижний слой терминальных вершин

    -  Выбираем  в левой половине последний элемент (его индекс m=[n/2]), а в правой половине – его непосредственных потомков (одного или двух, но хотя бы один будет обязательно) с индексом  2m  и, возможно,  2m+1

    -  Если потомков два, то выбираем из них наименьшего

    - Сравниваем элемент а_m с наименьшим из потомков: если он больше, то меняем эти элементы в массиве местами для получения фрагмента пирамиды; в противном случае оставляем все без изменений, поскольку эти элементы уже образуют фрагмент пирамиды

    -  Повторяем все описанные действия последовательно для оставшихся в левой части элементов справа налево, т.е. для  а_m-1, а_m-2,  а_m-3, . . ., а₁,  при этом если происходит обмен между родительской вершиной и одним из потомков, выполняется проверка для новой вершины-потомка, т.к. она может иметь своих потомков, с которыми возможно потребуется ее обменять для выполнения условия пирамиды.

    Тем самым, для каждого элемента массива  находится его новое расположение в массиве таким образом, чтобы  выполнялись условия пирамиды. Процесс определения нужного положения элемента в массиве-пирамиде называют просеиванием элемента через пирамиду. Построение пирамиды заканчивается после просеивания первого элемента  а₁. Пример для 15 элементов приведен в таблице  (символ  ~  обозначает перестановку элементов).

    В худшем случае каждый шаг в просеивании  очередного элемента требует двух сравнений: сначала сравниваются два потомка  текущего элемента, а потом наименьший из них сравнивается с самим элементом. В примере для построения пирамиды потребовалось 11*2=22 сравнения и 9 пересылок. 
 
 
 
 

    Таблица 1 –Присвоение элемента через пирамиду. 

 
 
 
 
    

2. Последовательное удаление минимального элемента с вершины пирамиды

Реализация этапа  состоит в  (n-1)-кратном повторении следующих действий:

-  С вершины пирамиды забирается минимальный элемент  а₁

-  На его место в вершину пирамиды помещается последний элемент в массиве, причем индекс этого последнего элемента на каждом шаге будет уменьшаться от  а_n до  а₂  

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

-  На последнем шаге в пирамиде останется один элемент (самый большой) и сортировка будет закончена

При больших  n  метод в среднем немного уступает быстрой сортировке и имеет оценку порядка (n*log ₂ n)/2. Единственное, в чем он превосходит быструю сортировку, так это поведение на аномальных входных данных, когда быстрая сортировка перестает быть “быстрой”, а пирамидальная сохраняет свою трудоемкость порядка O(n*log ₂ n). В указывается, что пирамидальную сортировку выгодно использовать в том случае, когда требуется не провести полную сортировку большого набора данных, а лишь найти несколько (причем – немного) первых наименьших элементов.

[3] Кормен Т, Пирамидальная сортировка. – М:Мир, 2000 – 390 с

[6] httr://www.codelab.ru/t/pyramid_sort/

 

     2 Реализация прикладной задачи с использованием пирамиды

    2.1 Постановка задачи

Написать диалоговую программу для работы с пирамидами. При запуске программы должно отображаться меню, пункты которого реализуют основные операции с пирамидой.

Программа должна быть однозначной и защищена от неправильных действий пользователя.

    2.2 Алгоритм решения задачи

Шаг 1. Задаем массив от 1 до 1000.

Шаг 2. Заполняем массив случайными числами.

Шаг 3. Программа  сортирует массив в порядке возрастания.

2.3 Описание программных средств

2.3.1 Описание переменных

2.3.1.1 Глобальные  переменные

var

   a: array[1..MaxN] of LongInt – массив пирамиды;

   n, hs – переменные для построения пирамиды;

 i – постепенно из пирамиды выбрасывает максимальный элемент;

2.3.1.2 Локальные переменные

Рrocedure swap(var x, y: LongInt);

x, y, z – переменные для создания пирамиды;

Рrocedure pushdown(j: LongInt);

j, max – элементы, для выбора максимального значения из трех.

Рrocedure heapsort;

n– переменная для построения кучи и сортировки массива 

    2.4 Описание процедур и функций и их значения

Procedure swap (var x, y: LongInt) – используется для создания пирамиды;

Рrocedure pushdown(j: LongInt) – процедура выбора максимального элемента;

Рrocedure heapsort– сортировка пирамиды;

Рrocedure input – процедура для ввода значений;

Рrocedure output – выводит отсортированный массив. 
 

    2.5 Входная и выходная информация

    2.5.1 Входная информация

Входной информацией  является определенный массив случайных  чисел. Размерность массива задается пользователем.

    Экранная  форма

    2.5.2 Выходная информация

    Выходной  информацией является отсортированный  массив.

    Экранная  форма

    2.6 Руководство пользователя

    В строку «Введите количество элементов (не более 1000)» необходимо ввести число  от 1 до 1000. Число будет соответствовать  размеру массива. Затем следует  нажать клавишу «Enter», появится заранее заданный массив. Нужно заполнить массив случайными числами. После каждого введенного числа необходимо нажать клавишу «Enter», чтобы перейти к вводу следующего. После того, как массив будет заполнен, программа отсортирует его по принципу пирамидальной сортировки. Для завершения работы с программой необходимо нажать клавишу «Enter». 

    2.7 Технология разработки программного средства

    2.7.1 Технология разработки программы

    Данная  программа разрабатывалась в  несколько этапов:

    - получение  задания на курсовое проектирование