Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
Результаты занесите в таблицу. 5. Вычислите ускорение шарика по формуле равноускоренного движения: ....полностью>>
'Документ'
В настоящее время задача воспитания подростков является достаточно серьёзной. Сводки вечерних новостей, телепередачи, информационные заметки и ролики ...полностью>>
'Документ'
Настоящим письмом  [указать наименование организации] просит Вас предоставить комплект конкурсной документации согласно опубликованному извещению на о...полностью>>
'Реферат'
В первой главе дается определение системы сбора данных, рассматривается ее обобщенная структура, даются основные сведения о возможных измеряемых сигна...полностью>>

Главная > Документ

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

1. Оценка эффективности алгоритмов. Нотация Big-O. Техника вывода оценки Big-O на примере алгоритма сортировки вставками. Классификация алгоритмов по трудоёмкости.

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

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

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

Вторым показателем эффективности алгоритма сортировки является объем дополнительной памяти, используемый для сортировки. По этому показателю алгоритмы делятся на три группы:

- алгоритмы, которые организуют сортировку на том же месте и не используют дополнительную память (кроме стека и таблицы);

- алгоритмы, которые используют представление в виде связанного списка или другие структуры указателей или индексов;

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

Нотация Big-O - порядок роста или асимптотическая оценка роста. Big-O = O(n): О - объем данных, n – нотация.

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

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

При анализе около каждой строки будем отмечать ее стоимость – число элементарных операций Сi и число раз, которые эта строка выполняется. Выведем основной параметр, используемый при анализе – размерность массива n, т.е. число элементов.

Insertion_Sort (A, n)

Стоимость

Число раз

1.

for j ← 2 to n

С1

n

2.

do key ← A[j]

С2

n-1

3.

добавить A[j] к отсортированной части A[1… j -1]

4.

i←j -1

С4

n-1

5.

while i>0 and A[i]>key

С5

6.

do A[i+1] ← A[i]

С6

7.

i←i-1

С7

8.

A[i+1] ←key

С8

n-1

Для каждого j от 2 до n подсчитаем, сколько раз будет выполнена строка 5 и обозначим это число через tj. Строка стоимостью С, повторенная n раз, вносит в общее время c*m операций. Сложив все вклады строк, получим показатель:

Эффективность зависит не только от размерности массива, но и от его упорядоченности.

Лучший случай, когда массив уже отсортирован. Тогда цикл в строке 5 завершается после первой проверки, т. к. A[i] <=key при i= j-1 и tj =1. Тогда общее время равно:

Таким образом, Т(n)=a*n+b. Линейная зависимость алгоритма сортировки. Зависит от размера массива.

Худший случай, когда массив расположен в обратном порядке, убывающем порядке. время работы функции будет максимальным, т.к. каждый элемент A[j] придется сравнивать со всеми элементами A[1]…A[j-1]. При этом tj =j.

Т.к. и , то

Таким образом, T(n)=a*n2+b*n+c. Константы a, b, c определяются значениями С1, …. , С8. Квадратичная зависимость (полиномиальный характер).

Асимптотическая оценка a*n2+b*n+c  a*n2 – порядок роста – определяет нотацию BigO=O(n2)

О (1)

Большинство инструкций программы запускается один или несколько раз, независимо от n. Т.е. время выполнения программы постоянно. (помещение в стек)

О (n)

Время выполнения программы линейно зависит от n. Каждый входной элемент подвергается небольшой обработке. (поиск min/max в массиве, значения в связанном списке) (for…; i

О (n2)

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

О (n3)

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

О (logn)

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

О (n*logn)

Время выполнения программы пропорционально n*logn возникает тогда, когда алгоритм решает задачу, разбивая ее на меньшие подзадачи, решая их независимо и затем объединяя решения подзадач (комбинация). Линерифмическая зависимость(сортировки быстрая, слиянием)

О (2n)

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

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

Общие принципы алгоритмов сортировки.

Базируются на использовании 2х операций: сравнении и обмене. Если данные полностью находятся в оперативной памяти, то сортировка называется внутренней. Если не полностью (во внешней памяти) – внешняя.

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

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

Адаптивный алгоритм – если трудоемкость зависит от перестановки данных (сортировка вставками – адаптивный; выбором - неадаптивный)

Устойчивый алгоритм – если при сортировке по одному ключу есть сохранение порядка по другим ключам.

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

2. Алгоритмы сортировки выбором и сортировки с помощью дерева выбора. Эффективность алгоритмов.

Selection_Sort (A, n). InPlace – алгоритм. O(n2).

С

44 55 12 42 94 06

06 55 12 42 94 44

06 12 55 42 94 44

06 12 42 55 94 44

06 12 42 44 94 55

06 12 42 44 55 94

начала ищется минимальный элемент в массиве A[1…n] и меняется местами с первым элементом в массиве. Далее находится второй минимальный элемент в массиве A[2…n] и меняется местами со вторым элементом и т.д. Т.е. алгоритм работает по принципу выбора наименьшего элемента из числа несортированных. Основную составляющую времени представляет количество операций сравнения во внутреннем цикле (строка 4).

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

Число обменов равно n. Число сравнений – n2/2.

Сортировка с помощью дерева выбора. O(n*logn).

Этот метод возник при попытке улучшить сортировку выбором. Можно ускорить сортировку, уменьшив количество сравнений при поиске наименьшего элемента, если в результате каждого прохода получать больше информации, чем просто позицию минимального элемента. Например, можно сравнить попарно соседние элементы и определить в каждой паре меньший элемент. Для этого потребуется n/2 сравнений. Затем сравнить попарно меньшие элементы и определить меньшие из меньших (требуется n/4 сравнений). Наконец получится одна пара меньших из меньших и определяется наименьший элемент. Хотя в сумме получилось n-1 сравнений, но зато определен минимальный элемент и получено дерево выбора, хранящее информацию о наименьших элементах в подгруппах из двух, четырех и т.д. элементах.

Как использовать это дерево для выбора следующего наименьшего элемента? Для этого убираем из дерева выбора наименьший элемент (выбор) и заменяем его в дереве на «дыру» (или ключ ). Для этого мы спускаемся по дереву по пути, указанному значением наименьшего ключа и заменяем его «дырой».

При возврате корректируем промежуточные узлы дерева, замененные «дырами», выбираем вновь в парах наименьшие значения (снизу вверх).В корне дерева вновь оказался элемент с наименьшим ключом. Вновь удаляем его из дерева и т. д.

Повторив n таких шагов, дерево становится пустым (то есть состоит из «дыр») и процесс сортировки закончен.

Недостатки:

  • дополнительная память для хранения дерева;

  • нужно полностью проходить все дерево, сравнивая элементы с дырами.

Высота дерева h = log2(2n).

3. Алгоритмы сортировки выбором и пирамидальной сортировки. Эффективность алгоритмов.

Selection_Sort (A, n). InPlace – алгоритм. O(n2).

С

44 55 12 42 94 06

06 55 12 42 94 44

06 12 55 42 94 44

06 12 42 55 94 44

06 12 42 44 94 55

06 12 42 44 55 94

начала ищется минимальный элемент в массиве A[1…n] и меняется местами с первым элементом в массиве. Далее находится второй минимальный элемент в массиве A[2…n] и меняется местами со вторым элементом и т.д. Т.е. алгоритм работает по принципу выбора наименьшего элемента из числа несортированных. Основную составляющую времени представляет количество операций сравнения во внутреннем цикле (строка 4).

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

Число обменов равно n. Число сравнений – n2/2.

Heap_Sort (A, n). InPlace – алгоритм. O(n*logn).

Пирамида определяется как последовательность ключей такая, что и для i=l, …, z/2, где - левый сын, - правый сын узла .

Часто пирамиду называют частично упорядоченным деревом, поскольку здесь не обязательно соблюдение требования . Такую последовательность (дерево) можно разместить в массиве. Корень дерева занимает первую позицию, то есть имеет индекс 1, сыновья корня – позиции 2, 3. В свою очередь сыновья сыновей занимают позиции 4 и 5 и 6 и 7 соответственно и т.д. Попробуем использовать вместо дерева выбора такую пирамиду. Например, пирамида является деревом выбора.

Как построить пирамиду на базе сортируемого массива?

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

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

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

К

1 2 3 4 5 6 7 8

44 55 12 | 42 94 18 06 67

44 55 | 06 42 94 18 12 67

44 | 42 06 55 94 18 12 67

06 42 12 55 94 18 44 67

ак в сортируемом массиве выстроить пирамиду?

Вторую половину массива можно считать нижним уровнем пирамиды. Здесь элементы взаимно не упорядочены. Будем постепенно добавлять к пирамиде слева элементы, и просеивать их. Входом являются массив и индексы, задающие границы строящейся в массиве пирамиды. Shift (A, l, r).

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

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

Итак, имеем исходную пирамиду: 06 42 12 55 94 18 44 67.

Удаляем элемент из вершины (06) и затем помещаем в вершину последний элемент (67). Значение (06) помещаем на место 67. При этом правая граница пирамиды смещается влево на одну позицию.

Оценка эффективности:

Пирамидальная сортировка неэффективна для небольших n, но очень эффективна при больших n и становится сравнима с сортировкой Шелла. Даже в самом плохом случае сортировка имеет эффективность О(n*logn). Неясно, какой случай плохой. Сортировка очень любит последовательности, в которых элементы более менее отсортированы в обратном порядке.

4. Алгоритмы сортировки вставками и сортировки Шелла. Эффективность алгоритмов.

Insertion_Sort (A, n). O(n2).

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

Алгоритм можно улучшить, убрав проверку i>0 в цикле while. Для этого перед сортировкой в массиве ищется минимальный элемент и помещается в первую позицию массива. После этого можно приступить к сортировке, не проверяя начало массива во внешнем цикле.

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

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

Число обменов равно n2/8. Число сравнений – n2/4.

Shell_Sort (A, n). O(n3/2).

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

Сортировка происходит в несколько этапов. На первом этапе элементы, отстоящие друг от друга на расстоянии h, объединяются в группу. Таким образом, образуется n/h групп. В каждой группе производится сортировка вставками.

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

Немаловажным вопросом является выбор расстояний h1, h2, h3, … ,ht при условии ht=1 и hi+1< hi. Сортировка с h1+i < hi /2 … 4, 2, 1 дает плохие результаты, поскольку на всех этапах, за исключением последнего, элементы на нечетных позициях не сравниваются с элементами на четных позициях. Для случайных файлов эффективность резко снижается и приближается к О(n2). Это пропорционально, например, если половина элементов с меньшими значениями находится на четных позициях, а другая половина с большими значениями – на нечетных позициях.

Нужно выбрать такую последовательность шагов, чтобы позиции элементов, попадающих, в одну группу, постоянно перемешивались. Для этого шаги должны быть взаимно простыми числами, т.е. не имеющими общих делителей (2, 7…). Кнут предложил следующую последовательность расстояний: 1, 4, 13, 40, 121, 364, 1093, 3280, 9841… Т.е., расстояния находятся в соотношении 1/3, hk-1=3 *hk+1, hk=hk-1/3.

Анализ эффективности сортировки Шелла показал, что алгоритм имеет показатель эффективности О(n3/2).

5. Алгоритмы обменной сортировки и Шейкер - сортировки. Эффективность алгоритмов.

Buble_Sort (A, n). O(n2).

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

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

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

Shaker_Sort (A, n).

Шейкер–сортировка является усовершенствованным методом пузырьковой сортировки.

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

Алгоритм пузырьковой сортировки демонстрирует симметрию: один неправильно расположенный «пузырек» всплывает на место за один проход, а неправильно расположенный «тяжелый» элемент в легком конце опускается за один проход на один шаг в сторону правильного места.

Массив 12 18 42 44 55 67 94 06 будет отсортирован за 2 прохода, а массив 94 06 12 18 42 44 55 67 будет отсортирован за 8 проходов. Эта симметрия подсказывает третье улучшение – менять направление следующих один за другим проходов. Поэтому алгоритм называется шейкер-сортировкой.

Вместо 7 проходов шейкер-сортировка дает 5 проходов, причем на каждом проходе количество просматриваемых пар уменьшается.

Анализ алгоритма шейкер-сортировки довольно сложен. Кнут получил, что среднее число проходов пропорционально и среднее число сравнений пропорционально . Но число обменов, как и методе пузырька равно . Эта сортировка хороша, когда элементы почти упорядочены.

6. Алгоритмы обменной сортировки и сортировки разделением. Эффективность алгоритмов.

Buble_Sort (A, n). O(n2).

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

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

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

QSort (A, l, r). O(n*logn).

Сортировка разделением является улучшением обменной сортировки (пузырьковой сортировки). Хотя пузырьковая сортировка среди элементарных методов считается в среднем самой неэффектной, ее улучшение – быстрая сортировка является самым лучшим на данный момент методом сортировки массивов. Метод был предложен Хоором и назван быстрой сортировкой. В этом методе для достижения наилучшей эффективности перестановки производятся на большие расстояния, как и в методе Шелла.

Рекурсивный вариант.

При просмотре элементов с обоих концов массива элементы массива А[l…r] переставляются таким образом, чтобы элементы A[l…k] были не больше любого элемента A[k+1, r], где к – некоторый индекс на интервале l…r, то есть l<= k<=r. То есть массив разбивается на две части, в первой из которых сосредоточены меньшие значения, а во второй – большие. Эта операция называется разделением. Затем операция рекурсивно выполняется для частей A[l…k] и A[k+1…r] до тех пор, пока размер части не станет равным 1. После этого массив отсортирован.

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

Разбиение массива. Partition(A, l, r).

Наугад берется элемент массива в качестве опорного, относительно которого массив разбивается на две части. Часть массива A[l…k] будет содержать элементы, не большие х, а вторая часть A[k+1…r] – элементы не меньшие х. Разделение происходит при просмотре массива с двух концов. Вначале просматриваем массив от конца до тех пор, пока не обнаружим элемент A[j]<= x, затем просматриваем массив от начала до тех пор, пока не обнаружим элемент A[i] >=x.

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

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

Frame4

Теперь по рекурсии разделяем первую и часть A[l…k] и A[k+1…r], выбирая в них в свою очередь опорные элементы. В приведенном примере опорный элемент выбран удачно, и массив оказался поделенным на две части. Реализация алгоритма разбиения содержит ряд тонких моментов. Во-первых, не очевидно, что индексы i и j не выйдут за пределы участка l…r в процессе работы. Во-вторых, разбиение сильно зависит от того, насколько удачно выбран опорный элемент х. Если разбиение происходит на примерно равные части, то время работы составляет O(nlogn). В худшем случае, если размеры частей сильно отличаются, время разбиения пропорционально O(n2) и снижается к эффективности метода сортировки вставками. В среднем случае, когда на последовательных рекурсиях получаются и худшие и лучшие разбиения, асимптотическая оценка эффективности быстрой сортировки совпадают с оценкой для наилучшего случая, то есть O(n*logn). Вероятность удачного выбора равна 1/n.

Метод имеет и недостатки: он неэффективен для небольших n. Алгоритм не любит упорядоченные массивы. Еще одно неприятное свойство – это проблема глубины рекурсии. Как известно, вызов функции образует в системном стеке кластер, в котором сохраняются точка возврата из функции, входные параметры функции, локальные переменные. Для больших файлов глубина рекурсии может быть значительной, особенно в наихудшем случае. То есть количество кластеров в стеке колеблется от logn до n. Это может привести к переполнению стека и отказу системы. Поэтому предлагают итеративную версию быстрой сортировки.

Итеративный вариант. It_QSort (A, n).

Итеративный алгоритм использует собственный стек разбиений. На каждом этапе возникают две следующих части. Только к одной части можно приступить сразу же, другая же заносится в стек. Каждая часть запоминается в стеке в виде левого и правого индекса. Часть, помещенная в стек первой будет в дальнейшем выбрана из стека последней. С расчетом на худший случай размер стека должен быть равным 2n.

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

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

Еще один способ поиска разделяющего элемента близкого к медиане известен, как метод медианы трех, когда в качестве граничного используется средний из трех случайно выбранных элементов массива. Этот метод существенно снижает возникновение вероятности худшего случая, поскольку вероятность выбора сразу двух наименьших или наибольших значений существенно ниже вероятности выбора одного наименьшего или наибольшего значения. Например, в качестве трех элементов можно взять первый, последний и серединный элементы в массиве A[l…r], то есть A[l], A[r], A[(l+r)/2].

Есть способ точного определения медианы. Хоор предложил другой способ поиска медианы, использующий ту же схему просмотра элементов, которая используется в алгоритме разбиения при быстрой сортировке. Find_median (A, n, k).

Сначала применяется разделение относительно выбранного значения A[k]. Получаются значения индексов i и j такие, что: 1) A[h] x для hi; 3) i

Возможны три варианта:

  1. x слишком мало. В результате искомое значение ищется в большей правой части

  2. x слишком велико и наоборот левая часть содержит искомое значение.

  3. k лежит в интервале j

Процесс разбиения продолжается до появления случая 3. В среднем каждое разбиение уменьшает размер следующего просматриваемого подмассива. Таким образом, на поиск медианы потребуется (n + n/2 + n/4 +…+ 1 = 2n) шагов. Но в худшем случае этот метод дает O(n2) шагов. Его не следует использовать для небольших массивов.

7. Алгоритмы нисходящей и восходящей сортировки слиянием. Эффективность алгоритмов.

Сортировка слиянием многим похожа на метод быстрой сортировки и также относится к алгоритмам типа O(n*logn). Производительность сортировки слиянием лежит между производительностью пирамидальноой и быстрой сортировки. В отличие от пирамидальной и быстрой сортировок, метод сортировки слиянием ведет себя стабильно, поскольку он не зависит от перестановок элементов в массиве. Достоинством сортировки слиянием является то, что он удобен для структур с последовательным доступом к элементам. Этот метод, прежде всего, используется для внешней сортировки. Но метод имеет и недостатки. Он требует дополнительной памяти по объему равной объему сортируемого файла.

Сортировку слиянием можно проиллюстрировать примером: 44 55 12 42 94 18 06 67.

Разобьем на первом шаге файл на два файла:

44 55 12 42 и 94 18 06 67.

Объединим эти два файла снова в один файл:

44 94 18 55 06 12 42 67.

Снова разобьем файл и объединим пары в четверки:

44 94 18 55 и 06 12 42 67.

Слияние: 06 12 44 94 18 42 55 67.

Разобьем файл и объединим четверки:

06 12 44 94 и 18 42 55 67.

Слияние: 06 12 18 42 44 55 67 94.

Итак, основной операцией является слияние. При слиянии требуется дополнительная память для размещения файла, образующегося при слиянии. Операция линейно зависит от количества элементов в объединяемых массивах. В общем виде можно предположить, что сливаемые файлы имеют разную размерность: A[1…n], B[1…m]. При слиянии образуется третий массив C[1…n+m]. Merge (A, n, B, m, C). Такая операция называется двух путевым слиянием.

Нисходящая сортировка слиянием. Merge_Sort (A, l, r, C). Merge (A, n, B, m, C). Merge (A, l, m, r, C).

Эта сортировка является рекурсивной операцией, которая делит файл пополам и выполняет по рекурсии сортировку обеих половин.

Рекурсия ограничена снизу размером разделяемого файла, равным 1. Каждый рекурсивный вызов делит файл пополам. В случае если размер файла кратен 2, получается полное, сбалансированное дерево рекурсии.

Если n не кратно 2, то дерево получается несбалансированным, но все равно его высота оценивается logn.

Восходящая сортировка слиянием. It_Merge_Sort (A, n, C).

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

Итеративный алгоритм сортировки слиянием полностью исключает первоначальное разделение массива на части, и сразу начинает выполнять слияние частей из 1-ого элемента, 2х, 3х и т.д.

Итак, сортировка слиянием так же, как и пирамидальная и быстрая сортировки имеют оценку эффективности O(nlogn). Она превосходит по быстродействию пирамидальную сортировку, но уступает почти в два раза быстрой сортировке. Но у нее есть превосходство перед быстрой сортировкой – устойчивость.

8. Алгоритм поразрядной сортировки MSD. Эффективность алгоритма.

Применяется с составным ключом большой длины (напр., телефонный номер – код города, атс…). Будем называть составной код ключом. Ключ – любая система счисления.

Алгоритмы поразрядной сортировки (radix sort) рассматривают ключи сортируемых элементов как числа с основанием R и работают с отдельными цифрами чисел. При побайтовом рассмотрении ключей, если ключами являются десятичные числа, то R=10, при символьных ключах R=128 или R=256. При побитовом рассмотрении ключей R=2.

MSD (Most Significant Digit radix sort). MSD_Sort (A, l, r, d, C). O(n).

Является рекурсивной и ее ход во многом аналогичен быстрой сортировке. Алгоритм заключается в том, что при очередном проходе элементы исходного массива помещаются в R массивов (раскладываются по R «корзинам») в зависимости от значения младшей цифры ключа. При R=10 ключи, начинающиеся с 0, окажутся в первом массиве, начинающиеся с 1 – во втором и т.д., т.е. потребуется 10 дополнительных массивов «корзин». Далее данные, находящиеся в каждой «корзине», раскладываются по значениям второй цифры и т.д., пока не будут рассмотрены все цифры ключей и пока размер части больше некоторого порогового значения размера корзины m. Очевидно, что сколько бы проходов ни сделали, общее число сортируемых элементов остается постоянным, а «корзины» будут содержать разное количество элементов. Поэтому одного дополнительного массива того же размера, что и исходный, было бы достаточно и в нем можно было бы разместить все «корзины». Однако размеры «корзин» определяются только в процессе очередного прохода, поэтому, видимо, наиболее подходящим способом реализации «корзин» будет применение цепных списков, а не массива. Для улучшения сортировки для малых «корзин» (m>1) следует применять элементарную сортировку.

9. Алгоритм поразрядной сортировки LSD. Эффективность алгоритма.

Применяется с составным ключом большой длины (напр., телефонный номер – код города, атс…). Будем называть составной код ключом. Ключ – любая система счисления.

Алгоритмы поразрядной сортировки (radix sort) рассматривают ключи сортируемых элементов как числа с основанием R и работают с отдельными цифрами чисел. При побайтовом рассмотрении ключей, если ключами являются десятичные числа, то R=10, при символьных ключах R=128 или R=256. При побитовом рассмотрении ключей R=2.

LSD (Least Significant Digit radix sort). LSD_Sort (A, n, C). O(n).

Frame5

Использует разделение ключей по «корзинам», но цифры выбираются справа налево от младшей (d) к старшей. Алгоритм нерекурсивный. После распределения ключей по младшей цифре, опять выполняется LSD-сортировка в пределах всего массива. Последующие этапы нарушают порядок ключей, и, тем не менее, результат правильный.

Несмотря на высокую оценку эффективности, алгоритм имеет недостатки, которые не позволяют считать его универсальным. Например, для поразрядной сортировки строк, состоящих из английских прописных букв, необходимо предусмотреть 27 групп (пробел и ост. буквы). Если исходный набор данных состоит из n строк, каждая группа должна вмещать n строк. Для больших значений n, если входные данные и результат хранятся в массивах, это требование становится невыполнимым. Однако применение связных списков позволяет сэкономить память. Таким образом, этот вид сортировки больше походит для упорядочения связанных списков, а не массивов.

10. Стек и очередь, общая характеристика, формы представления и операции.

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

Стек.

Это такой последовательный список переменной длины, включение и исключение элементов из которого выполняется только с одной стороны стека, называемого вершиной стека. Выборка элементов осуществляется в порядке, обратном их засылке (LIFO – Last Input – First Output). Это статическое или динамическое множество.

Форма представления: 1) массив: top – показывает на первую свободную ячейку, в которую можно поместить новый элемент, -это точки доступа к элементам; 2) односвязная структура.

Операции: 1) создание стека (конструктор: создание массива или пустого списка); 2) включение элемента в стек push(S, место) (если мест нет, push вернет overflow); 3) удаление элемента из стека (если пусто pop вернет underflow); 4) извлечение данных pop(S) (без удаления самого элемента, указывается номер элемента от вершины); 5) уничтожение стека (освобождение динамической памяти, деструктор); 6) опрос размера; 7) поиск search(S).

Очередь.

Это динамически изменяемый упорядоченный набор элементов. Добавление элементов в очередь производится с одного конца (хвост очереди), а выборка – с другого (голова) в соответствии с правилом FIFO (First In – First Out). Такая очередь является простой очередью без приоритетов. В очередях с приоритетами, более приоритетные элементы включаются ближе к голове очереди, выборка осуществляется с головы очереди.

Форма представления: 1) массив (для статической очереди; это последовательность, замкнутая в кольцо). В момент создания очереди front (первый элемент) = tail (последний элемент) = 0. Так же есть overflow (front = (tail+1) mod n) и underflow (front = tail). 2) односвязная структура.

Операции: 1) создание очереди (конструктор: создание массива или пустого списка); 2) включение нового элемента в очередь (1. очередь заполнена – возврат признака переполнения. 2. в очереди единственный элемент – выбрать элемент и установить указатели в начальное состояние. 3. очередь заполнена частично – выбрать элемент с головы очереди с учетом кольцевой организации, скорректировать указатель головы.) O(log2n); 3) выборка элемента из очереди (если пусто pop вернет underflow) O(1); 5) освобождение очереди (освобождение динамической памяти, деструктор).

Очередь с приоритетами.

Обеспечивает извлечение из очереди элемента с мин. или макс. приоритетом. Как правило, строится на базе массивов, в которых элементы хранятся по схеме через упорядоченные дерево или пирамиду (частично упорядоченное дерево). Добавление нового элемента – сначала в конец очереди, затем size+1, затем просеивание вверх/вниз. При удалении элемент извлекается из корня пирамиды, а на его место записывается самый правый элемент нижестоящего слоя. После этого элемент просеивается по пирамиде вниз, пока не займет правильного положения или не достигнет нижнего слоя.

Высота дерева h = log2n = количество узлов. Наиболее часто пирамида хранится в массиве, элементами которого является пара: приоритет и данные (p, data). Для пирамиды фиксируется индекс последнего элемента. Enqueue (Q, p, data). Dequeue (Q).

Деки.

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

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

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

11. Список, общая характеристика, формы представления и операции.

Списком называется упоря-доченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения и доступа к значению по номеру позиции. Список, отражающий отношения соседства между элементами, называется линей-ным. Длина списка равна числу элементов, содержащихся в списке, список нулевой длины называется пустым списком. Линейные связные списки являются простейшими динамическими структурами данных. Графически связи в списках удобно изображать с помощью стрелок. Если компонента не связана ни с какой другой, то в поле указателя записывают значение, не указывающее ни на какой элемент. Такая ссылка обозначается специальным именем - nil.

На рис. приведена структура односвязного списка. На нем поле INF - информационное поле, данные, NEXT - указатель на следующий элемент списка. Каждый список должен иметь особый элемент, называемый указателем начала списка или головой списка, который обычно по формату отличен от остальных элементов. В поле указателя последнего элемента списка находится специальный признак nil, свидетельствующий о конце списка.

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

Форма представления: 1) массив (статический и динамический (надежный)); 2) связанная структура (список на базе массива (в качестве ссылок используются индексы)).

Список на базе массива (если задан предельный размер списка). Поиск – О(1) - достоинство; вставка/удаление – О(n) – недостаток.

Insert (L, v, n). Односвязный список. List_Insert (L, v, n).

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

Кольцевой список с барьерным (фиктивным) элементом. Barier_List_insert (L, v, n). Недостаток – ограниченность массива. Достоинство – 1) гибкая структура без трудоемких перестроек (сдвигов); 2) нет динамического распределения памяти.

Операции: 1) создание списка; 2) уничтожение списка; 3) печать списка; 4) копирование списка; 5) упорядочение списка; 6) поиск элемента; 7) вставка элемента; 8) удаление элемента.

12. Бинарное дерево поиска. Алгоритмы поиска, вставки и удаления элементов. Эффективность алгоритмов.

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

BST_Search (t, k).

BST_Insert (t, k, data).

BST_Delete (t, k).

Производительность операций вставки, поиска и удаления в среднем пропорциональна О(log n). Но BST-дерево в худшем случае вырождается(когда ключи поступают в дерево в порядке возрастания или убывания). В этом случае сложность операций оценивается как О(n).

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

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

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

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

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

13. Рандомизированное дерево поиска. Алгоритмы вставки и удаления элементов в рандомизированном дереве. Эффективность операций.

Rand_BST_Insert(t, k, data). Rand_BST_Delete(t, k, deleted) + Rand_BST_JoinLR(a, b). O(logn).

При построении рандомизированного дерева основное исходное положение заключается в том, что любой элемент может с одинаковой вероятностью быть корнем дерева. Причем это справедливо и для поддеревьев рандомизированного дерева. Поэтому при включении нового элемента в дерево, случайным образом выбирается включение элемента в качестве листа, или в качестве корня. Вероятность появления нового узла в корне дерева или поддерева определяется, как 1/(n+1), где n – число узлов в дереве или поддереве. То есть дерево выглядит так, будто элементы поступали в случайном порядке. Поскольку принимаемые алгоритмом решения являются случайными, то при каждом выполнении алгоритма при одной и то же последовательности включений будут получаться деревья различной конфигурации. Таким образом, несмотря на увеличение трудоемкости операции включений, за счет рандомизации получается структура дерева, близкая к сбалансированной. Поиск в рандомизированном дереве ведется по стандартному алгоритму поиска в BST-дереве. Благодаря сбалансированности дерева в среднем поиск в рандомизированном дереве оценивается О(log n) и более эффективен в среднем, чем в BST-дереве.

Операция удаления и объединения двух деревьев в рандомизированном дереве также работает случайным образом. В основе удаления лежит замена удаляемого узла корнем его объединенных поддеревьев. В рекурсивное объединение поддеревьев также внесена случайность. Объединение ведется на базе того поддерева, у которого большее значение n.

При объединении левого поддерева из n-узлов с правым поддеревом из m-узлов корнем объединенного дерева будет корень левого поддерева с вероятностью n/(n + m) или корень правого поддерева с вероятностью m/(m + n).

Недостатком рандомизированной вставки являются затраты на генерацию случайных чисел в каждом узле. Чтобы минимизировать эти затраты, можно вместо системного генератора случайных чисел использовать числа, которые не являются совершенно случайными, но для генерации требуют небольших затрат. Например, функцию rand() можно заменить проверкой 111% n=3 для принятия решения о вставке в корень.

Второй недостаток – необходимость поддержки в структуре узлов рандомизированного дерева дополнительного параметра n[t], значение которого равно сумме параметров n левого и правого поддеревьев, увеличенной на 1. Этот параметр используется и корректируется операциями вставки и удаления элементов, а также дополнительными операциями поворотов узлов. Но т.к. этот параметр необходим в дереве и по другим причинам, например, для операции Select(), то поддержка этого параметра для рандомизированной вставки не является решающим недостатком.

14-15. AVL – дерево поиска. Алгоритм вставки и удаления элементов в AVL – дереве. Эффективность операций в AVL-дереве.

Алгоритм построения сбалансированного дерева был предложен Адельсоном-Вельским и Ландисом в 1962 г. Является сбалансированным только тогда, когда для каждого узла высота его двух поддеревьев различается не более чем на 1 (hrhl 1). Вставка и удаление – как в BST-дереве. Операции вставки и удаления элементов могут привести к изменению высот поддеревьев в узлах, лежащих на пути к вставленному или удаленному элементу. Поэтому после вставки или удаления элемента выполняется восходящая проверка и корректировка критериев сбалансированности этих узлов. Если в каком-либо узле обнаружено, разность высот поддеревьев стала больше единицы, выполняется поворот этого узла для выравнивания высот поддеревьев. В AVL-дереве используются четыре видов поворотов в зависимости от конфигурации поддеревьев узла с нарушенным критерием сбалансированности.

Если узел с нарушенным критерием перевешивает вправо, а его правый сын – влево, то RL.

Если узел с нарушенным критерием перевешивает влево, а его правый сын – вправо, то LR.

LR_AVL (t).

Если узел с нарушенным критерием перевешивает влево, а его правый сын – влево, то R.

Если узел с нарушенным критерием перевешивает вправо, а его правый сын – вправо, то L.

R_AVL (t).

Рассмотрим операцию включения в сбалансированное дерево нового узла. Пусть дан корень a с левым и правым поддеревьями L и R. Предположим, что новый узел включается в L, вызывая увеличение его высоты на 1. Возможны 3 случая после включения:

1. если hl=hr до включения, то L и R становятся неравной высоты, но критерий сбалансированности не нарушен.

2. если hl


3. если hl>hr до включения, то критерий сбалансированности нарушается, и дерево нужно перестраивать.

Вставка. AVL_Insert (t, k, data, &h_up).

В дерево на рисунке узлы с ключами 9 и 11 можно вставить без балансировки. Включение 9 ухудшает сбалансированность поддерева с корнем 10, но не нарушает критерий сбалансированности (случай 1). В поддереве с корнем 8 сбалансированность даже улучшается (случай 2). Но включение узлов 1, 3, 5 или 7 требует балансировки в поддереве с корнем 8.

Вращения.

Возможны лишь перемещения по вертикали узлов и поддеревьев. Их относительное горизонтальное расположение остается неизменным. Это обеспечивает сохранение упорядоченности узлов в перестроенном дереве.

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

  1. Поиск места включения нового узла в каком – либо листе.

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

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

Математический анализ этого алгоритма сложен. Эмпирические проверки этого алгоритма показывают, что ожидаемая высота сбалансированного дерева равна h=log(n)+0.25. То есть AVL-деревья ведут себя как идеально сбалансированные полные деревья.

Удаление.

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

Удаление элементов также имеет стоимость О(log n). Но если включение может вызвать один поворот, удаление может потребовать повороты в каждом узле пути поиска при обратном ходе рекурсии.

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

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

16. 2–3–дерево поиска. Алгоритм вставки и удаления элементов в 2–3–дереве. Эффективность операций в 2–3–дереве.

П

low2 low3

редложены Хопкрофтом в 1973 г. Соответствует полному идеально сбалансированному BST-дереву (все пути от корня до листьев одинаковы), если все его узлы являются 2-узлами. В этом случае его высота равна log2n. С другой стороны, если все узлы в 2-3-дереве – 3-узлы, то высота равна log3n. Таким образом, длина прохода от корня дерева к листьям с элементами и, следовательно, трудоемкость операций лежит в пределах от О(log3n) до О(log2n). Точка роста дерева – корень.

Состоит из листьев (для данных, имеют сыновей) и внутренних узлов. Для организации поиска элементов внутренние узлы дерева содержат дубликаты наименьшего ключа элемента во 2-ом поддереве и наим. ключа в 3-ем (если у узла есть 3-ий сын). Эти ключи служат границами поиска нужного листа с заданным ключом. Поиск начинается с корня. Если ключ меньше, чем минимальный элемент у второго сына (low2), то выбирается первый сын. Если узел имеет двух сыновей и ключ > low2, то выбирается второй сын. Если ключ > low2, но нет третьего сына, тот выбирается второй сын. Если есть третий сын и ключ < low3, то выбирается второй сын. Если есть третий сын и ключ  low3, то выбирается третий сын. Таким образом, если заданный ключ = ключу в листе, то данные найдены.

Вставка. T23_Insert(root,k,data)+Insert1(root,lt,&tdown,&ldown). T23_Insert(t,x,tup,lup).

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

Удаление. T23_Delete (root, k).

Операция удаления может привести к тому, что у родительского узла останется один сын. Это может вызвать слияние родительского узла с соседним внутренним узлом. Процесс слияния также может достичь корня и вызвать его замену на узел, образованный в результате слияния двух его сыновей. 1) Если при удалении узла k у родителя (узла t) останется один сын и родитель является корнем, то новым корнем становится его единственный сын старого корня. 2) Если t не является корнем, то проверяются его братья. 3) Если у какого-либо брата есть 3 сына, то узлу t передается один из сыновей брата. Брат и узел t становятся 2-узлами. 4) Если у братьев нет трех сыновей, то единственный сын узла t передается брату. Брат становится 3-узлом, узел t уничтожается. В этом случае у родителя узла t удаляется сын t и ситуация повторяется для родителя узла t.

При создании или удалении нового корня одновременно изменяется длина всех путей от корня к листьям и 2-3 дерево остается идеально сбалансированным.

17. 2-3-4-дерево и красно-черное дерево. Моделирование операций 2-3-4-дерева в красно-черном дереве.

Существует еще одна разновидность сбалансированных деревьев, аналогичных по алгоритмам вставки и удаления элементов 2-3-деревьям. Это 2-3-4 – деревья. Узлы содержат 2, 3 или 4 сына. Но эти элементы коллекции хранятся не только в листьях, но и во внутренних узлах 2-3-4-дерева. Элементы во внутренних узлах одновременно служат границами поиска в дереве. Данные хранятся во всех узлах дерева. Все узлы имеют один тип. В 2-3-4 – дереве узлы обладают еще большей гибкостью, чем в 2-3- дереве и соответственно количество разделений и слияний узлов в нем меньше, благодаря наличию 4-узлов. Точкой роста 2-3-4-дерева также является корень и, следовательно, 2-3-4-дерево является идеально сбалансированным. Трудоемкость операций: от О(log4n) до О(log2n).

Алгоритм поиска ничем не отличается от поиска в 2-3-дереве кроме того, что здесь в 4-узлах рассматриваются 4 интервала ключей для выбора одного из сыновей для последующего поиска. Поиск может закончиться на любом узле, а не только на листе, как в 2-3- дереве.

В 2-3-4-дереве происходит нисходящее расщепление (на пути от вершины вниз) узлов при вставке. Т.е., если при выборе сына некоторый узел является 4-узлом, то он расщепляется на два 2-узла и дальнейшая вставка идет через один из 2-узлов.

До сих пор не удалось точно проанализировать аналитически производительность 2-3-4 – деревьев. Но эмпирически показано, что для балансировки 2-3-4 – деревьев используется очень мало разделений. Худший случай 2-3-4 – дерева оценивается высотой log2n, но на практике высота не приближается к этому значению.

Ввиду сложности структуры узлов 2-3-4-дерева, алгоритмы операций для него становятся громоздкими и непроизводительными: накладные расходы, связанные с манипулированием сложными структурами узлов, рассмотрением различных сочетаний 2-, 3- и 4-узлов делают алгоритмы медленнее BST–деревьев. Поэтому непосредствен-ная реализация 2-3-4-дерева редко используется. Взамен предла-гается красно-черное дерево (RB-дерево), воспроизводящее структуру и алгоритмы 2-3-4-дерева. В RB-дереве 2-,3-,4- узлы заменяются группами 2-узлов.

Для различения отдельных узлов 2-3-4-дерева в группах принята раскраска узлов. Корневой узел группы имеет черный цвет (B), внутренние узла окрашиваются в красный цвет (R). Таким образом формируется двоичный эквивалент 2-3-4-дерева – RB-дерево.

  1. Каждый узел либо R, либо B.

  2. Каждый лист B.

  3. если узел R, то оба сына – B.

  4. Все пути вниз (от корня к листьям) содержат одинаковое число B узлов (одинаковая B высота).

  5. Корень черный.

Начальная стадия операция вставки и удаления выполняется точно так же, как и в BST-дереве. Узел с новым элементом вставляется в лист дерева и всегда окрашивается в красный цвет. Это может привести к нарушению третьего свойства структуры RB-дерева, если родитель нового узла тоже красный. При удалении узла из RB-дерева может быть нарушено четвертое свойство, если удаленный узел был черным. Алгоритмы операций вставки и удаления восстанавливают свойства RB-дерева путем восходящих поворотов и перекрасок узлов, лежащих на пути вставки и удаления. Тем самым достигается сбалансированность RB-дерева. Средняя трудоемкость операций – O(logn). Необходимо отметить еще одну особенность RB-дерева – наличие фиктивного, черного узла. В терминальных узлах RB-дерева вместо значения nil хранится адрес этого фиктивного узла. Узел введен для упрощения программирования итеративного алгоритма удаления.

В RB-дереве алгоритм поиска соответствует стандартному алгоритму поиска в BST-дереве и поэтому работает быстрее, чем в 2-3-4-дереве и быстрее, чем в BST-дереве. Дополнительные затраты на балансировку встречаются только тогда, когда новый элемент подключается к 4-узлу. Поскольку число 4-узлов невелико, то и затраты на балансировку невелики.

Рассмотрим преобразования в RB-дереве, эквивалентные вставке в 2-3-4-дерево. Новый элемент, то есть новый узел, как и в BST-дереве подключается в качестве листа к терминальному узлу. При этом связь, подключающая новый узел к дереву всегда красная, так как в результате подключения образуется как минимум 3-узел, то есть узел нового элемента всегда красный.

3) Подключение к 4 узлу должно вызвать разделение 4-узла на два 2-узла. Рассмотрим схему нисходящего разделения 4-узла, лежащего на пути поиска при вставке нового элемента.

3a)

3b)

3c)

3d)

Два последних случая 3с) и 3d) отличительны тем, что 4-узел подключен к красному узлу 3-узла. Разделение 4-узла приво-дит к образованию двух 2-уз-лов и на более высоком уров-не– к образованию структуры-__3-узла. В дереве образуются две последовательные R-связи. Можно преобразовать такое неправильное дерево так, чтобы эти две связи вели из одного узла, что соответствует 4-узлу, путем вращений. Если две последовательные R-связи ориентированы одинаково (3с), то выполняем ротацию корня неправильного дерева и изменяем цвета узлов. Если две R-связи ориентированы по-разному (3d), то сначала сводим связи к одинаковой ориентации (ротация верхнего R-узла), а затем выполняем ротацию, аналогичную случаю 3с).

18. Рекурсивный и итеративный алгоритмы вставки в красно-черное дерево.

RB_Insert (root. x) + RB_Insert1 (t, x, S). It_RB_Insert (root, x) + It_L (root, t).

Алгоритм вставки в красно-черное дерево гарантирует логарифмическую эффективность для поисков и включений. В худшем случае, когда путь поиска состоит из чередующихся 3- и 4-узлов, требуется 2logn+2 шагов. Анализ и моделирование RB-деревьев с n узлами, построенных из случайных ключей, показали, что эффективность имеет оценку О(1.02*logn). В этом смысле RB-деревья оптимальны для практического применения и часто включаются в библиотеки. При реализации алгоритма часто используется альтернативный подход при рассмотрении RB-дерева, как дерева с определенными структурными свойствами. При этом игнорируется соответствие с 2-3-4- деревом.

RB-дерево, как структура обладает следующими RB-свойствами: 1) каждый узел либо R, либо B; 2) каждый лист B; 3) если узел R, то оба сына – B; 4) все пути вниз (от корня к листьям) содержат одинаковое число B узлов (одинаковая B высота); 5) корень черный.

Начальная стадия операция вставки и удаления выполняется точно так же, как и в BST-дереве. Узел с новым элементом вставляется в лист дерева и всегда окрашивается в красный цвет. Это может привести к нарушению третьего свойства структуры RB-дерева, если родитель нового узла тоже красный. При удалении узла из RB-дерева может быть нарушено четвертое свойство, если удаленный узел был черным. Алгоритмы операций вставки и удаления восстанавливают свойства RB-дерева путем восходящих поворотов и перекрасок узлов, лежащих на пути вставки и удаления. Тем самым достигается сбалансированность RB-дерева.

Поскольку управление стеком в RB-дереве становится довольно сложным, то вместо стека введем в структуру каждого узла указатель на родителя. Итак, узел RB-дерева содержит, помимо данных, 3 указателя на сыновей и родителя (p[t]), и цвет color[t].

Ссылка nil всегда считается черным псевдолистом. Часто для удобства программирования nil заменяется ссылкой на общий для всех фиктивный черный узел-лист.

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

Случай 1: Если дядя нового узла y-красный, то восстановление свойства в области включения сводится к перекраске родителя и дяди в черный цвет, а деда – в красный. Перекраска не меняет черной высоты дерева.

Но теперь может быть нарушено 3-е свойство выше по дереву.

Случай 2, 3 - у красного узла x-родитель красный, но дядя - черный.

Случай 2: разные ориентации в дереве. Используем левый поворот родителя узла x, чтобы свести случай 2 к случаю 3.

Случай 3: делаем правый поворот деда узла x и перекраску: опущенный дед перекрашивается в красный цвет, а поднятый родитель – в черный цвет.

19. Итеративный алгоритм удаления из красно-черного дерева.

It_RB_Delete (root, k) + RB_FixUp (root, z). О(logn).

Удаление вершины несколько сложнее включения (может быть нарушено 4-ое свойство при удалении черного узла). Для упрощения программирования операции удаления в RB-дерево вводится фиктивный элемент NIL, который будет использоваться вместо ссылок nil в терминальных узлах дерева. Все терминальные узлы, не имеющие сыновей или одного сына, вместо nil имеют ссылку на фиктивный элемент NIL. Фиктивный элемент не содержит ни ключей, ни данных. Используются только ссылки на сыновей и родителя. Цвет фиктивного элемента всегда черный. Благодаря фиктивному узлу все реальные узлы всегда внутренние.

После удаления вызывается дополнительная операция (RB_FixUp), которая восстанавливает нарушенное 4-ое свойство - все пути вниз (от корня к листьям) содержат одинаковое число черных узлов (одинаковая черная высота). Восстановление ведется путем перекрашивания узлов и вращений на пути поиска удаляемого элемента. 1)Если удаляемый узел y-красный, то 4-е свойство RB-дерева не нарушается и операция удаления на этом завершается. 2)Если удалена черная вершина, то выполняется операция RB_FixUp для сына (z) удаленного узла (y). Сыном удаленного узла может быть либо его единственный левый или правый сын, либо фиктивный узел NIL, причем в этот момент p[z] или p[NIL] указывают на родителя удаленного узла y.

RB-дерево, как структура обладает следующими RB-свойствами: 1) каждый узел либо R, либо B; 2) каждый лист B; 3) если узел R, то оба сына – B; 4) все пути вниз (от корня к листьям) содержат одинаковое число B узлов (одинаковая B высота); 5) корень черный.

При удалении черного узла возможны 2 ситуации:

1) нарушение можно компенсировать, пере-красив узел х в черный цвет. Это позволит ликвидировать и нарушение 3-его свойства, если родитель вырезанного узла у – красный.

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

Перестройка учитывает 4 возможных случая, которые могут встретиться на пути:

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

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

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

Сыновья w разно-го цвета. Перекра-сив родителя х в черный цвет, а w – в красный, мы на-рушим свойство 3 для w. Поэтому сделаем сначала правый поворот узла w.

Важно, что правый сын узла w – красный. Перекрашивать нельзя. Левый сын может быть и красным и черным. Опять же действие по схеме случая 1 не годится, т.к. это приведет к нарушению свойства 3. Поэтому произведем вращение влево родителя х. Узел х отдает свою черноту родителю, а правый сын узла w перекрашивается в черный цвет. Узел w берет цвет корня поддерева до поворота. В этом случае происходит полное поглощение излишней черноты и на этом перестройка прекращается.

Операция RB_Delete выполняется за O(logn). Обычно производится не более трех вращений.

20. Хеш – таблицы. Типы и особенности функций хеширования.

Применяются для «словарей». Это множество данных большого объема, в котором преобладает операция поиска. Реже происходит вставка и удаление. Т.е. множество со стабильным размером. Это обычный массив с необычной адресацией, задаваемой хеш-функцией. Хеширование полезно, когда широкий диапазон возможных значений должен быть сохранен в малом объеме памяти, и нужен способ быстрого, практически произвольного доступа. Хэш-таблицы часто применяются в базах данных, и, особенно, в языковых процессорах типа компиляторов и ассемблеров, где они изящно обслуживают таблицы идентификаторов. В таких приложениях, таблица - наилучшая структура данных. Так как всякий доступ к таблице должен быть произведен через хэш-функцию, функция должна удовлетворять двум требованиям: 1) она должна быть быстрой; 2) она должна порождать хорошие ключи для распределения элементов по таблице. Последнее требование минимизирует коллизии (случаи, когда два разных элемента имеют одинаковое значение хеш-функции) и предотвращает случай, когда элементы данных с близкими значениями попадают только в одну часть таблицы. Один из наиболее эффективных способов реализации словаря - хеш-таблица. Среднее время поиска элемента в ней есть O(1), время для наихудшего случая - O(n).

Хеш-функции.

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

Модульнное.

Построение хеш-функции методом деления с остатком состоит в том, что ключу k ставится в соответствие остаток от деления k на m, где m – число возможных хеш-значений. h(k) = k mod m. Например, если m=13, k=100, то h(k)=9. Не рекомендуется m=10P, если ключи – десятичные числа. Тогда уже часть младших цифр полностью определяет хеш-значение. Хорошие результаты получаются, если в качестве m выбирать простые числа, далеко отстоящие от степени двойки. Значения, дающие коллизии при любом М – числа, кратные М, М + 1, …, М + m-1. Пример: плохого М (М1=100 - h1(k)=k mod 100) и хорошего М (М2=101 - h2(k)=k mod 101).

Мультипликативное. Пусть количество хеш-значений равно m. Зафиксируем константу А на интервале 0h(k) = m(k A mod1), где k A mod1 – дробная часть kA. Достоинство метода умножения заключается в том, что качество хеш-функции мало зависит от выбора m. Обычно в качестве m – выбирают степень двойки, т. к. в большинстве компьютеров умножение на m реализуется как сдвиг слова. Метод умножения работает при любом выборе константы А, но некоторые значения А могут быть лучше других. Оптимальный выбор А зависит от того, какого рода данные хешируются. Кнут после исследований заключает, что А (√5 - 1)/2 = 0,6180339887 является довольно удачным. (√5 - 1)/2 = 0,6180339887 – золотое сечение. Если рассмотреть интервал [0…1], на котором лежат значения k A mod 1 (дробная часть k A), то можно заметить, как ведут себя последовательные значения k (+ 0)A mod 1, k (+ 1)A mod 1, k (+ 2)A mod 1 и т.д. Каждая новая точка делит наибольший из интервалов золотым сечением (длина отрезка = сумме двух составляющих отрезков).

Соответственно ведет себя и хеш-функция: h(k) = m(k A mod1) на интервале ключей [0…m-1].

Выбор цифр.

Основана на выборе цифр. Быстро и легко вычисляется, однако не обеспечивает равномерного распределения элементов в таблице. Напр., из идентификационного номера сотрудника 001364825 можно извлечь четвертую и последнюю цифры, образовав число 35 – индекс элемента в таблице. Выбирая цифры из поискового ключа, следует быть осторожным, чтобы не произошло совпадение ключей.

Свертка.

Улучшить хеширование можно с помощью суммирования всех цифр поискового ключа. Напр., можно сложить все цифры числа 001364825 (0+0+1+3+6+4+8+2+5=29). 0  h(ключ)  81. Чтобы модифицировать этот метод или увеличить размер таблицы, можно сгруппировать цифры поискового ключа и складывать группы цифр.

21. Хеш – таблицы с цепочками коллизий и с открытой адресацией. Алгоритмы операций в хеш-таблицах. Методы повторного хеширования в хеш-таблицах с открытой адресацией. Эффективность операций в хеш-таблицах.

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

Каждый элемент хранит указатель на голову списка или NIL. Основная идея при открытом хешировании заключается в том, что потенциальное множество разбивается на конечное число подмножеств. Для m подмножеств, пронумерованных от 0 до m-1 строится хеш-функция h такая, что для любого элемента из исходного множества h(k) принимает целочисленное значение на интервале [0…m]. Значение хеш-функции определяет индекс в массиве указателей Т. Если подмножества примерно одинаковы, то в этом случае списки всех подмножеств должны быть наиболее короткими и средняя длина сегментов будет │U│/ m = α.

Используется массив списков. При хэшировании включаемого ключа получаем место в массиве (фактически попадаем в нужный нам список) и включаем в данный список наши данные(ключ). Графически это может быть проиллюстрированно так: в данном примере размер таблицы = 8. Например, чтобы добавить 11, мы делим 11 на 8 и получаем остаток 3.

Таким образом, 11 следует разместить в списке, на начало которого указывает hashTable[3].

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

Вставка - О(1); поиск - О(α); удаление - О(1). α оптим. = 2-5. 1 < α < 10.

Открытая адресация. Хеш-таблицы с открытой адресацией особенно эффективны, когда максимальные размеры входящего набора данных уже известны. Было доказано, что, когда таблица заполняется более чем на 50 процентов, ее эффективность значительно ухудшается (возрастает количество коллизий). Такие таблицы обычно используются для быстродействующего макетирования (они просты для программирования и быстры) и там, где быстрый доступ (нет связанного списка) приоритетен, а память легко доступна.

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

При открытой адресации порядок просмотра зависит от ключа. К хеш-функции добавляется второй аргумент - номер попытки (нумерация начинается с 0). Хеш-функция имеет вид: h:U*{0,1, …,m-1}→{0,1,…,m-1}. Последовательность проб для данного ключа k имеет вид: <h(k,0), h(k,1),…, h(k,m-1)>. Функция h должна быть такой, чтобы каждое из чисел 0, …, m-1 встречалось ровно один раз.

При поиске элемента с ключом k в таблице ячейки просматриваются в том же порядке, что и при вставке элемента с ключом k. Если встречается ячейка, в которой записан NIL, то это значит, что искомого элемента в таблице нет.

