Пример: Использование двух связанных двунаправленных списков для представления разреженных матриц(пример многосвязных линейных списков)

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

Цель состоит в том, чтобы оперировать с матрицей так, будто матрица представлена в памяти вся, но для экономии не отводить место на нулевые элементы.

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

Влево, вверх: связи со следующим ненулевым элементом слева в строке или вверху в столбце.

14 0 0 0

10 0 13 0 - разреженная матрица

0 0 0 0

-15 0 -21 2

Связь в головах горизонтальных списков является адресом самого правого значения в строке, а связь “вверх” в головах вертикальных списков является адресом самого нижнего значения в столбце.

При последовательном распределении памяти матрица размера 200*200 заняла бы 40000 слов, в то же время разреженная матрица 200*200 с большим числом нулевых элементов может быть представлена в вышеописанной форме в ОП, содержащей приблизительно 4000 слов (в 10 раз меньше расход памяти).
Разреженные матрицы применяются в алгоритмах решения линейных уравнений, обращения матриц и линейного программирования (симплекс - метод).

Многосвязные списки применяются также в базах данных

3. Древовидная структура, основные понятия. Способы обхода бинарного дерева.

Древовидная структура – это конечное множество, содержащее один или более узлов (n) такое, что:

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

2.остальные узлы содержатся в m>= 0 попарно непересекающихся множествах

T₁, Т₂, …, Т_m, каждое из которых в свою очередь является деревом.

3.Деревья T₁, Т₂, …, Т_m называются поддеревьями данного корня.

Дерево - это граф, который характеризуется следующими свойствами:

1. Cуществует единственный элемент (узел или вершина), на который не ссылается никакой другой элемент - и который называется корнем

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

3. На каждый элемент, кроме корня, имеется единственная ссылка, т.е. каждый элемент адресуется единственным указателем

Линия связи между парой узлов дерева называется обычно ветвью. Те узлы, которые не ссылаются ни на какие другие узлы дерева, называются листьями (или терминальными вершинами) (рис. 4.1, 4.2 - b,k,l,h - листья). Узел, не являющийся листом или корнем, считается промежуточным или узлом ветвления (нетерминальной или внутренней вершиной).

Дерево обычно изображается в перевернутом виде с корнем вверху, листьями внизу (рис. 12).

Дерево может быть определено как иерархия узлов с парными связями, в которой:

1. самый верхний уровень иерархии имеет один узел, называемый корнем;

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

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

Степень узла – число непосредственных потомков внутреннего узла.

В примере (рис. 12) степень узлов: A,B – 2, C – 3, E – 1; H,J,D,G,F – 0.

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

Если х находится на уровне i, то говорим, что y на уровне i+1. Узел у, который находится непосредственно под узлом х называется непосредственным потомком х (или сыном, или подчинённым). Узел x называется непосредственным предком y (или исходным, или отцом). Считается, что корень дерева находится на уровне 1

Уровень узла по отношению к дереву Т определяется следующим образом:

· корень дерева имеет уровень 1;

· корни поддеревьев, непосредственно входящих в дерево, имеют уровни 2,3, и т.д.

Глубина (высота) дерева – максимальный уровень узла дерева (в примере дерево имеет глубину равную четырем) или число уровней в дереве.

Степень дерева – максимальная степень его узлов (в примере дерево имеет степень = 3, т.к. максимальная степень узла = 3).

Лист (концевой узел, терминальный элемент) – элемент не имеющий потомков – это узел степени 0. (на рис. H,J,D,G,F – листья)

Внутренний узел (или узел разветвления) – это узел, не являющийся концевым (т.е. не являющийся листом).

Момент – число узлов (в примере – 9).

Вес – число листьев (в примере – 5).

Основание – число корней. (в примере – 1)

Длина пути х – число ветвей (ребер), которые необходимо пройти, чтобы продвинутся от корня к узлу х. Корень имеет длину пути 1, его непосредственный потомок – длину пути 2 и т.д. Вообще узел на уровне i имеет длину пути i.

Длина пути дерева – сумма длин путей всех его узлов. Она так же называется длинной внутреннего пути.

Средняя длинна пути Р_i есть:

, где n_i число узлов на уровне i.

Лес – множество (обычно упорядоченное), состоящее из некоторого (может быть равного 0) числа непересекающихся деревьев.

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

Высота сбалансированного дерева , где n – количество узлов.

1. В виде вложенных множеств:

1. В виде вложенных скобок

(А(В(H)(J))(C(D)(E(G))(F)))

3. В виде ступенчатой записи

1. В виде графа:

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

Ориентированное дерево - это такой ациклический ориентированный граф, у которого одна вершина, называемая корнем, имеет полустепень захода, равную 0, а остальные - полустепени захода, равные 1. Ориентированное дерево должно иметь, по крайней мере, одну вершину. Изолированная вершина также представляет собой ориентированное дерево.

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

