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

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

2. если хотя бы один потомок является концевым, то потомок заменяет место удаляемого узла

3. если ни один потомок не является концевым, то удаляемый узел нужно заменить:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

Включение в B–дерево.

Нужно включить в это дерево элемент с ключом 22.

Включение состоит из этапов:

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

2. Страница С расщепляется на две страницы, т.е. размещается новая страница D.

3. Количество m + 1 ключей поровну распределяется на C и D, а средний ключ перемещается на один уровень вверх, на страницу предок А.

На рис. 23 изображено B – дерево рис. 22 после включения элемента с ключом 22.

Причина необходимости создания структуры типа Б-дерева заключается в желании избежать обязательного просмотра всего содержимого индексированного файла соглас­но его физической последовательности. Дело в том, что если индексированный файл имеет большой размер, то и его индекс также очень велик. Поэтому последовательный просмотр даже одного только индекса требует больших затрат времени. Разрешить эту проблему можно тем же способом, что и раньше: рассмотреть индексный файл как обычный хранимый файл и создать для него еще один индекс. Эту операцию можно осуществлять повторно нужное количество раз (обычно она применяется трижды, по­скольку создание большого количества иерархических уровней индексирования требует­ся для очень больших файлов). При этом индекс на каждом из уровней будет неплотным по отношению к нижнему индексируемому уровню (он обязательно должен быть не­плотным, иначе такая структура бессмысленна, так как уровень п содержал бы такое же количество записей, что и уровень п+1, а для просмотра потребовалось бы такое же дли­тельное время).

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

Индексные Б–деревья.Верхний (первый) уровень индекса делит весь диапазон возможных значений ключа на m крупных интервалов (3).

Каждая ячейка 1–го уровня связана с блоком (страницей) ячеек 2–го уровня индекса .Каждая ячейка каждого блока 2–го уровня связана с блоком ячеек 3–го уровня и т. д.

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

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

Рис. 3. Пример структуры типа Б-дерева

6. Применение бинарных деревьев. Кодирование и сжатие данных. Кодовые деревья, дерево Хаффмена.

1)Бинарные деревья применяются для поиска дубликатов в тексте. Алгоритм: считывается 1-е число и помещается в корень дерева с пустым левым и правым поддеревьями, затем каждое след. Число сравнивается с числом , находящемся в корне. Если значения совпадают, то это дубликат, если новое число меньше значения корня, то процесс повторяется для левого поддерева и т.д Так продолжается пока не встретим дубликат или пока не достигнем пустое дерево.

2)Для сортировки

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

3)задача поиска информации(см.дерево поиска)

4)для представления арифметических выражений

Рассмотрим метод представления выражения,содерж.операнды и операторы в виде строгого бинарного дерева.Корень содержит оператор,кот.может быть применен к результ.выражения, представлен левым и правым поддеревом.Узел представляет оператор имеет 2 непустых поддерева.При этом не требуются (), т.к.структура дерева определяет порядок операций.

5)использование индексных деревьев для индексации массивов(В-деревьев сильноветвящихся)

Нелинейн.структуры индексов ключевых полей и не повторяющихся полей.При организации индексов чаще всего исп.древовид.структуры в виде В-деревьев.Узел такого дерева можно представить в виде:

х_i-i-ое значение индексир.поля

р_i-указатель на вершину содерж.значение индексир поля <или = х_i, р_i+1≥ хi_.

n-порядок В-дерева

Листовая вершина содержит информацию о нахождении стр.в файле базы данных записями имеющ.соответ зн-ия индексир.поля.

6)задача кодирования и сжатия информации(деревья Хаффмена).Для кодирования и декодирования сообщений.

Допустим,что алфавит состоит из 4-х символов.

Символ	Код
A	010
B	100
C	000
D	111

Сообщение: ABACCDA,закодируем его 010100010000000111010-21 бит

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

Символ	Код	частота	код
A	010	3	0
B	100	1	110
C	000	2	10
D	111	1	111

Построение дерева Хаффмена

Такая операция подсказыв метод реализ оптимальной схемы кодирования,если известн.частота появления символа. Находим в сообщ 2 символа,появл наименее часто. Это символы B и D, будем различать по после числу кода (0 и 1), соед их в единый символ BD,появлен кот означает, что это символ B, либо D.Часто появл. этого символа =сумме частот B и D,поэтому она=2 и т.д.

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

Определение кода символа

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

Декодиров сообщения

Исх. Сообщения при наличии кодировки сообщ и дерева Х может быть восстановлено след.образом:начиная с корня дерева каждый раз,когда встреч 0 двигаемся по левой ветви, а когда 1, двиг по правой ветви. Повторяем процесс, пока не дойдем до листа. Новый символ исх.сообщен и есть символ, соотв.закодир

11101000101110110

DACAACDAB

7. Сортировка. Методы вставок и обмена. Метод Шелла. Быстрая сортировка. Обменная поразрядная сортировка.

Сортировка – процесс перестановки объектов данного множества в определённом порядке.

Цель сортировки – облегчить последующий поиск элементов в отсортированном множестве.

Существует два вида сортировки (в зависимости от вида хранения данных):

• внутренняя (сортировка массивов);

• внешняя сортировка (сортировка файлов).

Терминология и обозначения

Даны элементы а₁,а₂,…,a_n. Сортировка означает перестановку элементов в таком порядке, что при заданной функции упорядочения f выполняется соотношение:

f(a_k1) f(а_k2) … f(а_kn).

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

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

Меры эффективности алгоритма сортировки:

С – количество сравнений ключей;

М – количество перестановок элементов.

Эти числа определяются как функции от n, где n – количество сортируемых элементов.

Хорошие алгоритмы (логарифмические) требуют порядка С~n*log₁₀n сравнений.

Для простых (квадратичных методов): С ~ n² .

Методы вставок

Сортировка простыми вставками.

Элементы условно подразделяются на готовую последовательность: а₁,…,а_i.

И входную последовательность а_i,…,а_n.

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

Пример:

Начальные ключи | 44 | 55 12 42 94 18 06 67

i=2 | 44 55 | 12 42 94 18 06 67

i=3 | 12 44 55 | 42 94 18 06 67

i=4 | 12 42 44 55 | 94 18 06 67

i=5 | 12 42 44 55 94 | 18 06 67

i=6 | 12 18 42 44 55 94 | 06 67

i=7 | 06 12 18 42 44 55 94 | 67

i=8 | 06 12 18 42 44 55 67 94|