Методы программирования. Громов Ю.Ю - 78 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

78
Заметим, что для того, чтобы знать, куда вставлять следующий эле-
мент «–
∞», необходимо помнить, откуда пришёл ключ, находящийся в
корне. Поэтому узлы разветвления должны содержать указатели, описы-
вающие позицию ключа, а не сам ключ. Отсюда следует, что необходима
память для N исходных записей, (N – 1) указателей и N выводимых записей.
Теперь рассмотрим одну из модификаций выбора из дерева, которая
устраняет необходимость указателей. Когда некоторый ключ поднимает-
ся вверх с нижнего уровня, то на нижнем уровне его сразу можно заме-
нить на «–∞». Если же ключ перемещается вверх с одного разветвления
на другое, то этот ключ можно заменить наибольшим из двух ключей,
который в конце концов всё равно должен подняться на его прежнее ме-
сто. Выполнив эту операцию (корпоративной системы выдвижений)
столько раз, сколько возможно, от исходной конфигурации дерева, пред-
ставленной на рис. 28, прийдём к дереву, изображённому на рис. 31.
Рис. 31. Дерево, в котором каждый ключ поднялся
на свой уровень в иерархии
Имея такое дерево, можно продолжать сортировку не восходящим
(см. рис. 28 – 30), а нисходящим методом: выводится элемент, находя-
щийся в корне, перемещается вверх наибольший из его потомков, пере-
мещается вверх наибольший из потомков последнего и так далее до пер-
вого перемещения вверх «–
∞». Этот метод имеет важное достоинство –
он позволяет избежать лишних сравнений «–
∞» с «–
∞».
Отметим, что до сих пор говорилось только о полных бинарных де-
ревьях, содержащих N = 2
n
узлов. В действительности можно работать с
произвольным значением N, поскольку для любого N нетрудно построить
полное бинарное дерево с N концевыми узлами.
Полные бинарные деревья удобно хранить в последовательных
ячейках памяти так, как показано на рис. 32 для дерева с шестнадцатью
узлами. Числа в узлах этого дерева обозначают не значения ключей, а
номера ячеек памяти, в которых хранятся ключи.
908
897
765
512
275
653
703
503
61 170
-
∝
426
509
677
-
∝
-
∝
87
-
∝
-
∝
-
∝
-
∝
-
∝
-
∝
-
∝
-
∝
154
-
∝
612
-
∝
-
∝
-
∝

Страницы