Учебно-методическии комплекс дисциплины «Структуры и алгоритм обработки данных» (стр. 10 )

typedef struct page {
  int m;  //количество элементов на данной странице
        //n<=m<=nn
  page *p0;  //указатель на левую страницу-наследник
  struct {  //элементы страницы (в виде массива)
  int key;
  page *p;
  }item[nn];  //nn - максимальное количество элементов
        //на странице  nn=2n
};

Включение в Б-дерево

Возможны две ситуации:

Элемент вставляется в страницу, содержащую m < 2n элементов. Тогда процесс включения ограничивается данной страницей. Включение элемента в заполненную страницу:

a) поиск по дереву элемента с данным ключом, и если такого элемента нет, то определение страницы, где элемент должен быть;

b) если на этой странице количество элементов m < 2n, то включение производится только на данной странице;

c) иначе размещается новая страница, количество ключей m+1 (ключ, который вставляется) поровну распределяется на две страницы, а средний ключ перемещается на уровень вверх;

d) все выполняется, начиная с пункта d но уже со страницей верхнего уровня.

В экстремальном случае расщепление может распространиться до корня. Следовательно, Б-дерево растет от листьев к корню.

Рассмотрим на примере:

Необходимо включить ключ 22 в Б-дерево порядка 2.

1. Выяснить, что ключ 22 отсутствует. Включение в страницу С невозможно, т. к. она заполнена.

2. Страница С расщепляется на две страницы (С и D).

3. Элементы страницы С + 1 поровну распределяются на страницы C и D, а средний элемент перемещается на уровень выше на страницу-предок А.

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

Вывод: если дерево содержит т элементов, то мы должны иметь возможность разместить в оперативной памяти k страниц (именно это накладывает ограничения на размер страницы).

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

Возможны два случая:

1. Удаляемый элемент находится на странице-листе. Тогда алгоритм прост и очевиден.

2. Удаляемый элемент находится не на странице-листе.

Алгоритм

1. Производим поиск смежного ключа (самый правый левого поддерева или самый левый правого поддерева). Допустим, находим его на странице Р.

2. Заменяем удаляемый элемент на смежный, а Р уменьшаем на единицу.

3. Проверяем число элементов на уменьшенной странице Р. Если m < n, то нарушено свойство Б-деревьев и нужно совершить дополнительные действия:

балансировку: в оперативную память вызывается одна из соседних страниц Q; элементы страниц P и Q поровну распределяются на обе страницы. слияние: используется, если страница Q достигла своего минимального значения. Процесс слияния полностью обратен процессу расщепления, общее число элементов на страницах P и Q равно 2n-1; можно слить эти страницы в одну и добавить средний элемент со страницы предка P и Q. удаление среднего ключа на странице-предке может также уменьшить ее размер ниже допустимой границы, тогда требуются балансировка или слияние на более высоком уровне. (В экстремальном случае слияние страниц распространяется до корня, что может вызвать уменьшение высоты Б-дерева).

Бинарные Б-деревья

Бинарное Б-дерево - это Б-дерево первого порядка (n=1).

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

Бинарное Б-дерево (ББ-дерево)

состоит из узлов с одним или двумя элементами; содержит две или три ссылки на потомков (еще его называют 2-3 дерево); все листья находятся на одном уровне; все нетерминальные страницы содержат два или три потомка.

Для представления ББ-дерева можно выбрать следующую структуру:

typedef struct node {
        int key;
        node *left;
        node *right;
        int h;
        };

left - указатель на страницу-наследник;

right - указатель либо на страницу-потомок, либо на страницу-брата; для различия используется показатель h (при одном значении фиксируется горизонтальное перемещение, а при другом - вертикальное).

Такое дерево поиска гарантирует максимальную длину пути.

Включение в ББ-дерево

Возможны следующие варианты:

1. Растет правое поддерево узла А и когда А - единственный ключ на странице, тогда потомок В становится братом А (вертикальная ссылка становится горизонтальной).

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

