ВУЗ:
Составители:
98
В этом примере в конце каждого отрезка помещён добавочный
ключ ∞, чтобы слияние заканчивалось естественно. Так как внешнее
слияние обычно имеет дело с очень длинными отрезками, то эта доба-
вочная запись с ключом ∞ не увеличит существенно длину данных и объ-
ём работы при слиянии. Кроме того, такая «концевая» запись часто слу-
жит удобным способом разделения записей файла.
В рассматриваемом процессе каждый шаг, кроме первого, состоит из
замещения наименьшего элемента следующим элементом из того же от-
резка и изменения соответствующего пути в дереве выбора. Так, на шаге 2
изменяется 3 узла, которые содержали ключ 87 на шаге 1. На шаге 3 из-
меняется 3 узла, содержавшие ключ 154 на шаге 2, и т.д. Процесс заме-
щения в дереве выбора одного ключа другим называется выбором с за-
мещением.
Каждый концевой узел дерева выбора представляет один из отрез-
ков, используемых в процессах слияния, а само дерево, по существу, ис-
пользуется как приоритетная очередь с дисциплиной «наименьший из
включённых первым исключается».
На рисунке 36 изображено дерево «проигравших», представляющее
собой полное бинарное дерево с 12 концевыми и 11 внутренними узлами.
В концевых узлах записаны ключи, а во внутренних – «победители», если
дерево рассматривать как турнир для выбора наименьшего ключа. Числа,
стоящие рядом с вершинами дерева, обозначают позиции записей при
последовательном распределении памяти для полного бинарного дерева.
Рис. 36. Турнир, в котором выбирается наименьший ключ
Чтобы определить новое состояние дерева выбора, когда наимень-
ший ключ 61 будет заменён другим ключом, нужно рассмотреть только
ключи 512, 87 и 154. Если интерпретировать дерево как турнир, эти три
ключа представляют проигравших в матчах с игроком 61. Поэтому во
внутренние узлы дерева необходимо записывать проигравшего в каждом
матче, а не победителя, и тогда информация, необходимая для изменения
этого дерева, будет легкодоступной.
154
61
170
170
275
154
426
154
61
87
61
503
87
512
61
908
170
897
275
653
426
154
509
2
1
3
4 5 6 7
8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23
Страницы
- « первая
- ‹ предыдущая
- …
- 96
- 97
- 98
- 99
- 100
- …
- следующая ›
- последняя »