Удаление элемента из таблицы с открытой адресацией не так просто. Если записать на его место NIL, то в дальнейшем нельзя будет найти те элементы, в момент добавления которых это место вошло в число проб и было занято, и из-за этого была выбрана более удаленная позиция. Возможное решение – записывать на место удаленного элемента не NIL, а специальное значение DELETED (“удален”), и при добавлении рассматривать ячейку со значением DELETED, как свободную. При поиске эту ячейку нужно рассматривать, как занятую. Недостаток этого подхода в том, что время поиска может оказаться большим даже при низком коэффициенте заполнения.

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

На практике используются обычно три способа вычисления последовательности проб: линейный, квадратичный и двойное хеширование.

Линейная последоват. проб. h (k, i) = (h`(k) + i) mod m.

Три состояния: занято, свободно, свободно после удаления. У метода очевидный недостаток: он может привести к образованию кластеров – длинных последовательностей занятых ячеек, идущих подряд. Это удлиняет поиск. Недостаток: уходим от О(1) к О(n).

Квадратичная последовательность проб. h (k, i) = (h` (k) + c1i + c2i2) mod m.

h’(k) – хеш-функция; c1 и c2 ≠ 0 – некоторые константы. Номер пробуемой ячейки квадратично зависит от номера попытки. Для того, чтобы использовались все ячейки таблицы, c1 и c2 выбираются не случайно. Как и при линейном методе, вся последовательность проб определяется ключом, т. е. h`(k), поэтому получается m различных перестановок. Однако тенденция к образованию кластеров частично устраняется. Хотя и остается эффект кластеризации в более мягкой форме – образование вторичных кластеров.

Двойное хеширование. h (k, i) = (h`(k) + h’’(k)*i) mod m.

h’(k) – хеш-функция; h'’(k)=k mod (m-1) + 1 – шаг перебора позиций. h'’(k) должна давать любые шаги, зависящие от ключа в пределах таблиццы.

Один из лучших методов открытой адресации. Перестановки индексов, возникающие при двойном хешировании, близки к равномерному хешированию. В отличие от линейного и квадратичного методов при двойном хешировании можно получить при правильном выборе h1 и h2 не m, а 0(m2) различных перестановок, поскольку каждой паре (h1 и h2) соответствует своя последовательность проб. Благодаря этому производительность двойного хеширования близка к той, что получилась бы при равномерном хешировании.

Анализ хеширония с открытой адресацией.

Так же как при анализе хеширования с цепочками стоимость операций с открытой адресацией оценивается в терминах коэффициента заполнения α=n/m. Для открытой адресации α ≤ 1. Если предположить идеальный случай, что хеширование равномерно, ключи выбираются случайным образом и все m! последовательностей проб равновероятны, то математическое ожидание проб при поиске в таблице с открытой адресацией отсутствующего элемента будет 1(1- α). Если α отделен от 1, то поиск отсутствующего элемента будет занимать время О(1). Например, при α = 0.5, среднее число проб будет не больше 1/(1 - 0.5) = 2. Если α = 0.9, то среднее число проб не больше 1/(1 – 0.9) = 10. Точно такую же оценку имеет и математическое ожидание стоимости операции добавления в таблицу. Математическое ожидание(МО) успешного поиска равно 1/α ln (1/1-α). Если таблица заполнена наполовину (α=0.5), то среднее число проб для успешного поиска не превосходит 1.387, а если на 90% - то 2.559.

МО успешного поиска получается усреднением общего числа проб при добавлении каждого элемента. МО общего числа проб равно сумме МО для каждого шага. При добавлении (i+1)-го элемента α = i/m и МО i + 1 = 1/1- αi = 1/(1-i/m) = m/m-i.

Таким образом, общее МО = m ln(m/m-n). Общее МО усредняем , т. е. делим на n: m/n ln(m/m-n) = 1/α ln(1/1-α).

Вставка - О( 1 / (1-α) ); поиск - О( (1/α) * ln( 1/(1+α) ) ); удаление - О(1). 0 < α < 1. α опт. = 0,5.

22-24. Структуры внешнего поиска. Основные принципы организации структур внешнего поиска. Представление хешированного файла, плотного и разреженного индексного файла.

Хранит множества и мультимножества. Множества хранятся во внешней памяти. Для эффективного доступа происходит организация поиска. Элементы – записи постоянной/переменной длины, которые хранятся в последовательном файле. Для поиска отдельных записей используется 1 или несколько ключей. Записи могут быть закреплены по месту положения или незакреплены. Закрепление записей связано с тем, что существуют несколько параллельных систем поиска – каждая подсистема ведет поиск по отдельному ключу. Для избежания перестройки во всех подсистемах, запись не должна изменять свое местоположение, и ее место не должна занимать ни одна запись. Время одного обращения к диску (внешней структуре) значительно превосходит обращение к ОЗУ, поэтому трудоемкость считается в количестве обращений. Принято группировать записи в блоки, страницы. Применяются для файла и для структуры поиска, которая также хранится в файле.

Множество индексов может быть организовано как: 1) хеш-файл (таблица); 2) упорядоченная по ключу последовательность индексов на все записи - плотный индекс; 3) упорядоченная по ключам последовательность индексов, где каждый индекс соответствует первой записи на странице файла с данными – разреженный индексный файл; 4) индекс в виде сильно ветвящейся - В-дерево.

Хеш-файл. организовывается по принципу цепочной хэш-таблицы.

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

Имеется таблица сегментов, содержащая В указателей, по одному на каждый сегмент. Каждый указатель в таблице сегментов представляет собой физический адрес первого блока связного списка блоков для соответствующего сегмента. Сегменты пронумерованы от 0 до В-1. Хеш-функция h отображает каждое значение ключа в одно из целых чисел от 0 до В-1. Если х –ключ, то h(x) является номером сегмента, который содержит запись с ключом х (если такая запись вообще существует). Блоки, составляющие каждый сегмент, образуют связный список. Таким образом, заголовок i-ого блока содержит указатель на физический адрес (i+1)-ого блока. Последний блок сегмента содержит в своём заголовке NIL-указатель. Элементы, хранящиеся в одном блоке сегмента, не требуется связывать друг с другом с помощью указателей - связывать между собой нужно только блоки. Если размер таблицы сегментов невелик, её можно хранить в основной памяти. В противном случае ее можно хранить последовательным способом в отдельных блоках. Если нужно найти запись с ключом х, вычисляется h(x) и находится блок таблицы сегментов, содержащий указатель на первый блок сегмента h(x). Затем последовательно считываются блоки сегмента h(x), пока не обнаружится блок, который содержит запись с ключом х. Если исчерпаны все блоки в связном списке для сегмента h(x), приходим к выводу, что х не является ключом ни одной из записей. Среднее количество обращений к блокам α= n/bk, если n-количество записей, блок содержит b записей, а k соответствует количеству сегментов.

Плотный индекс.

Индексный файл, который фиксирует в себе каждую запись. В сортировки файла данных не нуждается, т.к. при вставке новый элемент просто включается в конец файла данных с возвратом файлового указателя на это место. Состоит из 2-х файлов – данные (не сгруппированы по страницам) и индексы (всех записей, упорядочены по ключам и страницам, сгруппированы). Применяется правило бинарного поиска страницы, содержащей индекс с заданным ключом (m=(l+5)/2 ; km1). При использовании такой организации плотный индекс служит для поиска в основном файле записи с заданным ключом. Если требуется вставить новую запись, отыскивается последний блок основного файла и туда вставляется новая запись. Если последний блок полностью заполнен, то надо вставить новый блок из файловой системы. Одновременно вставляется указатель на соответствующую запись в файле плотного индекса. Чтобы удалить запись, в ней просто устанавливается бит удаления и удаляется соответствующий вход в плотном индексе (возможно, устанавливая и здесь бит удаления).

Разреженный индекс.

Применяется для уменьшения количества страниц. Для этого они сначала сортируются по ключам. Организованы страни-цы и индексы (ключ и указатель). Есть предельное количество индексов. Файл разреженного индекса значительно короче файла плотного. Файл с данными сортируется по ключу и формируется отсортированный файл с упорядоченными записями, сгруппированными в страницы. Причем на каждой странице оставляется резерв.

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

Однако, перед расщеплением можно передать в резерв лишние индексы одной из последней страниц.

25. B-дерево. Представление B-дерева. Алгоритмы вставки и удаления в Б-дереве. Эффективность операций в Б-дереве.

Cбалансированные деревья, удобные для хранения информации на дисках. Характерным для Б-деревьев является их малая высота h. Представление информации во внешней памяти в виде Б-дерева стало стандартным способом в системах баз данных. В Б-дереве узел может иметь много сыновей, на практике до тысячи. Количество сыновей (максимальное) определяет степень Б-дерева. Узел х, хранящий n[x] ключей, имеет n[x]+1 сыновей. Хранящиеся в х ключи служат границами, разделяющими всех потомков узла на n[x]+1 групп. За каждую группу отвечает один из сыновей х. При поиске в Б-дереве искомый ключ сравнивается с границами в узле х и выбирает один из n[x]+1 путей для дальнейшего поиска. Обычно насчитывается миллионы и миллиарды элементов. При обработке в ОП хранится только часть элементов, обрабатываемых в данный момент. Узлы Б-дерева содержат не один элемент, а группу элементов размером в 1 сектор.

Чтобы уменьшить количество операций чтения-записи на диск при поиске элемента в Б-дереве, нужно максимально уменьшить его высоту. Для этого степень Б-дерева делается максимальной. Типичная сте-пень – (50-2000). Она зависит от соотношения размера сектора и размера отдельного элемента. Например, Б-дерево степени 1000 и высоты 2 может хранить более миллиарда ключей. Узел-корень дерева обычно всегда хранится в ОП, для доступа к остальным ключам требуется всего 2 операции чтения с диска.

Представление Б-дерева.

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

Кроме того узел x хранит:

  1. n[x] – текущее количество ключей, хранящихся в узле;

  2. сами ключи в неубывающем порядке key1[x] ≤ key2[x] ≤ … ≤ keyn[x][x];

  3. булевый признак leaf[x] истинный, если узел – лист;

  4. p[x] = n[x]+1 указателей p1[x], p2[x], …, pn[x]+1[x] на сыновей. У листьев эти поля не определены.

Отдельный узел хранится на отдельной странице файла. Ключи key1[x], …, keyn[x][x] служат границами, разделяющими значения ключей в поддеревьях: K1 ≤ key1[x] ≤ key2[x] ≤ … ≤ keyn[x][x] ≤ Kn[x]+1, где Ki – множество ключей, хранящихся в поддереве с корнем pi[x].

