ДВОИЧНЫЙ ПОИСК, АВЛ-Дерево - Структуры и алгоритмы обработки данных
Алгоритм двоичного поиска в упорядоченном массиве сводится к следующему. Берем средний элемент отсортированного массива и сравниваем с ключом X. Возможны три варианта:
Выбранный элемент равен X. Поиск завершен.
Выбранный элемент меньше X. Продолжаем поиск в правой половине массива.
Выбранный элемент больше X. Продолжаем поиск в левой половине массива.
Из-за необходимости найти все элементы соответствующие заданному ключу поиска в курсовой работе использовалась вторая версия двоичного поиска, которая из необходимых элементов находит самый левый, в результате чего для поиска остальных требуется просматривать лишь оставшуюся правую часть массива.
Верхняя оценка трудоемкости алгоритма двоичного поиска такова. На каждой итерации поиска необходимо два сравнение для первой версии, одно сравнение для второй версии. Количество итераций не больше, чем. Таким образом, трудоемкость двоичного поиска в обоих случаях
АВЛ-Дерево
Дерево поиска называется Сбалансированным по высоте, или АВЛ - деревом, если для каждой его вершины высоты левого и правого поддеревьев отличаются не более чем на 1.
АВЛ-дерево никогда не будет в среднем по высоте превышать ИСДП более, чем на 45% независимо от количества вершин:
Log(N+1) ? hАВЛ(N) < 1,44 log(N+2) - 0,328 при N.
Таким образом, лучший случай сбалансированного по высоте дерева - ИСДП, худший случай - плохое АВЛ - дерево. Плохое АВЛ - дерево это АВЛ-дерево, которое имеет наименьшее число вершин при фиксированной высоте. Рассмотрим процесс построения плохого АВЛ-дерева. Возьмем фиксированную высоту h и построим АВЛ - дерево с минимальным количеством вершин. Обозначим такое дерево через TH. Ясно, что Т0 - пустое дерево, Т1 - дерево с одной вершиной. Для построения ТH при h > 1 будем брать корень и два поддерева с минимальным количеством вершин.
Одно поддерево должно быть высотой H-1, а другое высотой H-2. Поскольку принцип их построения очень напоминает построение чисел Фибоначчи, то такие деревья называют Деревьями Фибоначчи: TH = < TH-1, x, TH-2 >. Число вершин в TH определяется следующим образом:
N0 = 0, N1 = 1, NH = NH-1 + 1 + NH-2
Повороты при балансировке
Рассмотрим, что может произойти при включении новой вершины в сбалансированное по высоте дерево. Пусть r - корень АВЛ-дерева, у которого имеется левое поддерево (ТL) и правое поддерево (TR). Если добавление новой вершины в левое поддерево приведет к увеличению его высоты на 1, то возможны три случая:
- 1) если hL = hR, то ТL и TR станут разной высоты, но баланс не будет нарушен; 2) если hL < hr, то тl и tr станут равной высоты, т. е. баланс даже улучшится; 3) если hl > hR, то баланс нарушиться и дерево необходимо перестраивать.
Введем в каждую вершину дополнительный параметр Balance (показатель баланса), принимающий следующие значения:
- -1, если левое поддерево на единицу выше правого; 0, если высоты обоих поддеревьев одинаковы; 1, если правое поддерево на единицу выше левого.
Если в какой-либо вершине баланс высот нарушается, то необходимо так перестроить имеющееся дерево, чтобы восстановить баланс в каждой вершине. Для восстановления баланса будем использовать процедуры поворотов АВЛ-дерева.
Добавление вершины в дерево
Добавление новой вершины в АВЛ-дерево происходит следующим образом. Вначале добавим новую вершину в дерево так же как в случайное дерево поиска (проход по пути поиска до нужного места). Затем, двигаясь назад по пути поиска от новой вершины к корню дерева, будем искать вершину, в которой нарушился баланс (т. е. высоты левого и правого поддеревьев стали отличаться более чем на 1). Если такая вершина найдена, то изменим структуру дерева для восстановления баланса с помощью процедур поворотов.
Поиск элемента с заданным ключом, включения нового элемента, удаления элемента - каждое из этих действий в АВЛ-дереве можно произвести в худшем случае за О(log N) операций.
Отличие между процедурами включения и удаления заключается в следующем. Включение может привести самое большое к одному повороту, исключение может потребовать поворот во всех вершинах вдоль пути поиска. Наихудшим случаем с точки зрения количества балансировок является удаление самой правой вершины у плохого АВЛ-дерева (дерева Фибоначчи). По экспериментальным оценкам на каждые два включения встречается один поворот, а при исключении поворот происходит в одном случае из пяти.
Похожие статьи
-
МЕТОДОВ МЕТОД СОРТИРОВКИ Пирамидальная сортировка Пирамидальная сортировка основана на алгоритме построения пирамиды. Последовательность aI, aI+1,...,aK...
-
ОСОБЕННОСТИ РЕАЛИЗАЦИИ АЛГОРИТМОВ - Структуры и алгоритмы обработки данных
В ходе выполнения курсовой работы, помимо основных алгоритмов, потребовалось реализовать также несколько вспомогательных, необходимых для корректной...
-
ОПИСАНИЕ ПРОГРАММЫ, ОСНОВНЫЕ ПЕРЕМЕННЫЕ И СТРУКТУРЫ - Структуры и алгоритмы обработки данных
ОСНОВНЫЕ ПЕРЕМЕННЫЕ И СТРУКТУРЫ Struct BD { char FIO[32]; // фоpмат <Фамилия>_<Имя>_<Отчество> int numberO; char dolzhnost[32]; char dateB[8]; }...
-
ПОСТАНОВКА ЗАДАЧИ - Структуры и алгоритмы обработки данных
Хранящуюся в файле базу данных загрузить в оперативную память компьютера и построить индексный массив, упорядочивающий данные По дням рождения и ФИО ,...
-
МЕТОД КОДИРОВАНИЯ - Структуры и алгоритмы обработки данных
Код Шеннона Код Шеннона позволяет построить почти оптимальный код с длинами кодовых слов. Тогда по теореме Шеннона из п. 5.1 . Код Шеннона,...
-
Записи, множества, файлы - Структуры данных
Обобщением массива является комбинированный тип данных - запись, являющаяся неоднородной упорядоченной статической структурой прямого доступа. Запись...
-
При работе над проектом разрабатывались два основных компонента системы: база данных (далее - БД) и интерфейс клиентского приложения. Затем необходимо...
-
Данный алгоритм (англ. Maximal Neighborhood Search - MNS) [7] в отличие от алгоритма BFS позволяет дополнительно упорядочить вершины в найденных...
-
Самым традиционным и широко известным из структурированных типов данных является массив (иначе называемый регулярным типом) - однородная упорядоченная...
-
Постановление Правительства Российской Федерации №1119 "Об утверждении требований к защите персональных данных при их обработке в информационных системах...
-
Этапы жизненного цикла БД включают: -Планирование БД - определяются принципы, задачи создания БД. -Проектирование БД. -Материализация БД -...
-
Описание модулей программы Проект приложения содержит следующие модули. Модуль UnitCollection. pas содержит описание классов для работы с коллекцией и...
-
ОПИСАНИЕ ПОДПРОГРАММ - Структуры и алгоритмы обработки данных
Процедуры начальной обработки базы данных: 1. void Read() - считывает базу данных и формирует индексный массив. 2. void PrintMas(void) - осуществляет...
-
Структура записей данных в таких файлах имеет вид, представленный на рис. 4. Рис. 4 Структура записей данных в файлах с неплотным индексном При такой...
-
В алгоритме Zhou&;Koltun при вычислении отклонений цвета используется изображение, переведенное в градации серого. В данной реализации используется...
-
Способы обработки данных - Автоматизированные системы обработки экономической информации
Различаются следующие способы обработки данных: централизованная, децентрализованная, распределенная и интегрированная. Централизованная предполагает...
-
Построение ER диаграмм - Модернизация структуры базы данных на основе анализа требований предприятия
При построении моделей информационных систем важнейшей методикой является ER-моделирование или построение диаграмм сущность-связь. Сущность представляет...
-
Формулировка задания: Составьте программу подсчета числа тех гласных букв в слове X, что не используются в написании слова Z. Описание входных/выходных и...
-
Операции с файловой структурой - Операционная система Windows
К основным операциям с файловой структурой относятся: - навигация по файловой структуре; - запуск программ и открытие документов; - создание папок; -...
-
Физические модели БД - Банки и базы данных. Системы управления базами данных
Под физической моделью БД понимается способ размещения данных на устройствах внешней памяти и способ доступа к этим данным. Каждая СУБД по-разному...
-
Даталогическое проектирование - Банки и базы данных. Системы управления базами данных
Даталогической моделью БД называется модель логического уровня, построенная в рамках конкретной СУБД, в среде которой проектируется БД. Описание...
-
В настоящее время биометрия входит в состав наиболее распространенных технологий и средств защиты информации. Отпечатки пальцев являются самой широко...
-
Как известно , необходимость интеграции нескольких информационных систем как внутри одной организации (системы являются подсистемами к историчной...
-
Для вычисления цвета могут быть использованы различные подходы. Вычисление цвета может проводиться одновременно с геометрической реконструкцией,...
-
Для создания трехмерной реконструкции сцены или объекта необходимо создать его трехмерную модель и вычислить цвет ее вершин. Для геометрической...
-
ДД-код Константа16 ДД-код Константа16 1111 1111 FF 0000 0000 00 0011 0101 35 1111 0100 F4 0101 0111 57 1001 1010 9A 1000 1101 8D 0000 0111 07 1000 0000...
-
Компромиссная система, для удобства восприятия данных человеком и корректной работы компьютера, двоично-десятичная запись чисел. Принцип построения этой...
-
Протокол проверки программы - Программирование алгоритмов линейных и циклических структур
1. Введем размерность массива N = 6 2. Заполним элементы массива X(i) следующими значениями: 12, 1.34, 8, 10, 17.5, 30 3. Получим следующие результаты:...
-
Постановка задачи Необходимо разработать программу для поиска автобусных маршрутов. В качестве среды разработки должна использоваться Delphi 7. В...
-
Поиск, сбор и хранение научной информации - Поиск, накопление и обработка информации
Не все окружающие нас источники информации можно использовать для подготовки научных работ. Ведь научная работа всегда имеет достаточно узкую...
-
Умение читать книгу - Поиск, накопление и обработка информации
В книгах заключена работа многих предшествующих поколений. Осваивая колоссальное научное наследство, необходимо двигать знания вперед. Исследование всех...
-
Информационные технологии в строительстве - Поиск, накопление и обработка информации
Трудно сегодня найти сферу или область деятельности человека, где информация не играла бы основополагающую роль. Информация является главным ресурсом...
-
Структура SQL - Банки и базы данных. Системы управления базами данных
Широкое развитие информационных систем и связанная с этим унифицированность информационного пространства привело к необходимости создания стандартного...
-
Для иллюстрации последовательности проводимых работ приведем диаграмму Гантта данного проекта, на которой по оси Х изображены календарные дни от начала...
-
Численные эксперименты были проведены для следующих целей: Подтверждение корректности алгоритмов. Подтверждение линейности временных затрат алгоритмов. В...
-
После обмена данными с АЦП происходит преобразование считанных данных в одно целое число, характеризующее уровень сигнала на входе АЦП. Т. к. АЦП имеет...
-
Введение - Алгоритмы нескольких махов
Теория графов в последнее время широко используется в различных отраслях науки и техники, особенно в экономике и социологии, а также в генетике,...
-
Основные термины теории баз данных - БД (База данных) - совокупность специальным образом организованных данных, хранимых в памяти вычислительной системы...
-
В рамках выпускной квалификационной работы была разработана автоматизированная информационная система, предназначенная как для автоматического, так и для...
-
Анализ предметной области позволяет выявить пять сущностей: Сущность: Растения для сада (наименование растения; вид; высота; время цветения; отношение к...
ДВОИЧНЫЙ ПОИСК, АВЛ-Дерево - Структуры и алгоритмы обработки данных