Уханов - лекции

Элемент таблицы А*В означает А отрезков условной длины В.

Копирования исключаются за счет точного распределения отрезков по файлам. На примере использовали двухпутевое слияние. Если использовать многопутевое слияние, то будет работать быстрее. Поэтому рассмотрим слияние на шести файлах для 129 начальных отрезков.

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

Из таблицы следует, что

en = an-1;

dn = an-1 + en-1 = an-1 + an-2;

cn = an-1 + dn-1 = an-1 + an-2 + an-3;

bn = an-1 + cn-1 = an-1 + an-2 + an-3 + an-4;

an = an-1 + bn-1 = an-1 + an-2 + an-3 + an-4 + an-5,

где a0 = 1 и an = 0, при n < 0.

Числа Фибоначчи порядка p определяются правилами:

Fn(p) = Fn-1(p) + Fn-2(p) + ... + Fn-p(p) при n ≥ p;

Fn(p) = 0 при 0 ≤ n ≤ p-2;

Fp-1(p) = 1.

Другими словами, начинаем с p-1 нулей, затем пишем 1. Каждое следующее число является суммой p предыдущих. При p = 2 получаем обычную последовательность Фибоначчи.

Выведенная формула для an показывает, что число отрезков в f1 в процессе слияния на шести файлах есть число Фибоначчи пятого порядка: an = Fn+4(5).

Числа Фибоначчи пятого порядка образуют следующую последовательность: 0 0 0 0 1 1 2 4 8 16 31 ...

Итак, будем вычислять an и tn+1. Как только будет получено tn+1 ≥ N, где N – общее число отрезков, то получим нужное нам точное распределение отрезков. Если получено tn+1 > N, то значит N не является точным числом Фибоначчи. Поэтому следует дополнить N фиктивными нулевыми отрезками.

В общем случае, для M сливаемых файлов число отрезков в файле f1 будет числом Фибоначчи порядке p = M-1: an = Fn+p-1(p). А общее число отрезков будет вычисляться по формуле: tn+1 = tn + (p-1)an.

Каскадное слияние

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

Каждая строка представляет полный проход по всем данным. Проход 2, например, получен из 1 выполнением 5-путевого слияния с f1, ..., f5, на f6, пока не опустеет f5, затем 4-путевого

слияния с f1, ..., f4 на f5, 3-путевого – с f1, f2, f3 на f4, 2-путевого – с f1, f2 на f3 и, наконец, однопутевого (копирования) с f1 на f2. Подробно получение второго прохода можно представить в

таблице.

Ясно, что операции копирования излишни, и их можно было бы опустить. Фактически копирование занимает лишь небольшой процент времени. Большая часть времени тратится на пяти и четырехпутевые слияния.

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

Вычисляем an до тех пор, пока не получим an ≥ N. В этом случае будет получена требуемое точное распределение отрезков по файлам. Если получено an > N, то требуется дополнить N фиктивными нулевыми отрезками.

Древовидные таблицы

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

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

Дана последовательность 5 3 7 2 4 8 6 1. Строим дерево:

5

3 7

2 4 6 8

1

В этом случае возможно построение дерева следующего вида:

Такое дерево только усложняет поиск данных в таблице.

Оценим трудоемкость поиска в случайном дереве

Пусть дано n ключей 1, 2, ..., n, следующих в порядке возрастания. Допустим, что вероятность того, что в корень попадет i ключ равна 1/n. При этом, в левое поддерево попадет i-1 ключ, а в правое – n-i ключей.

Обозначим через an среднюю длину пути до узла дерева. Тогда an(i) – средняя длина пути до узла дерева, если в корне ключ i.

a n (i) = i −n1 (ai−1 +1) +1 1n + nn−i (a n−i +1) .

Первое слагаемое: искомый ключ с вероятностью i −n1 находится в левом поддереве и длина

пути до него ai-1 + 1.

Второе слагаемое: искомый ключ с вероятностью 1/n находится в корне и длина пути до него

1.

Третье слагаемое: искомый ключ с вероятностью nn−i находится в правом поддереве и длина пути до него an-i + 1.

характеристическим для разностного уравнения (1). Подставим в правую часть (1) нижние границы для N(l-1) и N(l-2), которые следуют из неравенства (2):

Очевидно, что если докажем справедливость (4), то этим будет доказана справедливость (2). Преобразуем (4):

1 > αl+1 - αl - αl-1 = αl-1( α2 - α - 1) = 0.

Трехчлен в скобках равен нулю, поскольку α – его корень. Получили, что 1 > 0. Таким

образом, неравенство (2) доказано. Следовательно, число вершин сбалансированного дерева

n > N(l) > αl+1. (5)

Найдем высоту сбалансированного дерева l. Для этого прологарифмируем неравенство (5). log2n > (l+1)log2α,

l < −1+ log2 n = −1+1,44log2 n . log2б

Таким образом, высота сбалансированного дерева не больше, чем 1,44log2n, без корня. Когда производится вставка или удаление – возможно нарушение балансировки. В каждом