Все листья находятся на одной глубине, равной высоте дерева h. Число ключей, хранящихся в одном узле, ограничено сверху и снизу единым для Б-дерева числом t, где t – минимальная степень дерева (t≥2) – t ≤ n ≤ 2t; 500 ≤ t ≤ 2000. Каждый узел, кроме корня содержит минимум t-1 ключей и t сыновей. Если дерево не пусто, то в корне должен храниться хотя бы один ключ. В узле хранится не более 2t-1 ключ, и внутренний узел имеет не более 2t сыновей. Узел, хранящий 2t-1 ключей, называется полным.

Если t=2, то у каждого внутреннего узла может быть 2, 3, 4 сына и такое дерево называется 2-3-4 деревом.

Высота дерева: . Т.е. временная сложность операций для Б-дерева оценивается как О(logt n).

Считаем, что корень дерева всегда находится в ОП и операция Disk_Read для корня не выполняется. Но когда корень изменяется, его нужно сохранять на диске. Все узлы, передаваемые операциям, как входные параметры, уже считаны с диска.

Поиск в Б-дереве. B_Tree_Search(x, k).

Рассмотрим рекурсивную операцию B_Tree_Search, параметрами которой является указатель х на корень поддерева и ключ k искомого элемента. Операция вызывается первоначально для корня дерева B_Tree_Search(root[T], k). При нахождении в дереве элемента с заданным ключом операция возвращает пару (y, i), где у – узел Б-дерева, i – порядковый номер указателя, для которого keyi [y]=k. Иначе операция возвращает nil. При проходе по Б-дереву число обращений к диску О(h). Цикл while занимает основное время вычислений и занимает время О(th).

Создание пустого Б-дерева. B_Tree_Create(T).

Чтобы построить дерево, сначала создается пустое дерево с помощью операции B_Tree_Create, а затем в него включаются элементы с помощью операции B_Tree_Insert. Обе эти операции используют вспомогательную операцию Allocate_Node, которая выделяет на диске место для нового узла. Эта операция занимает О(1), т.к. выполняется одно обращение к диску, времени и не использует операцию Disk_Read.

Операция разбиения узла Б-дерева. B_Tree_Split (x, i, y).

Ключевым моментом добавления эл-та в дерево является разбиение полного узла у с (2t-1) ключами на два узла, имеющие по (t-1) элемен-тов в каждом. При этом ключ-медиана отпра-вляется к роди-телю узла y – x. Этот ключ ста-новится разделителем двух полученных узлов. Ключ-медиана вставляется в упорядоченное множество ключей узла х. Элементы с большими, чем медиана ключами, переходят в новый узел z. Входными параметрами операции является неполный узел х, число i и полный узел y (y = pi [x]).

Добавление в Б-дерево. B_Tree_Insert (T, k, data). B_Tree_Insert_Nonfull(x, k, data).

Операции при включении проходит по одному из путей поиска от корня к месту. Для этого требуется время О(th)=О(t logt n) и О(h) обращений к диску. На пути поиска встречающиеся полные узлы расщепляются с помощью операции B_Tree_Split. Точкой роста Б-дерева является не лист, а корень. Новый корень содержит ключ-медиану старого корня. Сделав корень неполным (или он не был таковым с самого начала), мы вызываем операцию B_Tree_Insert_Nonfull(x, k, data), которая добавляет элемент k в поддерево с корнем в неполном узле х. Это рекурсивная операция.

Удаление из Б-дерева.

При удалении ключа их поддерева с корнем в узле х должно выполняться условие: узел х содержит не меньше t ключей, т.к. по правилам Б-дерева узел содержит минимум t –1 ключ. Т.е. при удалении нужно следить, чтобы в узлах на пути поиска был всегда запасной ключ. Если в результате удаления опустел корень, то корнем становится его единственный сын и высота Б-дерева уменьшается. При удалении возможны различные случаи:

1) Если ключ k находится в узле х, являющемся листом, то k удаляется из х. (Удал.6).

2) Если ключ k найден во внутреннем узле х, то

2a) если сын y узла х, предшествующий k, содержит не менее t ключей, то в его поддереве находится ключ k`, непосредственно предшествую-щий k. Этот ключ находится в листе поддерева с корнем y. Найти его можно за один про-смотр поддерева от его корня к листу. Рекурсивно вызываем операцию для k`: удаляем k`, заменяем в х ключ k на k`. (Удал.13).

2b) если сын z, следующий за k, содержит не менее t ключей, поступаем аналогично;

2c) если и y и z содержат t –1 элементов, соединяем узел y, ключ k и узел z, помещая все в вершину y, которая теперь содержит 2t –1 ключей. Уничтожаем z и удаляем из x ключ k и указатель на z. Рекурсивно удаляем k из y. (Удал.7).

3) Если х – внутренний узел, но ключа k в нем нет, найдем среди сыновей узла х корень pi [x] поддерева, где должен лежать ключ k (если этот ключ вообще есть). Если pi [x] содержит не менее t ключей, можно рекурсивно удалить k из поддерева pi [x]. Если же pi [x] содержит всего t –1 элементов, то предварительно делаем шаги 3a) или 3b):

3a) пусть оба соседа узла pi [x] содержат t –1 элементов. Тогда объединим узел pi [x] с одним из соседей (как в случае 2c). При этом ключ, разделяющий их в узле х, станет ключом медианой нового узла. (Удал.4).

3b) пусть pi [x] содержит t –1 элементов, но один из его соседей содержит по крайней мере t элементов (соседом называем такого сына узла х, который отделен от pi [x] ровно одним ключом разделителем). Тогда добавим сыну pi [x] элемент из узла х, разделяющий pi [x] и его правого соседа, а в узел х вместо него поместим самый левый ключ этого соседа. При этом самый левый сын соседа превращается в самого правого сына узла pi [x]. Аналогично поступаем для левого соседа. (Удал.2).

Описанный алгоритм требует возврата к уже просмотренному узлу (случаи 2a, 2b). Это происходит, когда требуется удалить элемент из внутренней вершины. К счастью большинство узлов Б-дерева – листья и эти случаи редки.

Операция требует О(h) обращений к диску. Вычисления требуют О(th)=О(t logt n) времени.

26. Коды Хаффмена. Алгоритм построения кодового дерева Хаффмена.

Дерево Хаффмана.

Алгоритм строит кодовое дерево, соответствующее оптимальному коду снизу вверх, начиная с множества |C| листьев и делает |С-1| слияние. Для каждого символа задаётся его частота f[C]. Для выборки двух объектов для слияния используется очередь с приоритетом. В качестве приоритета используется частота: чем меньше частота, тем более приоритетным является элемент очереди. Берётся два наиболее приоритетных узла и выполняется слияние, создаётся родительский узел, объединяющий два этих узла. В родительском узле фиксируется суммарная частота. Родительский узел также помещается в очередь с приоритетами и т.д. Всего необходимо выполнить С-1 слияние.

Haffman(C)

  1. ∆C- мн-во узлов-листьев.

  2. n ←|C|

  3. Q←{C} ∆Q-очередь с приоритетами.

  4. for i←1 to n-1

  5. do z ← Create_Interned

  6. x ← left[z] ← Deque_min(Q)

  7. y ← right[z] ← Deque_min(Q)

  8. f[z] ← f[x] + f[y]

  9. Enque(Q,z)

  10. return Deque_min(Q)

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

Используется двоичное просеивание для удаления, добавления.

Enque_min (Q,p,data)

  1. if last=n-1

  2. then ошибка «overflow»

  3. last ← last + 1

  4. i ← last

  5. j ← i/2

  6. while j>0 and p[Qj]>p

  7. do Qi← Qj

  8. i ← j

  9. j ← i/2

Если вероятности неодинаковы, то имеется возможность наиболее вероятным (часто встречающимся) элементам сопоставить более короткие кодовые слова и, наоборот, маловероятным элементам сопоставить более длинные кодовые слова.

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

Суть алгоритма Хаффмена удобно объяснить через построение кодового дерева — графа древовидной формы. Дерево строится от концевых вершин по направлению к корню, снизу вверх. Сначала упорядочим все элементы сообщения по невозрастанию или по неубыванию (это не принципиально) их вероятностей (частот встречаемости). Эти элементы образуют концевые вершины дерева, называемые также листьями. Выберем две из них с наименьшими вероятностями. Построим новую вершину, из которой одна ветвь идет к одному элементу, а другая — к другому. Этой новой вершине припишем вероятность, равную сумме вероятностей вершин, с которыми она соединена. Далее рассмотрим все оставшиеся концевые вершины и только что построенную. Выберем из них две с минимальными вероятностями и соединим их с новой вершиной, которой припишем сумму вероятностей объединяемых вершин. Поступаем так до тех пор, пока не останется ни одной пары вершин, которые можно было бы объединить. В результате получится дерево. Очевидно, что вероятность, приписанная корню дерева, равна 1. Теперь разметим ветви, выходящие из вершин: одной из них припишем 1, а другой 0, если хотим получить кодовые слова в таком алфавите. Сделаем это для всех пар ветвей. Тогда последовательность нулей и единиц, которую можно собрать, двигаясь от корня дерева к концевой вершине, образует кодовое слово для соответствующего элемента.

Средняя длина кодового слова вычисляется как взвешенная вероятностями сумма длин всех кодовых слов:

Lcp = p1L1 + p2L2 + ... + pnLn,

где p1,..., pn — вероятности кодовых слов;

L1,..., Ln — длины кодовых слов.

Клод Шеннон в 40-х годах XX века в своей «Математической теории связи»

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

Н = p1log(1/p1) + p2log(l/p2) + ... + pnlog(l/ pn)

Средняя длина кодового слова, обеспечиваемая кодом Хаффмена, приближается к энтропии при очень больших объемах сообщений. При этом длина кодового слова, имеющего вероятность р, приближается к log (l/p). В случае кодирования двоичными символами основание логарифмов в приведенных выше формулах равно 2.

Если не учитывать вероятности (т. е. считать их равными), то для кодирования n элементов с помощью нулей и единиц потребуется log(n) битов на каждый элемент. Точнее говоря, в качестве длины слова следует взять ближайшее большее целое для этого числа. Так, например, для кодирования 6 элементов потребуются слова длиной 3 (log(6) = 2,585). При этом все слова будут иметь одинаковую длину. Если же учесть вероятности, то для рассмотренного выше примера средняя длина кодового слова будет равна 2,5 (0,5x2 + 0,5x3).

При кодировании достаточно больших сообщений это дает экономию около 17%.

Код Хаффмена реализует обратимое и максимальное сжатие данных (обратимость означает, что имеется возможность полного восстановления исходного сообщения). Максимальность сжатия понимается в следующем смысле. Если источник сообщений генерирует символы с фиксированным распределением вероятностей, то при кодировании сообщений, длина которых стремится к бесконечности, достигается средняя длина кодового слова, равная энтропии. Следует заметить, что для одного и того же распределения вероятностей можно построить, вообще говоря, несколько кодов Хаффмена, но все они дают одинаковые результаты.

