Пусть имеется Б-дерево порядка m, из которого требуется удалить элемент с ключом х. Прежде всего, организуется поиск удаляемого элемента последовательным просмотром страниц, начиная с корневой. Пусть удаляемый элемент найден на некоторой странице. При этом возможны следующие две ситуации:
· если найденная страница является терминальной, то элемент просто удаляется с нее с последующей проверкой количества оставшихся на этой странице элементов; если после удаления на странице остается слишком мало элементов, предпринимаются некоторые дополнительные действия, описываемые немного позже
· если страница нетерминальная, то на место удаляемого элемента надо поставить элемент-заменитель, который находится также, как и в обычном дереве: входим в левое (правое) поддерево и спускаемся как можно ниже, придерживаясь максимально правых (левых) поддеревьев; после этого надо проверить страницу, с которой был взят элемент-заменитель и при необходимости предпринять корректирующие действия для восстановления структуры Б-дерева
Например, пусть в простейшем Б-дереве порядка 2 на рисунке ниже требуется удалить элемент с ключом х = 40. Левое поддерево для ключа 40 определяется ссылкой, связанной с его левым соседом, т.е. элементом 20. Просматриваем новую страницу (26, 35), выбираем самый правый элемент 35 и по его ссылке выходим на страницу (36, 37, 38). На этой странице крайний правый элемент 38 не имеет потомка и поэтому именно он должен быть элементом-заменителем. Ясно, что он является ближайшим меньшим элементом по отношению к удаляемому. Путь к элементу-заменителю показан жирной линией.
В обоих случаях после удаления элемента с некоторой страницы надо эту страницу проверить на число оставшихся элементов. По правилам построения Б-деревьев на каждой странице (кроме корневой) не может быть меньше m элементов. Если это условие после удаления не выполняется, т.е. на странице остается лишь m-1 элемент, необходима ее корректировка за счет привлечения одной из соседних страниц. Для этого с помощью родительской страницы определяется адрес соседней страницы и выполняется ее загрузка в ОП. Совместная обработка двух соседних страниц выполняется следующим образом.
1. Если на соседней странице имеется более m элементов (хотя бы m+1), то выполняется перераспределение элементов: с более “богатой” соседней страницы некоторое число элементов передается на “бедную” текущую страницу. В простейшем случае достаточно передать один элемент, но на практике чаще всего передается столько элементов, чтобы на этих двух страницах их было почти поровну. Здесь есть один тонкий момент – элементы с одной страницы на другую передаются не прямо, а через родительскую страницу, т.е. происходит как бы перетекание элементов с дочерней страницы на родительскую с вытеснением с нее элементов на текущую страницу.
2. Если соседняя страница сама является “ небогатой ”, т.е. содержит ровно m элементов, используется другой прием. В этом случае происходит объединение двух “бедных” страниц с созданием одной полной страницы. Полная страница создается следующим образом: m-1 элемент берется с текущей страницы, m - с соседней и один элемент - с родительской страницы. Интересно, что этот прием заимствования одного элемента с родительской страницы позволяет сохранить необходимую структуру Б-дерева, т.к. синхронно на 1 уменьшается число элементов на родительской странице и число страниц-потомков.
Поскольку число элементов на родительской странице уменьшилось, то надо и эту страницу проверить на “бедность”, и, при необходимости, выполнить ее корректировку. Это, в свою очередь, может привести к заимствованию элемента с еще более верхней страницы и т.д. В худшем случае этот процесс распространится до корневой страницы, что может потребовать корректировки самой корневой страницы. Правда, эта корректировка выполняется чуть по-другому, т.к. корневая страница может содержать и меньше m элементов. Особенность возникает лишь тогда, когда до удаления на корневой странице был лишь один элемент, и после удаления она становится пустой. В этом случае эта пустая страница просто удаляется, и тем самым на 1 уменьшается высота Б-дерева.
Пример. Пусть в простейшем Б-дереве порядка 2 удаляется вершина 12 и страница становится “бедной”. Соседняя страница (22, 25, 28) может отдать один элемент, и поэтому ключ 22 передается на родительскую страницу, вытесняя с нее ключ 20.
 | |
 |
