Операция удаления

Выполняется в два действия:

1. Поиск вершины.
2. Если он успешен. то удаление вершины.

Операция удаления вершины имеет три варианта решения, которые зависят от связи вершины с другими.

1. Вершина-лист

В этом случае удаление вершины заключается в удалении самой вершины и обнулении указателя на текущую вершину в родительской вершине.

1. Удаляется вершина с одним потомком.

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

1. Удаление вершины с двумя потомками.

Существуют два правила удаления такой вершины:

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

2. Указатель перенаправляется на корень правого поддерева, а корень левого поддерева присоединяется к самой левой вершине правого поддерева.

 

36.Структуры данных. Б – деревья.

Структуры данных (абстрактные структуры) – это математические модели, предназначенные для представления информации об объектах и о процессах. Структуры хранения данных – это структуры представления информации в компьютере, с помощью которых представляются структуры данных.

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

Относятся к классу сильно ветвящихся деревьев. Дерево строится на основе следующего типового элемента, который является вершиной дерева:

	k1	k2	…	kn
p0	p1	p2	…	pn

Вершина дерева содержит n ключей и (n+1) указателей.

Указатель p₀ указывает на поддерево, содержащее ключи, меньше k₁, p_n указывает на ключи, большие k_n, p_i указывает на ключи, большие k_i и меньшие k_i+1.

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

Свойства В – дерева.

1) В каждой вершине за исключением корня, имеют от n/2 до n-ключей. В корне от одного до n ключей.

2) Ключи расположены в порядке возрастания их значений.

3) Все листья дерева находятся на одном уровне.

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

Для выполнения этих операций выполняется поиск ключа в дереве.

Алгоритм поиска:

1) Указатель на текущую вершину получает адрес корня дерева;

2) Если указатель пуст, то искомого значения нет, ошибка, и переход к пункту 5

3) Производится поиск требуемого значения вершин текущей вершины (применяется двоичный поиск). Если значение найдено, то поиск успешный и переходим к пункту 5.

4) Если ключа нет, то указателю на текущую вершину присваивается значение соответствующего указателя по значению ключа. Переход к п.2.

5) Конец

Добавление вершины:

1) Поиск вершины с заданным ключом, если ключ обнаружен, то завершение с ошибкой.

2) Добавление заданного ключа в последнюю обрабатываемую вершину. Если число ключей в вершине равно n, то разбиение общего списка ключей на 2 подмножества и создается новый лист с вынесением среднего ключа в вершину-родитель.

3) Повторяется до нормальной вставки нового значения элемента.

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

 

37. Документирование программ. Спецификация.

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

Основным элементом спецификации является типизация(строгая фиксация структуры объекта с указанием порядка размещения элементов и перечня возможных значения элемента.) Понятие типизации применимо к переменным и процедурам и функциям. Для выполнения работ по разработке программ составляют спецификации на структуры и процедуры и функции.

Спецификация на структуры денных должна содержать: назначение, перечень элементов структуры с указанием их назначения, типа, возможных значений.

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

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