Существует еще один алгоритм сжатия — Шеннона-Фано, основанный на тех же идеях, но не гарантирующий максимального сжатия, как алгоритм Хаффмена. Код Шеннона-Фано строится с помощью дерева. Однако построение этого дерева начинается от корня. Все множество кодируемых элементов соответствует корню дерева (вершине первого уровня). Оно разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Эти подмножества соответствуют двум вершинам второго уровня, которые соединяются с корнем. Далее каждое из этих подмножеств разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Им соответствуют вершины третьего уровня. Если подмножество содержит единственный элемент, то ему соответствует концевая вершина кодового дерева; такое подмножество разбиению не подлежит. Подобным образом поступаем до тех пор, пока не получим все концевые вершины. Ветви кодового дерева размечаем символами 1 и 0, как в случае кода Хаффмена.

А. Деревья. Общая характеристика, формы представления и операции.

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

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

Существуют различные типы деревьев:

- дерево (свободное дерево) – непустое множество вершин и ребер. Характерным для дерева является существование только одного пути между любыми двумя вершинами. В этом смысле дерево можно считать частным случаем графа.

- МС – несвязанный набор деревьев.

- дерево с корнем – дерево, в котором выделен узел – корень дерева. Между корнем и любым другим узлом существует только один путь. Обычно ребра в дереве с корнем указывают направление пути от корня к узлам. В этом смысле к узлам дерева с корнем применяется терминология генеалогических деревьев (узел-родитель, дочерний узел, узлы-потомки, узлы-предки). Узлы, не имеющие дочерних узлов, называются листьями.

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

- М-арное дерево – дерево, в котором каждый узел должен иметь конкретное количество дочерних узлов. Если узлы не имеют заданного количества узлов, то они ссылаются на фиктивные узлы.

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

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

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

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

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

Математические свойства бинарных деревьев.

1) Бинарное дерево с n внутренними узлами имеет n+1 внешних узлов (листьев). 2) Бинарное дерево с n внутренними узлами имеет 2n ребер, n-1 ребро с внутренними узлами и n+1 ребро с внешними узлами. 3) Уровень узла в дереве на единицу выше уровня родительского узла. Уровень корня равен 0. Высота дерева – максимальный из уровней узлов в дереве. Длина пути дерева – сумма уровней всех узлов дерева. Длина внутреннего пути – сумма уровней всех внутренних узлов дерева. Длина внешнего пути – сумма уровней всех внешних узлов дерева. Из этих определений вытекают рекурсивные определения: высота дерева на единицу больше максимальной высоты поддеревьев его корня. При анализе рекурсивных алгоритмов максимальная глубина рекурсии соответствует высоте дерева рекурсии и определяет размер стека, необходимого для поддержки вычислений. 4) Высота бинарного дерева с n внутренними узлами не меньше log2n и не больше n-1. 5) Длина внутреннего пути с n внутренними узлами не меньше, чем n*log(n/4) и не больше, чем n*(n-1)/2.

B. Бинарное дерево поиска. Схемы обхода бинарных деревьев. Итеративные и рекурсивные алгоритмы обхода дерева.

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

Схемы обхода. Наиболее общей функцией обработки деревьев является обход дерева, когда для выполнения некоторой операции на дереве, требуется выборка значений из узлов дерева. В зависимости от алгоритма операции возможна одна из трех схем обхода: 1) прямой обход (сверху вниз), при котором обрабатывается значение в узле, а затем значения из левого и правого поддеревьев узла ( To_Down (T) ); 2) поперечный обход (слева направо), при котором обрабатываются значения из левого поддерева, затем значение узла, затем значения из правого поддерева; 3) обратный обход (снизу вверх), при котором обрабатываются значения из левого и правого поддеревьев, а затем значение узла.

To_Down (T) – сверху вниз.

Над деревом можно выполнять операции, имеющие не рекурсивный алгоритм. Но для этого операции должны использовать собственный стек, чтобы иметь возможность вернуться к ранее пройденным, но не обработанным узлам - It_To_Down (T).

Существует еще одна схема обхода узлов дерева – по уровням, при которой узлы посещаются сверху вниз и слева направо на одном уровне. Обход по уровням можно получить из предыдущей операции обхода «сверху вниз», заменив в ней стек на очередь, обслуживаемую по дисциплине FIFO. It_L-t-R (root, Op) – сверху вниз.

Рассмотрим использование операций обхода дерева для выполнения быстрого вывода дерева. Схема поперечного обхода удобна для вертикальной распечатки дерева. Print_BST (t, level) – R-t-L - справа налево. В результате вызова (0,3), (80,2), (0,5), (70,4), (0,5), (60,3), (0,4), (50,1), (0,3), (40,2), (0,5), (30,4), (0,5), (20,3), (0,5), (10,4), (0,5).

Если распечатать дерево по схеме прямого обхода, то получится схема печати, аналогичная распечатке дерева каталогов в файловой системе. Show_Down(T, level). Порядок обхода следующий: (50,1), (40,2), (20,3), (10,4), (0,5), (0,5), (30,4), (0,5), (0,5), (0,3), (80,2), (60,3), (0,4), (70,4), (0,5), (0,5), (0,3).

L-t-R (t, Op) - слева направо.

Print_BST (t, level) – R-t-L - справа налево.

t-L-R (t, Op) – сверху вниз.

L-R-t (t, Op) – снизу вверх.

C. Бинарное дерево поиска. Алгоритм вставки в корень дерева нового элемента. Алгоритм объединения двух деревьев.

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

BST_Root_Insert (t, k, data). В стандартной реализации BST-дерева каждый новый элемент вставляется в нижнюю часть дерева и становится листом дерева. Иногда целесообразно вставлять новый элемент в корень дерева. В результате вновь поступившие элементы располагаются ближе к корню дерева. Такая схема особенно целесообразна, когда приложение чаще всего обрабатывает последние элементы, недавно поступившие в структуру. Благодаря тому, что они находятся ближе к корню, среднее время поиска этих элементов снижается.

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

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

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

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

Объединение двух деревьев. BST_Join (a, b).

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

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

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

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

D. Бинарное дерево поиска. Алгоритмы поиска для заданного узла предыдущего и следующего по ключу узла дерева.

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

Функция BST_Predecessor (root, x) отыскивает для заданного узла предыдущий по значению ключа узел. Если у заданного узла есть левое поддерево, то функция отыскивает максимальный по значению ключа узел.

BST_Predecessor (root, x) + BST_Max (t) + BST_Min (t) + BST_Right_Parent (t, x).

E. Бинарное дерево поиска. Алгоритм поиска k–ого порядкового элемента. Алгоритм разбиения дерева на два дерева.

Описание бинарного дерева поиска в билетах 12-15.

Поиск k-ого элемента в дереве. BST_SelectK (t, k).

Вводится дополнительный параметр. n[t] – число узлов в поддеревьях данного узла. Должен поддерживаться операциями вставки, удаления, поиска. В корне проверяется параметр n[t] у левого сына.

Если nL>k, то для поиска k-ого элемента необходимо идти в левое поддерево корня.

Если nLL - 1.

Если nL=k, то узел найден.

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

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

Для операции Select k можно использовать идею, аналогичную бинарному поиску в массиве. Для отыскания в BST-дереве элемента с k-м наименьшим ключом проверяется количество узлов в левом поддереве корня. Если там имеется k узлов, то возвращается корневой элемент. В противном случае, если левое поддерево содержит более k узлов, рекурсивно отыскивается k-й элемент в левом поддереве. Если левое поддерево содержит m узлов и m

Для реализации операции SelectK удобно в структуру узлов BST-дерева ввести счетчик числа узлов в поддереве – n. Этот счетчик модифицируется любой операцией, изменяющей дерево(insert, delete, R,L). Это дополнение может снизить производительность операций вставки и удаления, увеличить затраты памяти. Но если операция Select k важна, то на эти затраты приходится идти.

Разбиение дерева на два дерева. BST_Part (root, k). + BST_Partition (t, x) + Rn (t).

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

F. Сбалансированные деревья поиска. Алгоритм общей балансировки бинарного дерева поиска.

BST_Balance(t). O(n).

У BST-деревьев два основных недостатка – значительный объем дополнительной памяти для связей в дереве и возможность вырождения дерева в список.

Рассмотрим способы балансировки дерева, снижающие эффект вырождения деревьев в худших случаях. Очень часто дерево формируют элементы упорядоченного файла, или файла с большим числом дублированных ключей. В этом случае построение дерева будет занимать квадратичное время, а поиск - линейное время. Можно периодично выполнять повторную балансировку дерева при его обходе. Но для слишком крупных деревьев выполнять ее часто не желательно. Такая балансировка не гарантирует против квадратичной зависимости для худшего случая между повторными балансировками – к тому же сама балансировка, по меньшей мере, имеет линейную зависимость.

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

Сбалансированным является такое дерево, высота которого логарифмически зависит от количества элементов в дереве n. Наиболее известные сбалансированные деревья: рандомизированное дерево, AVL-дерево, красно-черное (RB-дерево).

В идеально сбалансированном (2-3-дерево) дереве поиск занимает О(log n) время, а построение дерева – О(n*log n) времени. Но поддержание идеально сбалансированного дерева при включении новых элементов требует больших затрат, поэтому при балансировке используются более мягкие критерии. Если внешние узлы дерева расположены на одном, в крайнем случае, двух нижних уровнях, то обеспечивается достаточно высокая производительность.

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



Похожие документы:

  1. Книги: Англо-русский и русско-английский словарь пк

    Документ
    ... сортировка по алфавиту alphascope устройство для вывода буквенной информации на ... доступа с эффективным поиском, вставкой и удалением ... классификация (УДК) universal decimal classification (UDC) универсальная последовательная шина universal serial bus ...
  2. Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков

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

    Методическое пособие
    ... для оценки эффективности разработанной системы, как отношения затрат на разработку ... классификаций 40 4.2. Как создается классификация 43 4.2.1. Пример классификации. 49 4.3. Классификация и декомпозиция 51 4.5. Основания декомпозиции систем в технике ...
  4. Рекомендации по подготовке и проведению экзамена и оцениванию ответов

    Документ
    ... алгоритма. Исполнитель алгоритма. Система команд исполнителя (на примере учебного исполнителя). Свойства алгоритма. Способы записи алгоритмов ... информацию о природе, обществе и технике. Классификация информации По способу передачи и восприятия: ...
  5. Голицына О. Л., Партыка Т. Л., Попов И. И. Системы управления базами данных: Учеб пособие

    Документ
    ... классификация по ... эффективного алгоритма такой проверки). Рассмотрим процедуру приведения таблиц к НФБК. Такая процедура основывается на ... Приведем пример сортировки по двум ... Пример. Для вывода на экран всех индексных файлов, находящихся на принятом по ...

Другие похожие документы..