Если в этом дереве удалить, например, вершину 7, то придется объединять две страницы (5) и (10, 20) вместе и добавлять элемент 8 с родительской страницы для создания одной полной страницы.
 | |
 |
Программная реализация удаления имеет те же особенности, что и добавление, т.е. необходимо запоминать траекторию движения от корневой странице к текущей. Для этого можно ввести рекурсивную подпрограмму Delete с тремя параметрами:
· x – ключ удаляемого элемента (параметр-значение)
· pCurrent – ссылка на текущую страницу (параметр-значение)
· IsPure – признак того, что текущая страница после удаления содержит слишком мало элементов (параметр-переменная).
Псевдокод подпрограммы Delete:
procedure Delete (x: <тип ключа>; pCurrent: pPage; var IsPure: boolean);
Begin
if pCurrent = nil then “элемента x в дереве нет”
Else begin
“поиск x на странице pCurrent”;
if “x найден” then
Begin
if “страница pCurrent^ терминальная”
Then begin
“удалить элемент”;
“уменьшить счетчик числа элементов”;
“установить признак IsPure”;
End
Else begin
“найти элемент-заменитель”;
“вставить элемент-заменитель на место удаленного x”;
“уменьшить счетчик числа элементов”;
“установить признак IsPure”;
End
End
Else begin
Delete (x, “адрес дочерней страницы”, IsPure);
if IsPure then “вызов вспом. подпрограммы Pager()”;
end;
end;
end;
Здесь используется вспомогательная подпрограмма Pager, выполняющая корректировку страницы после удаления с нее элемента x в случае ее “обеднения”. Эта подпрограмма имеет 4 параметра:
· адрес текущей “бедной” страницы (pCurrent)
· адрес родительской страницы (pParent)
· номер элемента на родительской странице, который является непосредственным предком “бедной” страницы (nParent)
· логический признак (IsPure)
Псевдокод подпрограммы Pager:
procedure Pager (pCurrent, pParent: pPage; nParent: integer; var IsPure: boolean);
var pTemp: pPage; {адрес соседней страницы}
Begin
“определение адреса pTemp соседней вершины”;
“определение числа элементов, удаляемых с соседней страницы”;
“пересылка одного элемента с родительской страницы на текущую”;
if “со страницы pTemp пересылается более одного элемента” then
Begin
“пересылка элементов со страницы pTemp на pCurrent”;
“пересылка одного элемента на родительскую страницу”;
“сдвиг влево элементов в массиве на странице pTemp”;
“установка счетчиков числа элементов на соседних страницах”;
IsPure:= false;
End
else begin {объединение страниц}
“пересылка всех эл-тов со страницы pTemp на страницу pCurrent”;
“сдвиг влево элементов в массиве на родительской странице”;
“изменение счетчиков числа эл-тов на тек. странице и ее родителе”;
“удаление пустой страницы pTemp”;
“установка признака IsPure для родительской страницы”;
end;
end;
Главная программа должна вызвать подпрограмму Delete, а после возврата из цепочки рекурсивных вызовов – удалить опустевшую корневую страницу.
Внешняя сортировка
Пусть требуется выполнить сортировку сверхбольшого набора данных, который целиком в ОП не помещается. В этом случае рассмотренные ранее методы сортировки массивов не работают и приходится использовать внешние файлы. Исходный набор данных хранится во внешнем файле и, очевидно, многократно должен считываться в ОП. В каждый момент времени в ОП находится лишь часть полного набора. Главным критерием при разработке методов сортировки становится минимизация числа обращений к внешней памяти.
Основой большинства алгоритмов внешней сортировки является принцип слияния двух упорядоченных последовательностей в единый упорядоченный набор.
Например, пусть имеются две упорядоченные числовые последовательности: (5, 11, 17) и (8, 9, 19, 25)
Их слияние выполняется следующим образом:
· сравниваются первые числа 5 и 8, наименьшее (5) помещается в выходной набор: (5)
· сравниваются 11 и 8, наименьшее (8) – в выходной набор: (5, 8)
· сравниваются 11 и 9, наименьшее (9) – в выходной набор: (5, 8, 9)
· сравниваются 11 и 19, наименьшее (11) – в выходной набор: (5, 8, 9, 11)
· сравниваются 17 и 19, наименьшее (17) – в вых. набор: (5, 8, 9, 11, 17)
· остаток второй последовательности (19, 25) просто копируется в выходной набор с получением окончательного результата: (5, 8, 9, 11, 17, 19, 25)
В общем виде алгоритм слияния можно представить следующим образом. Пусть А={ai} и B={bj} – две исходные упорядоченные последовательности, R – результирующая последовательность.
1. сравниваем а1 и b1, если а1 < b1, то записываем а1 в R, иначе - b1 в R
2. если в уменьшившемся наборе остались числа, то сравниваем его минимальный элемент с минимальным элементом другого набора и записываем наименьший из них в R
3. повторяем шаг 2 до тех пор, пока не закончится какой-нибудь из наборов
4. как только заканчивается какой-нибудь набор, все оставшиеся элементы другой последовательности копируются в результирующий набор
Алгоритм слияния можно использовать и для сортировки массивов, если последовательно применить его несколько раз ко все более длинным упорядоченным последовательностям. Для этого:
1. в исходном наборе выделяются две подряд идущие возрастающие подпоследовательности (серии)
2. эти подпоследовательности (серии) сливаются в одну более длинную упорядоченную последовательность так, как описано выше
3. шаги 1 и 2 повторяются до тех пор, пока не будет достигнут конец входного набора
4. шаги 1 –3 применяются к новому полученному набору, т.е. выделяются пары серий, которые сливаются в еще более длинные наборы, и.т.д. до тех пор, пока не будет получена единая упорядоченная последовательность.
Пример. Пусть имеется входной неупорядоченный набор чисел:
24, 08, 13, 17, 06, 19, 20, 11, 07, 55, 33, 22, 18, 02, 40
Этап 1. Выделяем в нем серии (показаны скобками) и попарно сливаем их:
(24), (08, 13, 17), (06, 19, 20), (11), (07, 55), (33), (22), (18), (02, 40)
(24) + (08, 13, 17) = (08, 13, 17, 24)
(06, 19, 20) + (11) = (06, 11, 19, 20)
(07, 55) + (33) = (07, 33, 55)
(22) + (18) = (18, 22)
Новый набор чисел:
08, 13, 17, 24, 06, 11, 19, 20, 07, 33, 55, 18, 22, 02, 40
Этап 2. Выделяем в новом наборе серии и попарно сливаем их (число серий уменьшилось):
(08, 13, 17, 24), (06, 11, 19, 20), (07, 33, 55), (18, 22), (02, 40)
(08, 13, 17, 24) + (06, 11, 19, 20) = (06, 08, 11, 13, 17, 19, 20, 24)
(07, 33, 55) + (18, 22) = (07, 18, 22, 33, 55)
Новый набор:
06, 08, 11, 13, 17, 19, 20, 24, 07, 18, 22, 33, 55, 02, 40
Этап 3. Выделяем в новом наборе серии (всего три) и сливаем их:
(06, 08, 11, 13, 17, 19, 20, 24), (07, 18, 22, 33, 55), (02, 40)
(06, 08, 11, 13, 17, 19, 20, 24) + (07, 18, 22, 33, 55) = (06, 07, 08, 11, 13, 17, 18, 19, 20, 22, 24, 33, 55)
Новый набор и его две серии:
(06, 07, 08, 11, 13, 17, 18, 19, 20, 22, 24, 33, 55), (02, 40)
Этап 4. После слияния этих двух серий получим полностью упорядоченный набор:
02, 06, 07, 08, 11, 13, 17, 18, 19, 20, 22, 24, 33, 40, 55
Данный метод сортировки называется естественным слиянием. Его особенностью является то, что для его реализации на каждом шаге достаточно сравнивать только два элемента. Именно это позволяет хранить все основные элементы в дисковых файлах, загружая в ОП только небольшое число элементов из каждой серии.
Алгоритм слияния эффективно работает на длинных сериях и неэффективно на коротких. Поэтому его нецелесообразно применять с самого начала сортировки, поскольку для случайного входного набора на первых шагах будут получаться очень короткие серии, что приведет к неоправданно большому числу обращений к дисковой памяти.
Для устранения этого недостатка можно поступить следующим образом:
· исходный сверхбольшой набор данных разделяется на отдельные фрагменты такого размера, чтобы каждый фрагмент мог целиком разместиться в ОП
· каждый фрагмент отдельно загружается в ОП и сортируется каким-нибудь классическим улучшенным методом (например – алгоритмом быстрой сортировки)
· каждый отсортированный фрагмент рассматривается как серия и сохраняется во вспомогательном файле; в простейшем случае достаточно двух вспомогательных файлов, в которые серии сбрасываются поочередно (нечетные серии – в один файл (A), четные – в другой (B)).
Эти действия носят подготовительный характер.
 |