Бинарное дерево – упорядоченное дерево степени 2.

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

Способы обхода бинарного дерева.

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

1.прямой порядок(процедура Preorder(префиксный), рекурсивная процедура r_Preoder);

2.обратный порядок(процедура Inorder(инфиксный), рекурсивная процедура r_Inorder);

3.концевой порядок(процедура Postorder (постфиксный), рекурсивная процедура r_Postorder).

1. A B D C E G F H J – при прохождении в прямом порядке.

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

D B A E G C H F J

3. D B G E H J F C A – при прохождении в концевом порядке.

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

4. Дерево поиска. Включение элементов. Удаление элементов из дерева поиска.

Бинарные деревья часто используются для представления множеств данных, элементы которых имеют ключи – некоторые значения (числовые или символьные), по которым один элемент отличается от другого.

Если дерево организованно так, что для каждого узла внутри дерева все ключи в левом поддереве меньше, чем в правом, то – это дерево поиска. Используют для зщадачи сортировки и для задачи поиска

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

Type ссылка =^ узел;

Узел = record

Ключ: integer;

Счетчик: integer;

Лев, прав: ссылка;

End;

Процесс поиска представим в виде рекурсивной процедуры. Параметр процедуры Р передается как параметр-переменная, а не как параметр-значение. В случае включения переменной должно присваиваться новое значение ссылки, которая перед этим имела значение nil.

Алгоритм поиска по дереву с включением очень часто применяется в программах работы с базами данных (в СУБД) и в трансляторах для организации объектов, которые нужно хранить и искать в памяти.

Способы обхода и поиска:

1. Попасть в корень. Попасть в левое поддерево. Попасть в правое поддерево - RAB

2. Попасть в левое поддерево Попасть в корень. Попасть в правое поддерево –ARB

3. Попасть в левое поддерево Попасть в правое поддерево Попасть в корень. – ABR

В таком случае поиск осуществляется min за n сравнений, где n – глубина дерева.

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

Процесс поиска представим в виде рекурсивной процедуры.

Параметр процедуры Р передается как параметр-переменная, а не как параметр-значение. В случае включения переменной должно присваиваться новое значение ссылки, которая перед этим имела значение nil.

Удаление узлов из дерева заключается в переприсвоении ссылок и освобождении памяти,3 случая:

1. если у удаленного узла отсутствуют потомки, то ссылка на него из вышестоящего узла заменяется на ссылку данного узла, а память освобождается
2. если хотя бы один потомок является концевым, то потомок заменяет место удаляемого узла
3. если ни один потомок не является концевым, то удаляемый узел нужно заменить:

1) или на самый правый элемент его левого поддерева

2) или на самый левый элемент его правого поддерева

5. В-деревья, их свойства, построение. Индексирование массивов данных. Индексные деревья.

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

Будем называть также поддеревья страницами. На рисунке 9 изображено бинарное дерево, разделенное на страницы, состоящее из 7-и узлов каждая

Рис 20. - Бинарное дерево, разделенное на страницы (n = 3)

Уменьшение количества обращений к диску (а теперь обращение к каждой странице предполагает обращение к диску) может быть значительным. Предположим, что на каждой странице размещается 100 узлов, тогда дерево поиска, содержащее 10⁶ элементов потребуется в среднем log₁₀₀10⁶ = 3 обращения к страницам в место 20-ти.

При хранении дерева на диске соблюдать сбалансированность (а тем более идеальную) очень дорого. Для этого случая очень разумный критерий был сформулирован Р. Бэйером: каждая страница содержит от n до 2n узлов при заданном постоянном n. Следовательно, в дереве с N элементами и максимальным размером страницы 2n узлов наихудший случай потребует log_nN обращений к страницам. А обращение к страницам составляют, как известно, основную часть затрат на поиск. Кроме того, коэффициент использования памяти состоит не менее 50%, т.к. страницы заполнены хотя бы наполовину. При всех этих преимуществах данная схема требует сравнительно простых алгоритмов поиска, включения и удаления

Рассматриваемые структуры данных называются B – деревьями и имеют следующие свойства:

1. Каждая страница содержит не более 2n элементов (ключей).

2. Каждая страница, кроме корневой, содержит не менее n элементов (n – порядок B – дерева).

3. Каждая страница является либо листом, т.е. не имеет потомков, либо имеет m + 1 потомок, где m – число находящихся на ней ключей.

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

На рис. 21 показано B – дерево порядка 2 с 3-мя уровнями. Все страницы содержат 2, 3 или 4 элемента. Исключением является корень, которому разрешается содержать только один элемент. Все листья находятся на уровне 3.

Ключи расположены в возрастающем порядке слева направо, если спроецировать дерево на один уровень, вставляя потомков между ключами, находящимися на странице – предке.

.

Поиск по сайту: