- •А.Н. Горитов
- •Учебное пособие
- •Учебное пособие
- •Введение
- •1 Введение в предмет
- •1.1 Непрерывная и дискретная информация
- •1.2 Данные и эвм
- •1.3 Объекты предметной области
- •1.4 Представление информации об объектах
- •1.5 Абстрактные алфавиты. Кодирование
- •2 Основные типы и структуры данных эвм
- •2.1 Архитектурные особенности эвм, наиболее существенные для представления данных
- •2.2 Основные понятия о типах и структурах данных
- •2.3 Массивы
- •2.4 Строки
- •2.5 Записи
- •2.6 Записи с вариантами
- •2.7 Множества
- •3 Последовательный файл
- •3.1 Основные свойства последовательных файлов
- •3.2 Сортировка последовательных файлов
- •4 Полустатические структуры
- •4.1 Стек, очередь и дек как полустатические структуры
- •4.2 Представление полустатических структур с помощью массивов
- •5 Линейные динамические структуры
- •5.1 Основные свойства динамических структур
- •5.2 Реализация связного списка массивом
- •5.3 Кольцевой связный список
- •5.4 Линейный двусвязный список
- •6 Представление динамических структур с помощью указателей
- •6.1 Указатели
- •6.2 Представление стека
- •6.3 Представление очереди
- •6.4 Ведение динамических списков с помощью указателей
- •6.5 Алгоритм составления кольцевого двусвязного списка
- •7 Древовидные структуры данных
- •7.1 Основные понятия и определения
- •7.2 Представление деревьев в эвм
- •7.3 Основные операции с бинарными деревьями
- •7.4 Сильно ветвящиеся деревья
- •8 Алгоритмы на графах
- •8.1 Машинное представление графов
- •8.2 Поиск в глубину в графе
- •8.3 Поиск в ширину в графе
- •8.4 Стягивающие деревья (каркасы)
- •8.5 Отыскание фундаментального множества циклов в графе
- •8.6 Эйлеровы пути в графе
- •8.7 Алгоритмы с возвратом
- •8.8 Нахождение кратчайших путей в графе
- •8.9 Кратчайшие пути от фиксированной вершины
- •8.10 Алгоритм Дейкстры
- •8.11 Пути в бесконтурном графе
- •Литература
7.4 Сильно ветвящиеся деревья
Представление информации с помощью бинарных деревьев не отражает всего многообразия задач, связанных с иерархическими структурами данных. Оно достаточно, например, если мы хотим представить родственные отношения "по восходящей линии", т.е. когда для каждого человека указываются его родители (в качестве потомков). Если же нужно изобразить "нисходящую линию", то окажется, что дерево будет иметь узлы со многими ветвями. Такие деревья называются сильно ветвящимися деревьями.
С такими ситуациями можно справиться по-разному. Если, например, задана абсолютная верхняя граница количества детей, то можно представить детей в виде компонента-массива в записи, представляющей человека. Это приводит к неэкономному расходу памяти.
Поэтому часто используют двоичное представление сильно ветвящегося дерева, когда в узле имеется ссылка на самый левый элемент (на самого младшего или самого старшего потомка), а все элементы одного уровня образуют линейный список (рис. 23).
Иван |
| |||||
й |
|
| ||||
|
|
| ||||
i |
|
| ||||
|
|
|
|
|
| |
Ал-др |
|
Мария |
|
Вл-р | ||
ш |
|
|
|
• | ||
|
|
|
|
| ||
• |
|
|
• | |||
|
|
|
|
|
| |
|
Павел |
| ||||
|
• |
| ||||
|
t |
|
Иван |
| ||
• |
| ||
|
1 |
| |
|
|
|
|
Конст-н |
|
Дмитр. | |
|
|
| |
|
|
|
|
|
|
t | |
|
|
|
|
Георгий |
|
Наталья | |
|
|
• | |
|
|
| |
t |
t |
Инна
Рис. 23 Сильно ветвящееся дерево
Это тоже плохой выход, т.к. функционально такие ссылки имеют совершенно разный смысл. Включение в структуру еще каких-то родственных связей приводит к быстрому их разрастанию в сложный реляционный банк данных, который может отображаться в несколько деревьев. Алгоритмы, работающие с такими структурами, тесно связаны с их описанием, поэтому нет смысла определять для них какие-то общие правила работы.
Однако имеется практически очень важная область применения сильно ветвящихся деревьев, которая представляет общий интерес.
Это – формирование и использование крупномасштабных деревьев поиска, в которых необходимы включения и удаления, но для которых оперативная память недостаточно велика или слишком дорога, чтобы использовать её для долговременного хранения.
Предположим, что дерево должно храниться на внешнем запоминающем устройстве, например, на диске. Динамические структуры данных вполне подходят для этой цели. Принципиально новым является лишь то, что ссылки представляют собой адреса на диске, а не в оперативной памяти. Время поиска на диске больше, т.к. обращение к диску требует времени ожидания на перемещение головок и поворот.
Если множество данных, состоящее из 1 млн. элементов, хранится в виде бинарного дерева, то для поиска элемента потребуется в среднем log2106 = 20 шагов поиска. Поэтому желательна такая организация памяти, которая требует меньше числа обращений.
Сильно ветвящиеся деревья – идеальное решение данной проблемы. Если происходит обращение к некоторому одиночному элементу, расположенному на внешнем устройстве, то без больших дополнительных затрат можно обращаться также к целой группе элементов.
Значит дерево нужно разделять на поддеревья, считая, что все эти поддеревья одновременно полностью доступны. Назовем такие поддеревья страницами (рис. 24). Теперь за одно обращение к диску мы обращаемся к целой странице.
Таким образом можно существенно уменьшить число обращений, увеличив количество узлов на странице. Предположим, мы разместили на одной странице 100 узлов (это разумная цифра). Тогда дерево поиска, содержащее 1 млн. узлов, потребует в среднем log100106 = 3 обращений к страницам вместо 20.
При этом нужно иметь в виду, что в случае сильно ветвящихся деревьев необходима схема управления их ростом, т.к. если дерево растет случайным образом, то наихудший случай может потребовать даже 104 обращений.
Б-деревья
Критерии управления ростом могут быть различными. Очевидно, нужно сразу отвергнуть идеальную сбалансированность, т.к. она требует слишком больших затрат на балансировку.
Более мягкий критерий был сформулирован Р. Бэйером: каждая страница (кроме одной) содержит от n до 2n узлов при заданном постоянном n. N называется порядком дерева. Следовательно в дереве с N элементами, наихудший случай потребует lognN обращений к страницам при максимальном размере строк - 2n узлов. При этом коэффициент использования памяти составляет не менее 50%, т.к. страницы заполнены хотя бы наполовину. При всех этих преимуществах данная схема требует сравнительно простых алгоритмов поиска, включения и удаления.
Рассматриваемые страницы данных называются Б-деревьями.
Свойства Б-деревьев:
каждая страница содержит не более 2n элементов (ключей);
каждая страница, кроме корневой, содержит не менее n элементов;
каждая страница является либо листом, т.е. не имеет потомков, либо имеет m+1 потомков, где m - число находящихся на ней ключей;
• все листья находятся на одном и том же уровне. Пример Б-дерева, порядка 2 с 3-мя уровнями:
25
30 40
Г
10 20 П
5 7 8 13 15 18 22 24 26 27 32 35 38 42 45 46
Все страницы содержат 2, 3 или 4 элемента, кроме корня, который может содержать только 1 элемент. Все листья – на 3-ем уровне. Ключи расположены в возрастающем порядке слева направо, если представить дерево как одноуровневое, вставляя потомков между ключами, находящимися на странице - предке. При таком расположении Б-дерево представляет собой естественное развитие принципа организации бинарных деревьев поиска. Отсюда естественно вытекает метод поиска элемента с заданным ключом. Рассмотрим страницу, имеющую вид:
1 |
|
P0 Kl PI K2 РЗ КЗ . . |
. . PM-1 KM PM |
1 1
т.е. содержащую m ключей.
Пусть задан аргумент поиска Х. Предполагая, что страница считана в оперативную память, мы можем использовать известные методы поиска среди ключей кь ..., км. (При большом m - бинарный поиск, при небольшом - последовательный). При этом время, затрачиваемое на поиск в оперативной памяти, пренебрежимо мало по сравнению со временем, затрачиваемым на считывание страницы в оперативную память.
Если поиск неудачен, то возможны следующие ситуации:
к, < х < к1+1 для 1 <= i < m. Продолжаем поиск на странице р,Л;
х > km. Продолжаем поиск на странице ртЛ;
3) x < k1. Продолжаем поиск на странице p0^.
Если в каком-то случае ссылка равна nil, то элемента с ключом x нет в дереве и поиск заканчивается.
Включение в Б-дерево также выполняется просто. Если элемент вставляется в страницу, содержащую m < 2n элементов, то процесс включения ограничивается только этой страницей. Если страница уже заполнена, то только в этом случае структура дерева меняется и могут появиться новые страницы. Рассмотрим дерево порядка 2:
А 20
i
7 10 15 18 26 30 35 40
ВС
Пусть нужно включить в дерево ключ 22. Процесс включения разобьется на следующие этапы:
выясняется, что ключ 22 отсутствует. Включение в страницу С невозможно, т.е. она уже заполнена;
страница С расщепляется на две страницы: С и D;
количество m+1 ключей распределяются поровну между С и D, а средний ключ перемещается на один уровень вверх, на страницу-предка А. Получим:
А 20 30
7 10 15 18 22 26 35 40
ВС D
При этом полученное сохраняет все свойства Б-деревьев. В частности, при расщеплении получаем страницы, содержащие ровно n элементов. Разумеется, включение элемента в страницу-предка может вызвать переполнение этой страницы. Произойдет распространение расщепления, которое может дойти до корня. В этом случае высота дерева увеличится. Можно сказать, что Б-дерево растет от листьев к корню.
По-видимому наиболее удачным будет описание алгоритма включения рекурсивным способом, т.к. процесс расщепления может распространяться назад вдоль пути поиска.
Вначале опишем страницу, располагая элементы на ней в форме массива: TYPE PAGE = RECORD
M: INDEX; P0: REF;
E: ARRAY[1..NN] OF ITEM END; где
CONST NN = 2*N; TYPE REF = ^PAGE;
INDEX = 0..NN; ITEM = RECORD
KEY: INTEGER; P: REF;
COUNT: INTEGER END; Компонента COUNT заменяет всевозможную прочую информацию, не играющую никакой роли в процессе поиска. Каждая страница содержит пространство для 2n элементов. Поле m указывает, сколько элементов размещено в действительности.
Алгоритм поиска с включением достаточно прост и по структуре напоминает простой поиск по бинарному дереву с той разницей, что дальнейший путь выбирается не из двух возможных ветвей. Поиск внутри страницы целесообразно оформить как бинарный поиск в массиве.
Схематично процедура поиска с включением выглядит следующим образом: PROCEDURE SEARCH(X: INTEGER; A: REF;
VAR H: BOOLEAN; VAR U: ITEM); BEGIN IF A = NIL THEN BEGIN {Х нет в дереве}
Присвоение значения х элементу U и установка h в true,
указывая, что элемент U передается вверх по дереву END ELSE
WITH АЛ DO BEGIN {поиск х на странице ал} двоичный поиск в массиве; IF найдено
THEN увеличение счетчика появления элемента ELSE BEGIN
search(X, потомок, Н, U); IF Н THEN {передача вверх элемента U} IF (число элементов на АЛ) < 2N THEN включение в страницу АЛ и установка
Н в false ELSE расщепление страницы и передача вверх среднего элемента END END END;
Здесь булевская переменная h сигнализирует о том, что второй выходной параметр U является передаваемым вверх элементом (при h=trae), который направляется на страницу включения.
Особенно следует предусмотреть ситуацию, когда происходит расщепление страницы-корня. В этом случае следует создать новую корневую страницу и включить в неё один элемент, переданный через параметр U. Таким образом новая страница-корень будет содержать только один элемент. Использование оператора WITH означает не только то, что внутри оператора идентификаторы полей страницы автоматически относятся к странице АЛ. Если реально страницы размещаются во внешней памяти, оператор WITH дополнительно означает передачу указанной страницы в оперативную память. Поэтому каждое обращение к SEARCH предполагает размещение в памяти одной страницы. Всего же необходимо k = lognN рекурсивных обращений. Здесь N - количество элементов дерева.
Следовательно, мы должны иметь возможность разместить в памяти К страниц. Это налагает ограничения на размер страницы 2N. Но количество размещаемых страниц может быть больше чем К, т.к. включение может вызвать их расщепление. Корневую же страницу лучше постоянно хранить в оперативной памяти, т.к. каждый поиск всегда начинается с корня.
Проиллюстрируем процесс построения дерева со следующей последовательностью вставляемых ключей (рис. 25):
20; 40 10 30 15;
35 7 26 18 22; 5;
42 13 46 27 8 32; 38 24 45 25;
а)
б)
; - момент размещения новой страницы.
ж
I 20 I
10 1530 40
в)
г)
20 30
Г
7 10 15 1822 26 35 40 [То 20 30
5 7 15 1822 2б1 35 40
д)
е)
5 7 813 15~Ti22 2426 2732 35 38 42 45 46
Рис. 25 Рост Б-дерева порядка два
Удаление элементов из Б-дерева просто в общих чертах, но сложно в деталях. Здесь можно выделить два случая.
Удаляемый элемент находится на странице-листе, и тогда алгоритм удаления очевиден и прост.
Элемент не на листе. Тогда его нужно заменить на один из двух лексикографически смежных элемента, которые находятся на страницах-листьях и которые легко удалить.
Во втором случае поиск смежного ключа аналогичен соответствующему поиску в бинарном дереве. Мы спускаемся по самым правым указателям левого поддерева вниз к листу Р, заменяем удаляемый элемент на самый правый элемент Р и затем уменьшаем размер Р на единицу.
Как в первом, так и во втором случае после удаления элемента мы должны проверить число элементов m на уменьшенной страницы, т.к. при m < п основное свойство Б-деревьев нарушается.
Если это произошло, нам придется отобрать элемент у одной из соседних страниц Q. Поскольку это требует вызова страницы Q в оперативную память и поэтому является достаточно дорогой операцией, заберем с Q сразу побольше элементов. Обычно элементы страниц Р и Q распределяются поровну на обе страницы (это называется балансировкой).
Но может так оказаться, что с Q нельзя забирать элементы, т.к. она уже достигла своего минимального размера п. В этом случае общее число элементов на страницах Р и Q равно 2п-1 и мы можем слить эти страницы в одну, добавив один элемент (средний) со страницы-предка. Процесс является обратным по отношению к процессу расщепления страниц (на нашем примере можно наблюдать, пытаясь удалить из полученного дерева ключ 22) (рис. 26).
I 20 301 7 10 15 18 22 26 35 40
I 20 1
7 10 15 18 26 30 35 4о
Рис. 26 Удаление ключа 22 в Б-дереве Но удаление среднего ключа на странице-предке может в свою очередь уменьшить её размер ниже допустимой границы п. И тогда потребуется дальнейшая балансировка или слияние уже на более высоком уровне. Этот процесс может распространиться на всем пути к корню. Если корень уменьшается до размера 0, он удаляется и высота дерева уменьшается.
10 20 1
8
13 15 18 2
а1)
10
18 30
40
8 13 15 20 22 26 27 32 35 38 4
5 7 813 15 18 2026
2732 35 38 42 46
5 7 8 13 15 18 20 26 30 40 42 46
в) в1)
10 22 , | 5 7 15 18 20 26 3
15 18 2026 30 35 40
15 22
^ZL
г) г1)
7 10
18 20 26 30 35 40
20
7 10 15 18
26 30 35 40
10 20 30 40
Рис. 27 Распад Б-дерева порядка два
Рассмотрим процесс распада дерева на примере (рис. 27). Пусть имеется исходное дерево (рис. 27 а)) порядка два, из которого последовательно нужно удалить ключи: 25, 45, 24; 38, 32; 8, 27, 46, 13, 42; 5, 22; 18, 26, 7, 35, 15; (; – скачки, т.е. освобождение страниц)
Самостоятельно: составить процедуры для:
поиска в Б-дереве;
включения в Б-дерево;
удаление из Б-дерева.
Контрольные вопросы
Древовидные структуры данных. Основные понятия.
Представление деревьев в ЭВМ.
Процедура формирования дерева.
Обход бинарного дерева.
Поиск в бинарном дереве.
Включение нового узла в дерево.
Удаление узла из дерева.
Сильно ветвящиеся деревья.
Б-деревья.
Свойства Б-деревьев.
Поиск в Б-дереве.
Включение в Б-дерево.
Удаление из Б-дерева.