Cтраница 2
Почти все машинные представления деревьев основаны на связанных распределениях. Каждый узел состоит из поля данных и некоторых полей для указателей. В следующем примере представления дерева каждый узел имеет по три поля указателей. [16]
Конечно, хотелось бы, в частности, избавиться от дырок, которыми в конечном итоге будет заполнено псе дерево и которые порождают много ненужных сравнений. Кроме того, надо было бы поискать такое представление дерева из п элементов, которое требует лишь п единиц памяти, а не 2п - 1, как это было раньше. Уилльямсом [2.14], где было получено, очевидно, существенное улучшение традиционных сортировок с помощью деревьев. [17]
Начинаем с выбора первого элемента списка в качестве корневого узла. Помещаем его в ячейку 1 произвольной пустой области, используемой для представления дерева. [18]
Были разработаны многочисленные структуры данных, которые способны поддерживать эффективные реализации всех операций над очередями по приоритетам. Большая их часть базируется на прямом связном представлении пирамидально упорядоченных деревьев. Две связи необходимы для продвижения вниз по дереву ( либо к двум потомкам в бинарном дереве, либо к первому потомку и к одному из следующих потомков в бинарном представлении общего дерева) и одна связь с родителем требуется для продвижения вверх по дереву. Разработка реализаций операций, поддерживающих пирамидальный порядок на любой ( пирамидально упорядоченной) древовидной форме с явно определенными узлами и связями или на других представлениях в общем случае не требует особых ухищрений. Основная трудность сопряжена с такими динамическими операциями как вставить, объединить и удалить наибольший, которые требуют модификации древовидных структур. В основу различных структур данных положены различные стратегии модификации древовидных структур с одновременным сохранением баланса в дереве. В общем случае алгоритмы используют деревья, обладающие большей гибкостью, нежели полные деревья, однако сохраняют их достаточно сбалансированными, чтобы временные показатели не выходили за пределы логарифмических границ. [19]
Мы объединяем два сортирующих деревьев степени 2 ( сверху), помещая больший из двух корней в вершину результирующего дерева, при этом поддерево ( левое) этого корня становится правым поддеревом другого исходного корня. Если операнды содержат 2 узлов, то результат содержит 2 1 узлов. Если операндами являются пирамидально упорядоченные левосторонние деревья, такой же порядок сохраняется и в результирующем сортирующем дереве, при этом ключ с наибольшим значением находится в корне. Отображение той же операции, ориентированной на представление пирамидально упорядоченного биномиального дерева, показано под разделительной чертой. [20]
Порядковый номер необходим, так как Хв может быть кластером разрезания, не входящего в Q. При таком способе зада - - ныя вершин по набору дуг дерева 3) j однозначно восстанавливаются вершины дерева, как множества разрезаний. При представлении Ф) целесообразно делить его на каждом шаге процесса на две части. Вторая часть - это множество висячих звезд вместе с информацией о границах и о расстоянии от вершин до корня, упорядоченное с помощью функции предпочтения. Такой способ представления дерева приводит к сокращению объема информации п к сокращению времени поиска разветвляемой вершины. [21]
В течение сортировки запись переме-лхается только один раз; все остальные перемещения являются перемещениями признаков или адресов. Однако здесь есть некоторая зависимость от реализации. Запись может перемещаться дважды: из буфера ввода в область сортировки и из области сортировки в буфер вывода. Если используется схема чередующихся буферов, то область сортировки и память, используемая для представления дерева, располагается в отдельной рабочей области вне области буферизации. [22]
Использование локально-организованной структуры языка Лисп позволило создать программу с модульной структурой, отдельные компоненты которой можно переделывать или заменять независимо. Так, например, основная программа работы с деревом состоит из трех достаточно независимых блоков. Управляющий блок контролирует процесс движения по дереву; он ответственен за выполнение описанного выше алгоритма поиска информации и пополнения дерева. Связь с пользователем реализуется с помощью другого блока, управляющий блок обращается к нему с помощью функции GET INF для получения информации от пользователя и функций SHOW и UNSHOW для выдачи информации пользователю. Информация пользователю может быть выдана в виде одной строки или в виде меню, которое может видоизменяться в зависимости от структуры информации и возможностей дисплея, но все это никак не меняет работу основного блока. Наконец, отдельный блок знает о том, как представлено дерево в памяти машины. Управляющий блок обращается к нему с помощью небольшого числа функций, например BRANCHES для получения списка ветвей, выходящих из данной вершины, или GO BACK для возврата по дереву на один шаг. Можно изменять способ представления дерева, например упаковывать отдельные его фрагменты для экономии памяти, можно включать в дерево дополнительную информацию, не используемую основным алгоритмом ( например связать с каждой вершиной дерева множество продукций, которые будут выполняться в нестандартных ситуациях), опять сохраняя при этом основной алгоритм. [23]