После этого начинается 2-ой этап сортировки:
· выполняется объединение первых серий из разных файлов, т.е. серий 1 и 2, и результат записывается в третий вспомогательный файл С
· выполняется объединение вторых серий из разных файлов, т.е. серий 3 и 4, и результат записывается во вспомогательный файл D
· выполняется объединение третьих серий из разных файлов, т.е. серий 5 и 6, и результат записывается опять в файл С
· серии 7 и 8 после объединения записываются в файл D и т.д.
В итоге, в файлах С и D получатся объединенные серии, которые потом между собой начинают попарно объединяться с записью результата во вспомогательные файлы А и В и т. д. Процесс укрупнения серий продолжается до тех пор, пока не будет получена одна единственная серия, представляющая полученный результат.
 |
Для программной реализации данного метода сортировки необходимы:
· достаточно большой массив в ОП для реализации 1-го этапа
· пять файлов, из которых один исходный и 4 вспомогательных.
Если необходимой для четырех вспомогательных файлов дисковой памяти не хватает, то можно обойтись двумя вспомогательными файлами, но за счет замедления процесса сортировки. В этом случае объединенные серии из А и В помещаются в исходный файл, а потом распределяются опять в А и В. Тем самым появляется дополнительный шаг распределения серий из исходного файла по двум вспомогательным.
 |
