Cтраница 3
Другая причина использования языка Лисп - его локальная организация: он дает возможность создать легко перестраиваемую программу, позволяющую вносить изменения в работу отдельных элементов системы, не переделывая ее целиком ( см. обсуждение в начале гл. Предполагалось, что система PROMPTER должна работать по-разному в зависимости от типа пользователя, от характера вводимой информации. Способ отображения информации на экране дисплея должен зависеть от возможностей этого дисплея, наконец, способ представления деревьев в памяти мог зависеть от особенностей конкретного компьютера. [31]
Тривиальной операцией, на которой базируются все биномиальные алгоритмы, является объединение двух сортирующих деревьев степени 2, состоящих из одинакового числа узлов. В результате объединения получаем сортирующее дерево, содержащее в два раза большее число узлов, которое, как показано на рис. 9.16, совсем нетрудно построить. Корневой узел с большим значением ключа становится корнем результирующего дерева ( другой исходный корень при этом становится потомком корня результирующего дерева), а его левое поддерево становится правым поддеревом другого корневого узла. Если задано связное представление деревьев, то операция объединения выполняется за постоянное время: мы всего лишь устанавливаем две связи в вершине. [32]
В их статье вводится также важная идея прохождения деревьев различными путями и приводятся многочисленные примеры алгоритмов алгебраических манипуляций. К сожалению, эта важная статья готовилась в спешке и содержит множество опечаток. В нашей терминологии прошитые списки Пирлиса и Торнтона являются всего лишь право-прошитыми деревьями; бинарные деревья, которые прошиваются в обоих направлениях, были независимо открыты А. Графические способы представления связей между древовидными структурами и соответствующие линейные обозначения были описаны А. Представление деревьев в прямом порядке со степенями и соответствующие алгоритмы, связывающее это представление с десятичной классификацией Дьюи, предложены С. [33]