узле храним показатель сбалансированности – разность уровней поддеревьев. Обозначим «+» тот факт, что правое поддерево выше левого на единицу; «–» если левое выше правого; «•» если высоты поддеревьев равны. Можно выделить два основных случая:

1 .

A

+ +

B

+

h α

h+1

2.

h+1

βh γ

h+1

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

1.

сохраняется обратный обход

2.

X

•

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

имеют высоту h+2, как и до включения нового узла, следовательно, часть дерева, расположенная над А, не изменится. Для работы алгоритма необходимо хранить в узлах показатели сбалансированности, которые могут иметь значения +1, -1, 0. Для этого достаточно двух битов.

Восстановление балансировки требует логарифм числа операций, следовательно, время тратится логарифмическое.

Идея сбалансированных деревьев принадлежит: Адельсон-Вельский и Ландис. Поэтому эти деревья еще называют АВЛ-деревьями.

В-деревья

Рассмотрим большое бинарное дерево и предположим, что оно хранится на диске. Если буквально следовать рассмотренным алгоритмам работы с деревом, то потребуется около log2N обращений к диску. При N = 106 потребуется до 20 обращений к диску. Но, если разделить дерево на страницы по 7 узлов и считать, что в каждый момент доступна лишь одна страница, то потребуется примерно в три раза меньше обращений. Группировка узлов в страницы, по существу, преобразует бинарные деревья в октарные, разветвляющиеся в каждой странице на 8 путей. Если увеличить число узлов в странице, то потребуется еще меньше обращений к диску.

Изобразим на рисунке группировку узлов в странице по 3 узла.

страницы

Если узлы бинарного дерева объединить в страницы, которые читаются в один проход, тогда дерево будет иметь высоту log4N.

Можно объявить размер страницы и записать в нее столько узлов, сколько поместится. Но может возникнуть проблема мощного перемещения узлов снизу вверх.

Каждый узел В-дерева содержит не менее m/2 ключей и не более чем m, кроме корня, который может содержать от 1 до m ключей. Тогда m – это порядок В-дерева. Если m четно, то удобно. Все листья В-дерева располагаются на одном уровне.

Будем считать, что узел имеет следующую структуру:

Рассмотрим основные операции над В-деревьями. Поиск.

Начинаем поиск от корня. Либо найдем в очередном узле ключ, либо найдем пару ключей ki и ki+1, таких, что искомый ключ находится между ними: ki < k < ki+1. В этом случае нужно спуститься вниз по дереву по указателю pi+1.

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

Вставка.

Вставка всегда происходит в лист.

Если в листе ключей меньше, чем m, то производим вставку. Требуемый лист находим, используя операцию поиска.

Пример: m = 4. Имеем следующее дерево:

100 200

Требуется вставить ключ 140. С помощью операции поиска находим нужный лист и производим вставку. Получим дерево:

100 200

Если теперь будем производить вставку ключа 160, то возникнет переполнение узла, поскольку этот ключ будет пятым, а порядок дерева 4. В этом случае нужно поискать соседа слева или справа, у которого число ключей меньше m. Если такой сосед найден, то рассмотрим множество ключей, состоящее из ключей переполнившегося узла, ключей соседа и разделяющего их ключа отца. Для рассматриваемого примера, это будет множество 20 30 40 100 110 130 140 150 160. В этом множестве найдем средний ключ. Его поставим на место разделяющего ключа в отце, меньшие ключи уйдут к соседу, оставшиеся составят переполнившийся узел. Т.е. получим:

110 200

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

40 110 200

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

Следовательно, В-дерево растет от листьев к корню. Удаление.

Удаление всегда производится из листа.

Если удаляемый ключ находится в листе и если после его удаления в узле остается не менее m/2 ключей, то все в порядке.

Рассмотрим, например, удаление ключа 210. После его удаления в узле остается меньше, чем m/2 ключей. Получили дефицит ключей или антипереполнение. В этом случае поищем богатого соседа и рассмотрим множество, состоящее из ключей узла, из которого произошло удаление, ключей богатого соседа и разделяющего их ключа отца. Для рассматриваемого примера это будет множество 130 140 150 160 200 270. Средний ключ этого множества поместим в качестве разделяющего в отца, а остальные поделим поровну между узлом, из которого удаляли и соседом. Получим следующее:

40 110 150

Теперь удалим ключ 20. В данном случае нет богатого соседа. Тогда рассмотрим множество, состоящее из ключей узла, из которого произошло удаление, разделяющего ключа в отце и соседа с m/2 ключами. Все это множество поместим в узел, из которого удаляли. Сосед уничтожается, а в отце становится на один ключ меньше. Дерево примет следующий вид:

110 150

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

Если удаляемый ключ находится не в листе.

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

Например, удалим узел 110. Получим следующее:

100 150

Оценим время поиска в В-дереве.

Рассмотрим, к скольким узлам будет происходить обращение в наихудшем случае при поиске в В-дереве порядка m. Предположим, что имеется N ключей, а на уровне l расположено