3. Узел В один на странице. Увеличилась высота левого поддерева узла В. Левое поддерево А может стать братом В, но необходим поворот, так как левая ссылка не может быть горизонтальной.

4. Если В уже имеет брата, тогда подъем А даст страницу с тремя узлами, что требует расщепления: С становится потомком В, который поднимается на ближайший более высокий уровень.

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

Лучше использовать Симметричное бинарное Б-дерево.

У такого дерева узел может иметь горизонтальные ссылки и направо, и налево.

СББ-дерево имеет следующие свойства:

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

Структура СББ-дерева включает в себя две переменные lh, rh для обозначения природы ссылок.

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

Максимальная высота СББ-дерева с n узлами – log n.

Самый длинный путь – 2 log n.

Основное свойство Б-деревьев – все терминальные узлы находятся на одном уровне.

Такие структуры еще называют кустарниками (т. к. их можно сравнить с подстриженными кустарниками).

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

1. У кустарниковых деревьев длина пути в среднем больше, чем у AVL-деревьев, зато перестройка узлов у кустарниковых деревьев будет происходить реже.

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

Лекция №13

Тема: Графы

Цель: Ввести основные понятия и определения. Знать способы задания графов.

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

Граф – это пара G=<V, E>, где V - конечное непустое множество вершин, Е - множество ребер (пар вершин). Граф состоит из множества элементов данных, называемых вершинами и множества ребер, соединяющих эти вершины попарно.

Вершины могут обозначать города, а ребра – дорожное сообщение между ними.

Орграф

Если пары Е неупорядочены (движение по дорогам может происходить в обоих направлениях) - граф неориентированный, иначе - ориентированный (орграф). Если часть ребер ориентирована, а часть нет, то такой граф называется смешанным.

Вершины и называются смежными, если существует ребро Е, соединяющее их. Ребра называют смежными, если они имеют хотя бы одну общую вершину. Говорят, что ребро (, ) инцидентно вершинам, .

Петля – это ребро графа, соединяющее некоторую вершину саму с собой.

Путь – это такая последовательность вершин, , …, , что для всех i, , существуют ребра (, ).

Путь в орграфе – это последовательность вершин, , …, , для которой существуют направленные дуги ->, ->, …, ->.

Путь называется простым, если все вершины графа различны.

Длина пути равна количеству ребер, составляющих путь.

Вершины и называются связанными, если для этих вершин существует путь, , …, .

Граф называется связным, если для любой пары вершин существует соединяющий их простой путь.

Цикл – это простой путь длины не менее 1, который начинается и заканчивается в одной и той же вершине.

Дерево – это граф без циклов.

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

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

Способы задания графов

Существуют следующие способы задания графов:

матрица инцидентности; матрица смежности; матрица весов; список ребер; список смежности.

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

Матрица инцидентности – это матрица размером (где n - число вершин, m - число ребер). Для ориентированного графа столбец, соответствующий ребру <x, y>, содержит 1 в строке, соответствующей вершине y (стрелочка), -1 - в строке, соответствующей вершине х (начало стрелки); 0 - в остальных строках. В случае петли возможна постановка другого числа (петля <x, x>, число 2).

Например:

Для неориентированного графа столбец, соответствующий ребру <x, y>, содержит 1 в строках, соответствующих вершинам x, y, и 0 - в остальных строках.

Например:

Для представления графа матрицей инцидентности требуется элементов информации, из которых большинство нули. Матрица инцидентности неудобна для ввода и обработки на ЭВМ; кроме того, она не несет прямой информации о ребрах.

Для ответа на вопрос - существует ли ребро <x, y> - необходимо перебрать все столбцы.

Матрица смежности - матрица размером, элементы которой равны 1, если i-я вершина смежна с j-ой, и 0 в противном случае.

У неориентированных графов ребро <x, y> является ребром <y, x>, а потому матрица смежности для них всегда симметрична.

Матрица смежности является симметричной и достаточно просто может использоваться для ввода и обработки на ЭВМ.