Лекция 5 Структуры данных Математические модели данных. Базовые типы данных. Ссылочные типы данных. Древовидные структуры данных. Упорядоченные бинарные деревья. Авл-деревья. Хэш-таблицы

скачать Лекция 5 Структуры данных Математические модели данных. Базовые типы данных. Ссылочные типы данных. Древовидные структуры данных. Упорядоченные бинарные деревья. АВЛ-деревья. Хэш-таблицы. Данные – это то над чем производятся действия. Действия формально описываются системой или, более точно, композицией функций, вычислимых алгоритмом (механической процедурой или подходящими процессорами). По всей видимости, характер данных определяет специфику функций (специфику алгоритма). Самыми простыми данными являются натуральные числа и рекурсивные функции, которые определяют все мыслимые сложные действия над такими элементарными объектами. Гёделем было показано, что любая задача порождения или распознавания объекта любой сложности может быть сведена к процедуре, которая называется гёделизацией. Объекты могут быть закодированы натуральными числами, а действия с ними – рекурсивными функциями. Сложность такого кодирования (гёделизации) объектов произвольной природы является самостоятельной и весьма сложной задачей. Собственно, до появления развитых языков программирования (FORTRAN, ALGOL, PASCAL, C) программирование сложных задач сводилось к построению последовательности операций над двоичными кодами. Возникает вопрос: можно ли разделить сложность решения задачи между конструированием сложных данных и конструированием сложных функций. В настоящее время основное направление развития языков программирования связано с разработкой описания «сложных» данных и «сложных» функций над этими данными. При решении конкретных задач всегда приходится подбирать «сладкую парочку» – данные и алгоритм. ^ Математические модели данных (ММД) ММД представляет собой формальное описание данных, позволяющее конструировать сложные данные из простых. Здесь необходимо вспомнить конструкторские механизмы, которые были изучены для описания алгоритмов. Напомним, а) для машинного описания алгоритма – это логическая структура алгоритма (ЛСА), задаваемая в виде правил «машины состояний» (SM); б) для описания алгоритма композиций функции – это механизм конструирования рекурсивных функций; в) для описания алгоритма в виде исчисления – это формулы (коды объекта) и правила вывода (ПВ) новых формул (кодов объекта). Алгоритм «работает» с процессором, а данные «работают» с памятью; они должны записываться , храниться и извлекаться из нее. ММД должна учитывать именно эту специфику данных. ^ Абстрактные типы данных (АТД) и структуры данных (СД) АТД = , где A – множество элементов данных, P – множество отношений над. A. F – множество функций над отношениями из P. является составляющей АТД и поэтому АТД=. Конкретный тип данных всегда требует определения структур данных и функций (операций) F.. Тривиальным типом может быть множество натуральных чисел, где, например, , отношение быть натуральным числом задаётся известным правилом позиционного десятичного кодирования. Тип «натуральное число» определяется операциями «сложения» и «умножения». Над бинарными кодами может быть задан другой тип – «булевский» с булевскими операциями , &, . Для транслятора, интерпретирующего последовательности символов, нужно сообщить АТД, из которых будет строиться программа. Языки программирования содержат АТД, которые называются базовыми типами и конструкторские механизмы порождения сложных АТД из базовых. ^ Фундаментальные структурные отношения Два отношения позволяют человеку понимать и организовывать окружающий мир: 1) отношение «состоит из» и 2) отношение «имеет значение». На фундаментальность этих способов понимания и организации мира в любой области человеческой деятельности впервые обратил внимание А.А.Богданов в своей работе «Тектология или всеобщая организационная наука» (1913). Мы уже встречались с понятием «структурированного программирования», где понятие программа уточнялось следующим образом. Программа «состоит» из последовательности программ, либо альтернативных программ, либо циклических программ. Информационная структура алгоритма (ИСА), задающая сложную функцию, «уточнялась» подстановкой образующих функций. Например, функция y = x1 + x2 «состоит из» двух аргументов x1 и x2, которые определяют структуру функции, x1 и x2 «имеют значения» (принимают значения) либо 1, либо 2, либо 3, либо (но не все вместе) из множества натуральных чисел. Отметим что отношение структуризации «состоит из» строится как конъюнктивное высказывание. Объект «состоит из» объекта 1 и объекта 2 и т.д. Отношение «имеет значение» строится из дизъюнктивных высказываний. Объект может быть определен как объект 1, либо как объект 2, либо… и т.д. Искусственные объекты реального мира строятся (организуются) с учётом этих фундаментальных отношений. На рис.1 представлена структура объекта «самолёт». Однократной дугой отмечены отношения «состоит из» двукратной дугой – «имеет значение». Сложная структура слов некоторого языка задаётся правилами формальной грамматики, которые описывают замену (подстановку) одного фрагмента слова на другой и фактически задают отношение «состоит из», а альтернативные правила замены передают отношение «имеют значение» (фрагмент «состоит из» фрагмента 1 и фрагмента 2, либо из фрагмента 3 и т.д.). На рис.2 представлено структурное описание болезни «грипп». Диагностическая таблица состоит из набора признаков: x1– кашель и x2 – температура и x3 – насморк. Каждый признак имеет значения 1 (имеет место) либо 0 (не имеет место). Болезнь «грипп» описывается прецедентами (отношение «либо»), если набор признаков относится к болезни «грипп», то он отмечается «1». Для таблицы построено пространство признаков в котором «*» отмечены точки, задающие отношение «грипп». Проведенная минимизация формулы высказывания «грипп» даёт следующее структурное описание: . Смысл этого высказывания: «если есть кашель и насморк, либо температура, то это грипп». Заметим, что здесь не решаются никакие задачи диагностики, кроме задачи порождения описания структуры данных типа «грипп». При конструирования структур данных всегда средствами языка записывают отношения «состоит из» и «имеет значение». Рис. 1. Структурное описание объекта «Самолет». Рис. 2. Структурное описание болезни «Грипп». Структурная формула гриппа: (x1 & x3)  x2. ^ 1.3. Отображение данных в памяти компьютера Конструкции базовых типов во всех процедурных языках повторяют структуру памяти ЭВМ. История появления базовых типов связана с построения формальных моделей памяти, которые с одной стороны отменяли бы жёсткую физическую адресацию, но, с другой стороны, позволяли, введённую формальную идентификацию элементов данных , отображать на структуру физической памяти. Чтобы подчеркнуть это различие, говорят о логической памяти (формальной модели) и физической памяти. ^ Функция адресации xа Задаёт отображение данных на адреса памяти . В зависимости от построения функции адресации можно выделить несколько типов логической памяти. Логическая память совпадает (отождествляется с физической памятью). ^ Индексно – ключевая память, k; xа. Каждый элемент памяти снабжается уникальным именем – ключом. Множество ключей К строится (выбирается) так, чтобы быть линейно – упорядоченным. В этом случае легко построить взаимно однозначное отображение (где N – множество натуральных чисел. В этом случае выделяется прямая адресация для данных, которые находится физически в оперативной памяти и индексно – последовательная, если данные находятся на диске либо ленте. ^ Ассоциативная память, , где – функция, выделяющая содержание (семантику) в самом элементе данных «х». Для логической памяти, имеющую сложную или даже очень простую СД (например, прямую адресацию) определяются операции порождения СД и операции распознавания СД. Базовыми операциями (элементарными) являются следующие. а) ^ Включение элемента данных в СД. Содержательно это означает, дан элемент и СД, необходимо встроить «х» в СД. При помощи этой операции порождается СД, в том смысле, что х «размещается» в СД. б) ^ Поиск элемента данных в СД. Задан идентификатор «х», найти «х»в СД. Для различных функций адресации и СД приходится создавать собственный алгоритм поиска. В этом случае удобно создавать определённые классы СД, и для каждого класса свой алгоритм поиска. в) ^ Исключение элемента данных из СД. Эта операция является отживающим атавизмом, связанным с экономией памяти. Операция состоит из поиска элемента и действий, анулирующих его связи в СД. ^ 1.4. Рекурсивные структура данных. Конструктивные механизмы порождения СД можно разбить на два типа: 1) описания конечных структур, обычно это формулы, записанные специальными конструкциями языка программирования 2) рекурсивные схемы (индуктивные описания), записанные также при помощи специальных конструкций языка. Примером индуктивного описания может служить описание структуры арифметического выражения в языке программирования, использующего формализм Бэкуса – Наура, который является контекстно – свободной грамматикой, о чём говорилось выше. ^ 2. Базовые типы данных в языках программирования. Базовые типы данных это те СД, которые разрешены в языках программирования и понимаются соответствующим транслятором. Например базовыми типами для языка FORTRAN являлись только натуральные и действительные числа. Далее рассматриваются базовые типы, характерные для языка PASCAL. Заметим, что PASCAL был первым языком, в котором были введены сложные типы данных и были предложены рекурсивные механизмы описания бесконечных СД. Большинство языков по примеру PASCAL’я дополнительно ввели аналогичные типы данных. ^ 2.1. Стандартные типы данных. Стандартные типы данных – это типы, которые являются встроенными для большинства ЭВМ. Они включают целые числа (integer), логические значения (booleаn), множество символов печати (char), вещественные числа (real). Для данных типа integer определены точные операции (+) – сложение, (-) – вычитание, (*) – умножение, для boolean определены значения true (истина), false (ложь) и операции () – дизъюнкция, (&) – конъюнкция, () – отрицание. ^ 2.2. Простые типы данных Эти СД определяют множество заданное перечислением своих значений, т.е. множество объединяющие элементы данных с отношением «иметь значение». Например, type цвет=(красный, зелёный, синий). По сути дела являются идентификаторами, эти идентификаторы затем могут быть использованы в программе как константы. Этот тип является простейшей структурой и порождается простым перечислением элементов данных. 2.3. Массив Наиболее распространённая СД, начиная с языка FORTRAN. Массив «состоит из» одинаковых элементов данных с так называемым «случайным доступом» с функцией адресации , где – множество индексов, позволяющих выбрать элемент х. Описание СД «массив» задаётся формулой – , где Т – имя типа, I – индекс обычно «имеет значение» из множества N – натуральных чисел, Т0 – некоторый простой тип, например, real, char и т.д. Сложная СД «массив от массива» аналогична конструкции «функция от функции». 2.4. Запись. СД «запись» представляет объединение («состоит из») элементов, принадлежащих к различным типам. ……… end По сути дела СД «запись» задаёт декартово произведение множеств Z1, Z2,…, Zn – 2.5. Множество Конструкция СД «множество» задаёт множество элементов объединённых отношением «имеет значение» Значениями типа Т является множество элементов типа Т0. Например, означает, что задано множество значений Иногда значением конструкции «» служит множество всех подмножеств множества Т0. Например, для множество значений будет . АТД «множество»= Где  – операция пересечения множеств,  – объединение множеств, / – разность множеств. ^ 2.6. Последовательность данных. Файлы Общее свойство СД, которые обсуждались выше, заключалось в их «конечности». Число элементов массива – конечно, число записей – конечно, число элементов множества значений тоже конечно. Например, определение языка L на алфавите A есть , где , множество всех возможных слов в алфавите A. Слово хA может быть бесконечно в том смысле, что, если есть слово х длиной «l», то к нему можно приписать символ ( в соответствии с правилами порождения слов языка L) и сделать слово длиной «l+1». Например, порождающая грамматика в алфавите A= с правилами порождает все слова в алфавите A, приписывая к слову символ «а» или «b». Определение последовательности как АТД с операцией приписывания (конкатенации), задаётся по индукции: Последовательность с типом Т – пустая последовательность. Последовательность с типом Т – есть элемент данных типа Т. Последовательность с типом Т есть Последовательность с типом Т и приписанным (например, справа) элементом данных типа Т. Для последовательностных СД объём памяти, который необходим для их размещения заранее неизвестен. Трансляторы, работающие с такими СД, должены обладать процедурами динамического распределения памяти. Большинство языков программирования имеет возможность задавать последовательностные СД в виде файла. , где Т0 – любой базовый тип данных. Очень важное свойство файла – последовательный доступ. Файл строится (порождается) при помощи последовательного добавления элементов данных (например, в конец). Поиск элементов данных (распознавание) производится последовательно (от начала до конца). Принято считать, что файл находится в одном из двух состояний: 1) порождение (запись), 2) поиск (чтение). Заканчивая описания базовых типов данных, необходимо сделать замечание: произвольная организация сложных структур «данные от данных» (по анологии «функция от функции») не всегда допускается в языках программирования и, как правило, допустимая структуризация описывается в документации на определённую версию транслятора. ^ 3. Ссылочные типы данных Пара элементов данных может быть связана отношением «следует за». Порождение таких структур может быть конечным описанием таких пар, либо, в случае бесконечных структур, некоторым рекурсивным механизмом. Поиск (распознавание) элемента данных происходит из специального начального элемента алгоритмом обхода СД с отношением «следует за». Для реализации СД с отношением «следует за» вводится ссылочный тип данных. Структура элемента ссылочного типа представляет собой запись с полями, где кроме полей, содержащих информацию, есть поля, служащие для организации СД. имя элемента информация поля ссылок (указателей) на имена следующих элементов xi ai xi1 xi2 … xij … xin xij – ссылка (указатель) на имя следующего элемента xij задаёт отношение «следует за». Конечные структуры задаются совокупностью пар элементов. Пример 1. Список авиатрасс, связывающих города. Отношение «следует за» суть отношение «из города x можно долететь до города y». type Москва= record информация о трассе; Казань; Новгород end type Казань=record информация о трассе; Новгород; Казань; end type Новгород=record информация о трассе; Москва Далее ссылочные структуры будут иллюстрироваться бинарным графом, вершины которого суть имена элементов данных, а направленные дуги соответствуют отношению «следует за». Для примера 1 граф ссылочной СД будет иметь следующий вид, показанный на рис.1 Рис.1 Ссылочный граф для СД «авиатрассы». ^ 3.1. Линейные списки (LL) LL линейный список или очередь имеет ссылочный граф вида где 0, 1, и т.д. имена элементов данных, построенных в цепочку. Бесконечные LL задаются рекурсивным описанием type T = record key: integer; next:  T end где поле «next» содержит ссылку (указатель) на следующий элемент данных. Операция удаления элемента из любого места списка определяет разрыв графа ссылок и новые ссылки для организации необходимого отношения «следует за». Поиск любого элемента списка всегда начинается с начального элемента. ^ 3.2. Связные списки. Древовидные списки Цепочки LL могут быть связаны между собой либо введением специальных элементов связей, либо полей ссылок. Обычно под связными списками понимают деревья, например, показанные на рис. 2. Записи, которые не содержат ссылок (пустые ссылочные поля) называются терминальными. Для рис. 2 это записи с номерами 5, 7, 8, 11, 12, 13. Начало древовидного списка называется корнем, или корневой записью. Как видно из ссылочной СД древовидного списка, некоторые ссылочные поля являются пустыми. Древовидный список может быть записан в виде скобочной формулы, где знак «» соответствует отношению «следует за», а знак «,» соответствует отношению «и». Например, формула х  (y, z) читается так: «за «х» следует и «y» u «z».» Для древовидного списка на рис. 2 скобочная формула будет иметь вид: 01(2(6(9(12,10(11,13)))),3(7,4(8,5))) Язык ЛИСП фактически использует древовидные списки в виде скобочных формул. Операции включения и исключения элементов древовидного списка проводятся изменением значений ссылочных полей. Рис. 2. Древовидный список ^ 3.3. Поиск элемента в древовидных списках Последовательность обхода (алгоритм обхода) при поиске заданного элемента должна гарантировать доступ к всем элементам древовидной СД для проведения процедуры идентификации (распознавания). Существует три вида процедур такого обхода. обход «в ширину снизу-вверх». Процедура является аналогом вычисления по скобочной формуле. Для построения алгоритма удобно скобочную формулу представить в виде ЯПФ (ярусно – параллельной формы). На рис.2г показана ЯПФ древовидного списка. Просмотр начинается с нижнего 7–го яруса и и заканчивается 0–м ярусом. Последовательность осмотра ярусов Обход «в ширину сверху-вниз». Обход начинается с 0–го яруса и заканчивается нижним 7–м. Обход «с возвратом» (back tracking). Представляет собой алгоритм Тезея обхода лабиринта. Для этих целей дерево лабиринта снабжает специальной вершиной, входом (выходом) в корень дерева (она обозначена «». Последовательность обхода Тезеем дерева (по правилу «правой руки») на рис.2 будет следующим: , 0, 1, 2, 6, 9, 12, 9, 10, 13, 11, 10, 9, 6, 2, 3, 7, 3, 4, 8, 4, 5, 4, 3, 1, 0. ^ Произвольная ссылочная структура Для выполнения алгоритмов над произвольными бинарными отношениями служат произвольные ссылочные структуры. На рис.3 показано описание буквы «А» в виде отношения связей между элементами . Заметим, что это отношение является симметричным и поэтому ссылочный граф тоже является симметричным. Поиск элемента в произвольных ссылочных структурах производится только алгоритмом Тезея, для этого назначается дополнительный элемент «вход/выход Тезея». Число операций, которые необходимо затратить на поиск элемента в древовидных ссылочных структурах либо произвольных ссылочных структурах, состоящих из «n» элементов, равно в среднем n/2, а в худшем случае «n». г) последовательность обхода ссылочного графа для поиска элемента (Т-код) , T1, S1, S2, T2, S2, P, S1, P, S2, S1, T1,  Рис. 3. Произвольная ссылочная структура, задающая описание буквы «А» ^ 4. Упорядоченные бинарные деревья (УБД) В этих СД поле имени в записи элемента данных содержится значение «ключа». Переменная ключ- k обладает следующими свойствами. Каждое значение k в поле имени записи уникально и таким образом однозначно идентифицирует запись. Значения ключей линейно упорядочены и в этом смысле могут быть однозначно отображены на множестве натуральных чисел. Тройка вершин со значениями ключей со структурой , где z– вершина «отец», а х и y – вершины «сыновья» имеют строгое отношение порядка такое, что и . ^ УБД деревом называется дерево, вершины которого размечены значениями ключей так, что они образуют отношение строго частичного порядка. На рис.4а показано такое дерево. Рёбра дерева суть отношение порядка обозначено «<<». На рис.4 и далее УБД представлены, расположенными по направлениям <R> – (lewer – опустить, rise – поднять) или (left – левый, right – правый). Стиль изображения принят для экранной визуализации деревьев. Рис. 4 Упорядоченное бинарное дерево ^ 4.1. Характеристики УБД Начальная вершина называется корнем дерева. Оконечные вершины называются терминальными. На рис.4в вершины 6, 8, 9, 10 – терминальные. Путь по дереву от вершины i до вершины j- li,j. Величина пути li,j равна количеству вершин, которые нужно пройти от i до j (включая i). На рис.4в путь из вершины 2 в 9 – , а путь На дереве для каждой вершины могут быть выделены поддеревья, которые заканчиваются соответственно терминальными вершинами. На рис.4б показаны соответствующие левые и правые поддеревья, а на рис.4в поддеревья с выделенной корневой вершиной. ^ Высота дерева с корневой вершиной измеряется – максимальным расстоянием до терминальной вершины. Аналогично измеряется высота деревьев и . На рис.4б и 4в показаны значения высот различных деревьев. Дисбалансом дерева с корневой вершиной называется разность Если – дисбаланс влево. Если – дисбаланс вправо. На рис.4в дерево размечено значениями дисбалансов каждой вершины. ^ 4.2. Порождение УБД Процедура порождения УБД определена для последовательности данных. Процедура представляет собой автомат, работающий с лентой данных. В момент t автомат «отрывает» от ленты ровно одну ячейку, где расположен элемент данных c ключом («оторванная» ячейка пропадает и далее не участвует в процессе) и пристраивает её к дереву по следующим правилам если (где вершина дерева, построенная на всех предыдущих тактах), то сравнивается со следующим правым элементом (вверх по дереву) если , то сравнивается со следующим левым элементом (вниз по дереву) если при движении L или R, или отсутствуют ( является терминальным), то связывается ссылкой с . На рис.5 показана последовательность шагов порождения УБД. ^ 4.3 Эквивалентные последовательности данных. Последовательности называются эквивалентными, если они порождают одинаковые деревья. На рис.5б и рис.6 показаны деревья для эквивалентных и не эквивалентных последовательностей, содержащих одни и те же значения ключей. Рис. 5. Порождение УБД Рис. 6. Эквивалентность последовательностей ^ 4.4. Удаление вершины из УБД Назовём узлом УБД вершину вместе с её связями с другими вершинами УБД. Заметим, что число связей для каждой вершины не более трёх. Процедура удаления состоит из двух операций операция удаления узла (присвоение всем ссылочным полям записи значения «пустая ссылка»). На рис.7а показан разрыв связей для узла Z и «осколки» УБД – правое поддерево xD и левое поддерево yD. В xD выделен терминальный узел, находящийся на минимальном расстоянии от х. В yD выделен терминальный узел , находящийся на максимальном расстоянии от y. Далее необходимо ввести операцию восстановления УБД из «осколков» так, чтобы не нарушить отношение порядка в исходном УБД. операция связывания «связывает» ссылками вершины v, x и y и имеет два варианта, показанные на рис.7б. Эта операция восстанавливает «разрушенную» структуру в УБД. Очевидно, что отношения в исходном УБД и преобразованном УБД сохраняются. Замечание. Для построения УБД без удалённой вершины «Z» можно воспользоваться процедурой порождения дерева для последовательности, в которой вычеркнут элемент «Z». При этом может возникнуть УБД совершенно «не похожее» на исходное дерево. Введённые выше операции «удаления» и «связывания» гарантируют минимальную перестройку УБД при удалении вершины. На рис.8 и 9 приведены примеры удаления узлов из УБД. б) Связывание деревьев yD, xD с узлом v, операция связывания обозначена «+». Два варианта операции связывания. I. 1) v +хD – связывание v и хD. 2) min xL + yD – связывание xD и yD. II. 1) v +yD – связывание v и yD. 2) min yR + xD – связывание yD и xD. Рис. 7. Операции восстановления УБД при удалении узла (вершины) а) удаление узла 17 Рис. 8. Пример удаления узла и восстановления УБД а) Удаление узла 12 б) Два варианта связывания 1) операция 1) операция 2) операция 2) операция Рис.9. Пример удаления узла и восстановления УБД ^ 5. Сбалансированные деревья УБД называется сбалансированным, если для каждого его узла «х» значение дисбаланса, где  и  числовые характеристики левых и правых деревьев узла «х». Числовые характеристики в основном отражают количество операций поиска, которое необходимо сделать, чтобы найти произвольный узел. ^ Идеально сбалансированные УБД УБД Идеально сбалансировано, если для каждого его узла «х» количество узлов в xDL и xDR различаются не более, чем на 1. , где  и  количество узлов. На рис.9а показанное идеально сбалансированное дерево. Для идеально сбалансированного дерева из «n» узлов количество операций поиска любого узла не более, чем . Порождение идеально сбалансированного дерева на каждом шаге состоит из двух операций: Операция размещения узла в соответствии с алгоритмом построения УБД ^ Операции балансировки, связанной с вычислением дисбаланса для каждой вершины и преобразованием дерева к виду идеально сбалансированного. а) Идеально сбалансированное дерево П1=8, 12, 14, 16, 15, 10, 11, 9, 4, 6, 7, 5, 2, 3, 1 б) АВЛ – дерево П2=8, 12, 14, 16, 15, 10, 11, 9, 7, 6, 5, 3, 4, 1, 2 в) П=11, 12, 14, 15, 16, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5 Рис.10 Сбалансированные деревья. 6. АВЛ-деревья Алгоритм идеального балансирования является достаточно сложным и здесь не приводится. Более простые алгоритмы балансировки получаются, если ввести следующее определение: УБД является АВЛ-деревом тогда и только тогда, когда для каждого его узла «х» высота его правого поддерева и высота его левого поддерева различается не более, чем на 1. АВЛ – дерево получило своё название по фамилиям математиков, предложивших и исследовавших такие типы сбалансированных деревьев – Адельсон – Вельский (Россия), Ландис (США). На рис. 10б показано АВЛ-дерево, а на рис. 10в разбалансированное дерево на тех же данных. Очевидно, что количество операций поиска любого узла АВЛ – дерева не более . Операция балансировки АВЛ-дерева показана на рис.11. Здесь уместно привести аналогию с подтягиванием гирь в часах. Если в каком-то узле Ш существует дисбаланс, например , то левая гиря опустилась ниже, чем правая, значит нужно подтянуть правую гирю, и наоборот. Для того, чтобы подтягивать гири (гири по сути дела это ШDR и ШDL) нужно освободить их от связей, а затем, когда балансирование выполнено опять связать Ш с оставшимся АВЛ-деревом. На рис. 12, 13 приводятся примеры АВЛ-балансировки, которые выполняются за несколько шагов. При многошаговой балансировке в случае, когда имеются несколько «самых нижних» разбалансированных узлов алгоритм может привести к «зацикливанию». Свойства АВЛ-деревьев, для которых алгоритм балансирования не приводит к зацикливанию, до сих пор неизвестны. Проводится разметка дисбаланса узлов. Находится самый нижний узел УБД с . (обозначается Шi) Для Шi рассматривается окрестность 2-го порядка. Вводятся операторы «вращения» Проводится операция связывания, не нарушающая АВЛ-отношений а) для операция lower = опустить (Ш) на одну позицию. Ш = panties Операция «lower» не нарушила отношения порядка между узлами. Отношение до вращения (по построению УБД) сохраняется в УБД и после вращения б) для , операция rise = поднять (Ш) Операция «rise» не нарушила отношений порядка между узлами. Ш>u до возвращения и после сохраняется. Рис.11 Операция балансировки АВЛ – дерева. а) Исходное УБД 1) Поднять Ш1 2) Опустить Ш2 Рис.12 Пример двухшаговой балансировки, приводящей к АВЛ – дереву. а) Исходное УБД с разметкой дисбаланса узлов 1) Поднять Ш1 2) Опустить Ш2 Поднять Ш3 Рис.13. Пример 3-х шаговой балансировки ^ 7. Хэш – функции (функции расстановки) Хэш – функция или функция расстановки задаёт отображение , где – множество значений ключей, а A – множество адресов памяти, в которой располагаются данные с этими ключами. Если память является абстрактной памятью, то вместо адресов выступает множество индексов и . Своё имя ^ Н – функция получила от английского слова hash (перемешивать). В связи с тем, что отображение производится на конечное множество индексов Н – функцию называют иногда Н – таблицей. Множество реальных данных K с ключами значительно меньше множества возможных ключей . Например, множество возможных 8-символьных слов из 2 – буквенного алфавита составляет 268 – 1 млрд. слов. Таким образом, если каждое слово из 8 букв является ключом, то 1 млрд. слов, а это объём 300 – страничной книги. Проблема возникает, если последовательность ключей длиной n отобразить в память (таблицу) длиной m. При этом n и m приводят к различным Хэш – функциям. ^ 7.1. Прямая адресация. . Пусть или по другому , и n<<m. Практически таблица будет иметь бесконечную (наращиваемую) длину. Например, пусть . Длина Н – таблицы m=15, тогда некоторые ячейки таблицы окажутся незаполненными как это показано на рис.14. Понятно, что необходимо более «плотно забивать»память и строить функцию расстановки, экономящую память. Н – таблица П(k)=0, 1, 3, 15, 4, 6, 2, 4. k 0 1 2 3 4 0 6 0 0 0 0 0 0 0 0 15 i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Рис.14. Н – таблица с прямой адресацией k=i. ^ 7.2. Открытая адресация. . В этом случае для n<m На рис. 15 приведен пример заполнения Н – таблицы длиной m=4 последовательностью ключей длиной n=8. При этом возникают коллизии, на одну и ту же ячейку с одним и тем же индексом претендуют несколько элементов данных, как это показано на рис.14а. На ячейку «0» претендуют 5 и 20, на ячейку 1–36, 6, 31, на ячейку 2–17, 2. Наиболее простым способом разрешения коллизий является алгоритм размещения в свободную правую ячейку. При этом «правая часть» таблицы всегда может быть увеличена на одну ячейку. Работа по этому правилу требует проведения операции идентификации занятости, такая операция называется пробой. Пример такого размещения в Н-таблице показан на рис. 15б. Поиск элементов с ключом k=i требует очевидно такое же число проб, как и его размещение. Удаление элемента с ключом k=i оставляет соответствующую ячейку свободной. Число операций при размещении элемента в наихудшем случае, когда уже размещено «n» элементов равно также «n». Число операций поиска (проб) при таблице длиной в наихудшем случае равно также «». а) Н – таблица для П(k)=17, 2, 36, 5, 20, 6, 31, 3 Пример коллизии б) Заполнение Н – таблицы при открытой адресации. 1) k 17 2) k 17 2 3) k 36 17 2 i 0 1 2 3 i 0 1 2 3 i 0 1 2 3 размещение 17 размещение 2 размещение 36 1 проба 2 пробы 1 проба 4) k 5 36 17 2 5) k 5 36 17 2 20 6) k 5 36 17 2 20 31 i 0 1 2 3 i 0 1 2 3 4 i 0 1 2 3 4 5 размещение 5 размещение 20 размещение 6 1 проба 5 проб 5 проб 7) k 5 36 17 2 20 31 6 8) k 5 36 17 2 20 31 6 3 i 0 1 2 3 4 5 6 i 0 1 2 3 4 5 6 7 размещение 6 размещение 3 6 проб 5 проб Рис.15. Н – таблица с открытой адресацией и Н – функцией ^ 7.3. Кольцевая адресация В этом случае Н – таблица сворачивается в кольцо и Н – функция рекурсивно зависит от числа проб j. На рис. 16 показано размещение 8 записей в 8 ячейках, организованных в кольцо. m=8 П(k)=21, 22, 13, 15, 29, 30, 37, 39 для 5, 6, 5, 7, 5, 5, 6, 5, 7 Коллизия разрешается сдвигом на один шаг по «кольцу» и повторной пробой до тех пор, пока не будет найдена свободная ячейка. Можно построить Н – функцию, которая сдвигает пробу на несколько шагов, например, на 2. Оказывается, такая функция приводит к неразрешимой коллизии (см. рис. 17). Кольцевые Н – функции уменьшают количество проб и увеличивают плотность заполнения ячеек таблицы, но как показано на примере рис. 17 могут привести к неразрешимым коллизиям. Выбор той или иной кольцевой Н – функции, дающее минимальное число проб и максимальную плотность заполнения, является нерешённой проблемой. Хорошей кольцевой Н – функцией считается функция расстановки с квадратичным шагом. П(k)= 21, 22, 13, 15, 29, 30, 37, 39 m=8 h(k)= 5, 6, 5, 7, 5, 5, 6, 5, 7 n=8 П(k) 21 22 13 15 29 30 37 39 пробы 1 1 3 2 5 5 7 6 Рис.16 Кольцевая Н – таблица с – функцией, зависящей от номера пробы 1 – шаговым сдвигом. П(k)= 21, 22, 13, 15, 29, 30, 37, 39 m=8 h(k)= 5, 6, 5, 7, 5, 5, 6, 5, 7 n=8 коллизия П(k) 21 22 13 15 29 30 37 пробы 1 1 2 2 4 4 Запись с ключом 37 не может разместиться Рис. 17. Пример Н – функции с неразрешимой коллизией. Кольцевая Н – таблица с Н – функцией, зависящая от номера пробы с 2 – шаговым сдвигом . 7.4. Н – таблица с цепочками Другой способ разрешения коллизий – организация Н – таблицы с цепочками (линейными списками). В этом случае значение образуют некоторые классы списков, начальным элементом этого списка являются индексы . Записи с ключами, вступающие в коллизии, образуют элементы этого класса, которые организуются в линейные списки. Например, для 17, 2, 36, 5, 20, 6, 31, 3 на рис. 14а показаны классы записей, сгруппированные по значению их индекса. Эти записи могут быть организованы в списки как это показано на рис.17. 31  20  6  2  5  36  17  3 i 0  1  2  3  класс i = 0 класс i = 1 класс i = 2 класс i = 3 Рис. 18. Н – таблица с цепочками Скачать 297,24 Kb. оставить комментарий Дата 02.10.2011 Размер 297,24 Kb. Тип Лекция, Образовательные материалы