- •Структуры и алгоритмы обработки данных Методическое пособие
- •Ктн е. В. Курапова, кф-мн е. П. Мачикина
- •Оглавление
- •ВвЕдение
- •Необходимые понятия и определения
- •Основные структуры данных
- •Задача сортировки массивов
- •Трудоемкость методов сортировки массивов
- •Задача сортировки последовательностей
- •Теорема о сложности сортировки
- •Задача поиска элементов с заданным ключом
- •Методы сортировки с квадратичной трудоемкостью
- •Метод прямого выбора
- •Алгоритм на псевдокоде
- •Пузырьковая сортировка
- •Алгоритм на псевдокоде
- •Шейкерная сортировка
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Метод Шелла
- •Метод прямого включения
- •Алгоритм на псевдокоде
- •Метод Шелла
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Быстрые методы сортировки массивов
- •Пирамидальная сортировка
- •Свойства пирамиды
- •Алгоритм на псевдокоде
- •Построение (1, 8)-пирамиды
- •Сортировка
- •Алгоритм на псевдокоде
- •Метод Хоара
- •Алгоритм на псевдокоде
- •Проблема глубины рекурсии.
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Работа с линейными списками
- •Указатели. Основные операции с указателями
- •Основные операции с линейными списками
- •Методы сортировки последовательностей
- •Метод прямого слияния
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Цифровая сортировка
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Двоичный поиск в упорядоченном массиве
- •Алгоритм двоичного поиска
- •Алгоритм на псевдокоде
- •Обозначим
- •Найден – логическая переменная, в которой будем отмечать факт успешного завершения поиска.
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Сортировка данных с произвольной структурой
- •Сравнение данных произвольной структуры
- •Сортировка по множеству ключей. Индексация
- •Алгоритм на псевдокоде (на примере пузырьковой сортировки)
- •Индексация через массив указателей
- •Варианты заданий
- •Двоичные деревья
- •Основные определения и понятия
- •Различные обходы двоичных деревьев
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Идеально сбалансированное дерево поиска
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Случайное дерево поиска
- •Определение случайного дерева поиска
- •Добавление вершины в дерево
- •Алгоритм на псевдокоде
- •Удаление вершины из дерева
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Сбалансированные по высоте деревья (авл-деревья)
- •Определение и свойства авл-дерева
- •Повороты при балансировке
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Удаление вершины из дерева
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Определение б-дерева порядка m
- •Поиск в б-дереве
- •Алгоритм на псевдокоде
- •Построение б-дерева
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Определение двоичного б-дерева
- •Добавление вершины в дерево
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Деревья оптимального поиска (доп)
- •Определение дерева оптимального поиска
- •Точный алгоритм построения доп
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Хэширование и поиск
- •Понятие хэш-функции
- •Алгоритм на псевдокоде
- •Метод прямого связывания
- •Метод открытой адресации
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Элементы теории кодирования информации
- •Необходимые понятия
- •Кодирование целых чисел
- •Алфавитное кодирование
- •Оптимальное алфавитное кодирование
- •Алгоритм на псевдокоде
- •Почти оптимальное алфавитное кодирование
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Рекомендуемая литература
- •Псевдокод для записи алгоритмов
- •Структуры и алгоритмы обработки данных
- •630102, Г. Новосибирск, ул. Кирова, 86.
Алгоритм на псевдокоде
Построение Б – дерева (D: Данные, a: pPage, Rost: Boolean, V: Item)
Обозначим D – добавляемые данные
а – адрес страницы
Rost – логическая переменная; (принимает значение истина, если дерево выросло).
V – рабочая переменная типа Item для элемента, передаваемого вверх по дереву.
u – рабочая переменная типа Item, фактический параметр при вызове процедуры построения
IF (a = NIL) {D нет в дереве, включение}
V.Data := D
V.p := NIL
Rost := ИСТИНА
ELSE Поиск в Б-дереве (D,a)
IF (R > 0 и a→ eR.data = D ) {элемент D есть в дереве}
ELSE (на этой странице ключа D нет)
IF(R = 0) Построение Б-дерева(D, a→p0, Rost, u)
ELSE Построение Б-дерева (D, a→eR.p, Rost, u)
FI
IF (Rost = true) {включение u вправо от eR}
IF (k < 2m) Rost := false {есть место на странице}
k := k+1
DO (i = k, k-1, ..., R+2) ei = ei-1
OD
e R+1 := u
ELSE {переполнение страницы}
New(b) {создание новой страницы}
IF (R<= m)
IF (R=m) V := u
ELSE V :=em
DO ( i = m, m-1, ..., R+2) ei := ei-1
OD
eR+1:= u
FI
DO (i:=1, 2, ... m ) b→ei := a→ei-1
OD
ELSE {включение в правую страницу}
R:= R-m
V:=em+1
DO(i=1, 2, ... R-1) b→ei := a→ei+m+1
OD
b→eR:= u
DO ( i:=R+1, R+2, ..., m) b→ei := a→ei+m
OD
FI
a→k := m
b→k := m
b→p0:= V.p
V.p := b
FI
FI
FI
FI
При создании Б-дерева необходимо предусмотреть разделение корневой страницы и создания нового корня из одного элемента. Это будет выполняться, если после обращения к процедуре построения Б-дерева с параметром Rost равным ИСТИНА.
Алгоритм на псевдокоде
Разделение корневой страницы
Root := NIL
DO <ввести D>
Построение Б-дерева (D, Root, Rost, u)
IF (Rost = true) (включение новой корневой страницы)
q :=Root
new(Root)
root→k := 1
root→p0 := q
root→e1:= u
FI
OD
Определение двоичного б-дерева
На первый взгляд кажется, что наименьший интерес представляют Б-деревья первого порядка. Но иногда стоит обращать внимание и на такие исключительные варианты. Очевидно, что Б-дерево первого порядка не имеет смысла использовать для представления больших множеств данных, требующих вторичной памяти, т.к. приблизительно 50% всех страниц будут содержать только один элемент.
Двоичное Б-дерево состоит из вершин (страниц) с одним или двумя элементами. Следовательно, каждая страница содержит две или три ссылки на поддеревья. На рисунке 53 показаны примеры страниц Б – дерева при m = 1.
Рисунок 53 Виды вершин ДБД
Поэтому вновь рассмотрим задачу построения деревьев поиска в оперативной памяти компьютера. В этом случае неэффективным с точки зрения экономии памяти будет представление элементов внутри страницы в виде массива. Выход из положения – динамическое размещение на основе списочной структуры, когда внутри страницы существует список из одного или двух элементов.
Рисунок 54 Вершины двоичного Б-дерева
Таким образом, страницы Б-дерева теряют свою целостность и элементы списков начинают играть роль вершин в двоичном дереве. Однако остается необходимость делать различия между ссылками на потомков (вертикальными) и ссылками на одном уровне (горизонтальными), а также следить, чтобы все листья были на одном уровне.
Очевидно, двоичные Б-деревья представляют собой альтернативу АВЛ-деревьям. При этом поиск в двоичном Б-дереве происходит как в обычном двоичном дереве.
Высота двоичного Б-дерева . Если рассматривать двоичное Б-дерево как обычное двоичное дерево, то его высота может увеличиться вдвое, т.е.. Для сравнения, в АВЛ-дереве даже в самом плохом случаеh<1.44 log n. Поэтому сложность поиска в двоичном Б-дереве и в АВЛ-дереве одинакова по порядку величины.