Наоборот, если требуется ускорить сортировку за счет дополнительной дисковой памяти, то вместо 4-х вспомогательных файлов можно использовать 6,8,10 и т.д. Ускорение работы происходит за счет того, что объединяются не 2 серии, а 3, 4 или 5 и т.д.
Практические задания
Задание 1. Разработать программу для имитации обработки простейшего Б-дерева второго порядка. Программа должна выполнять следующие действия:
· построение Б-дерева для заданного набора вершин, начиная с пустого дерева
· добавление отдельной вершины
· поиск заданной вершины
· удаление заданной вершины
· вывод Б-дерева в наглядном виде
Имитация обработки определяется тем, что файлы для хранения элементов дерева не используются.
Задание 2. Разработать программу сортировки файлов методом естественного слияния. Для простоты этап предварительной сортировки фрагментов для получения начальных серий не реализуется. Должны использоваться 5 файлов – входной и 4 вспомогательных. Исходный набор заполняется случайными числами в диапазоне от 1 до 1 миллиона.
5.9. Контрольные вопросы по теме
1. В чем состоят особенности задач внешнего поиска и сортировки?
2. Какой критерий является основным для алгоритмов внешнего поиска и сортировки?
3. Для решения каких задач используется структура данных Б-дерево?
4. Что называется страницей Б-дерева?
5. Почему страничная организация Б-дерева является эффективной для решения задачи внешнего поиска?
6. Каким условиям должно удовлетворять Б-дерево?
7. Какими свойствами обладает Б-дерево как дерево поиска?
8. Как оценивается эффективность использования Б-деревьев для задач внешнего поиска?
9. Какие данные должна содержать страница Б-дерева?
10. Какие описания необходимы для определения Б-дерева как структуры данных?
11. Какие шаги включает алгоритм поиска в Б-дереве?
12. Какие основные шаги включает алгоритм добавления вершины в Б-дерево?
13. Что происходит при попытке добавления новой вершины на полностью заполненную страницу Б-дерева?
14. К чему может привести процесс расщепления полной страницы Б-дерева при добавлении новой вершины?
15. В каких случаях высота Б-дерева может увеличиться на единицу?
16. Приведите практический пример добавления вершины в простейшее Б-дерево.
17. Какие особенности возникают при программной реализации алгоритма добавления новой вершины в Б-дерево?
18. Почему при добавлении новой вершины в Б-дерево необходимо запоминать путь от корневой страницы к терминальной?
19. Какие параметры использует рекурсивная подпрограмма добавления новой вершины в Б-дерево?
20. Приведите схему рекурсивной подпрограммы добавления новой вершины в Б-дерево.
21. Что должна делать главная программа при добавлении новой вершины в Б-дерево?
22. Какие основные шаги включает алгоритм удаления вершины из Б-дерева?
23. Как обрабатывается удаление вершины из Б-дерева для терминальной и нетерминальной страницы?
24. Как находится элемент-заменитель для удаляемой из Б-дерева вершины?
25. Какая ситуация может возникнуть после удаления вершины с одной из страниц Б-дерева?
26. За счет чего сохраняется необходимая структура Б-дерева после удаления вершины?
27. Зачем и как выполняется перераспределение вершин между двумя соседними страницами при удалении вершины из Б-дерева?
28. Зачем и как выполняется объединение двух страниц при удалении вершины в Б-дереве?
29. К каким последствиям может привести процесс слияния соседних страниц при удалении вершин из Б-дерева?
30. Приведите практический пример удаления вершины из простейшего Б-дерева.
31. Какие особенности имеет программная реализация удаления вершины из Б-дерева?
32. Какие параметры должна иметь рекурсивная подпрограмма удаления вершины из Б-дерева?
33. Приведите схему рекурсивной подпрограммы удаления вершины из Б-дерева.
34. В чем состоит принцип слияния двух упорядоченных последовательностей?
35. Какие шаги выполняет алгоритм слияния двух упорядоченных последовательностей?
36. Как используется алгоритм слияния последовательностей для сортировки данных?
37. Что такое серия и как это понятие используется при сортировке данных?
38. Как можно улучшить сортировку файлов методом естественного слияния?
39. В чем состоит первый этап внешней сортировки?
40. В чем состоит второй этап внешней сортировки?
41. Какие необходимы вспомогательные файлы при внешней сортировке и как они используются?
42. Как можно уменьшить число вспомогательных файлов, используемых при внешней сортировке?
43. За счет чего можно ускорить сортировку файлов?
44. Как влияет число вспомогательных файлов на эффективность внешней сортировки?
Основные термины и понятия
АВЛ-сбалансированное дерево – разновидность дерева поиска, в котором для каждой вершины высота ее левого и правого поддерева отличаются не более чем на единицу
Балансировка дерева – перестановка вершин с целью сохранения “хорошей” структуры дерева
Б-дерево – разновидность дерева поиска с очень большим числом ключей, основанная на группировании соседних ключей в виде страниц и хранении этих страниц на дисковой памяти
Быстрая сортировка - улучшенный метод сортировки массивов, основанный на разбиении набора данных на все меньшие подмассивы с последующей сортировкой каждого из них
Внешняя сортировка – упорядочивание больших наборов данных с преимущественным хранением на дисковой памяти
Внутреннее хеширование – метод разрешения конфликта ключей при хеш-поиске, основанный на размещении конфликтующих ключей в свободных ячейках таблицы
Внутренняя сортировка – упорядочивание элементов массива, полностью располагающихся в оперативной памяти
Высота дерева – наиболее длинный путь от корневой вершины к терминальной
Граф – нелинейная структура данных, состоящая из элементов-вершин, между некоторыми из которых установлены определенные связи
Двоичное дерево – разновидность дерева, в котором каждая вершина может иметь не более двух связанных с нею поддеревьев
Двунаправленный линейный список – разновидность списковой структуры, в которой каждый элемент имеет два указателя на каждого из своих соседей
Дерево – нелинейная структура данных, рекурсивно представимая в виде отдельных поддеревьев
Дерево поиска – разновидность двоичного дерева, в котором для каждой вершины ключи в левом поддереве меньше, а в правом поддереве больше ключа этой вершины
Динамическое распределение памяти – механизм, с помощью которого при выполнении программы можно получать и освобождать области памяти для хранения каких-либо данных
Естественное слияние – один из методов внешней сортировки, основанный на попарном сравнении и объединении двух упорядоченных последовательностей в одну последовательность
Заголовок списка – дополнительный необязательный элемент в начале списка, который никогда не удаляется из списка
Идеально сбалансированное дерево – разновидность двоичного дерева, для каждой вершины которого число вершин в левом и правом поддеревьях отличаются не более чем на единицу
Карманная сортировка – один из специальных методов сортировки, применяемый для ключей с различными значениями в пределах от 1 до n
Конфликт ключей – ситуация, когда при использовании хеш-поиска два различных ключа претендуют на одно и то же место в массиве
Матрица смежности – способ описания графа с помощью двухмерного массива N*N, ненулевые элементы которого соответствуют связанным вершинам
Метод Шелла – улучшенный метод сортировки массивов, основанный на многократном группировании элементов массива с уменьшающимся шагом и последующей сортировкой методом вставок
О-нотация – способ оценивания трудоемкости алгоритма в зависимости от объема обрабатываемых данных
Открытое хеширование – метод разрешения конфликта ключей при хеш-поиске, основанный на использовании вспомогательных списков для конфликтующих ключей
Очередь – линейная структура данных, в которую добавление производится с одного конца, а удаление – с другого
Переменные-указатели – специальные переменные, значениями которых являются адреса областей памяти
Пирамида – разновидность двоичного дерева, в котором ключ каждой вершины не больше ключей всех ее потомков
Пирамидальная сортировка – улучшенный метод сортировки массивов, основанный на специальном представлении исходного массива в виде так называемой пирамиды
Поразрядная сортировка - один из специальных методов сортировки, применяемый для целочисленных ключей с известным числом разрядов и требующий использования дополнительных списков
Простейшие методы сортировки – алгоритмически простые методы сортировки массивов с трудоемкостью порядка n2
Сортировка вставками – простейший метод сортировки массивов, основанный на поиске для каждого очередного элемента подходящего места в уже обработанной последовательности
Сортировка выбором - простейший метод сортировки массивов, основанный на поиске в необработанном подмножестве наименьшего элемента
Сортировка обменом – простейший метод сортировки массивов, основанный на попарном сравнении и перестановке соседних элементов
Специальные методы сортировки – группа методов сортировки массивов, основанных на использовании дополнительной информации о сортируемом наборе, требующих большой дополнительной памяти, но имеющих линейную трудоемкость
Список – линейная структура данных с возможностью добавления и удаления элементов в любом месте
Список смежности – способ описания графа в виде массива или главного списка вершин, с каждым элементом которого связан список смежных с нею вершин
Стек – линейная структура данных с односторонним добавлением и удалением элементов
Улучшенные методы сортировки – алгоритмически достаточно сложные методы сортировки массивов с трудоемкостью порядка n*logn
Универсальные методы сортировки – группа методов сортировки массивов, не требующих никакой дополнительной информации о сортируемых наборах и никакой дополнительной памяти
Хеш-поиск – метод поиска, позволяющий по значению входного ключа сразу определять его положение в массиве, организованном в виде специальной таблицы (хеш-таблицы)
Хеш-таблица – массив ключей, размещенных в ячейках, индексы которых определяются с помощью специального преобразования (хеш-функции)
Хеш-функция – специальный алгоритм (в частном случае – функция), применяемый для преобразования входного ключа в индекс его размещения в массиве (хеш-таблице)
Литература
1. Кнут Д. Искусство программирования, том 1. Основные алгоритмы, 3-е изд. – М.: Изд. дом “Вильямс”, 2000 г.
2. Кнут Д. Искусство программирования, том 3. Сортировка и поиск, 2-е изд. – М.: Изд. дом “Вильямс”, 2000 г.
3. Вирт Н. Алгоритмы и структуры данных
4. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. – М.: Изд. дом “Вильямс”, 2001 г.
5. Кормен Т. и др. Алгоритмы: построение и анализ. – МЦНМО, 2000 г.
6. Топп У., Форд У. Структуры данных в С++. – М.: ЗАО “Издательство БИНОМ”, 2000 г.
7. Хэзфилд Р., Кирби Л. и др. Искусство программирования на С. Фундаментальные алгоритмы, структуры данных и примеры приложений. – К.: Издательство “ДиаСофт”, 2001 г.