Представление - деревей
Cтраница 2
 |
Структура вершины двоичного дерева. [16] |
В нашем рассмотрении важна не максимальная эффективность машинного воплощения бинарных деревьев, а возможность представления деревьев любой арности через двоичные деревья, которые вполне естественно считать канонической формой компьютерного представления деревьев. [17]
Составные выражения объединяются в древовидной структуре, при этом используется очевидное соответствие между символическими выражениями и представлением конечных деревьев. [18]
Дело в том, что списковые структуры, являющиеся основным типом данных в языке Лисп, являются идеальным способом для представления деревьев в памяти компьютера. Особенно ярко возможности Лиспа проявляются при работе с деревьями, которые могут разрастаться, причем новые ветви могут вырастать из любой вершины дерева. В такой ситуации лисповские локально-действующие динамические процедуры выделения памяти и процедуры сборки мусора, позволяющие освободить неиспользуемую более память, являются незаменимыми. При работе на традиционных языках пришлось бы специально программировать такие процедуры. [19]
В нашем рассмотрении важна не максимальная эффективность машинного воплощения бинарных деревьев, а возможность представления деревьев любой арности через двоичные деревья, которые вполне естественно считать канонической формой компьютерного представления деревьев. [20]
Для пересылки обычно используются линейные или последовательные файлы. Однако в ряде применений требуются представления деревьев или транзитивных графов. Примером может служить список разборки большого механизма, например автомобиля. Такая структура хорошо представляется деревом, а иногда и транзитивным графом. [21]
Были разработаны многочисленные структуры данных, которые способны поддерживать эффективные реализации всех операций над очередями по приоритетам. Большая их часть базируется на прямом связном представлении пирамидально упорядоченных деревьев. Две связи необходимы для продвижения вниз по дереву ( либо к двум потомкам в бинарном дереве, либо к первому потомку и к одному из следующих потомков в бинарном представлении общего дерева) и одна связь с родителем требуется для продвижения вверх по дереву. Разработка реализаций операций, поддерживающих пирамидальный порядок на любой ( пирамидально упорядоченной) древовидной форме с явно определенными узлами и связями или на других представлениях в общем случае не требует особых ухищрений. Основная трудность сопряжена с такими динамическими операциями как вставить, объединить и удалить наибольший, которые требуют модификации древовидных структур. В основу различных структур данных положены различные стратегии модификации древовидных структур с одновременным сохранением баланса в дереве. В общем случае алгоритмы используют деревья, обладающие большей гибкостью, нежели полные деревья, однако сохраняют их достаточно сбалансированными, чтобы временные показатели не выходили за пределы логарифмических границ. [22]
Несмотря на многословное описание, сама программа для игры в калах довольно проста. Основную трудность составляет построение структуры данных для представления игровых деревьев и обеспечение должного порядка создания и уничтожения этих деревьев. Вам, вероятно, придется написать свои собственные программы, которые будут выделять пространство для деревьев и собирать освобождающуюся память. Требование эффективности по времени работы накладывает ограничение на глубину просмотра; учитывайте это в программах порождения дерева. Вероятно, имеет смысл обеспечить относительную независимость минимаксной процедуры от остальной части программы, с тем чтобы изменения минимаксной процедуры не влияли на всю программу. [23]
Глава состоит из трех главных разделов. Раздел 9.1 вводит тип данных языка Норе для представления абстрактных синтаксических деревьев промежуточного кода, а в разд. Мы завершаем данную главу общим обсуждением проблем, связанных с использованием интерпретатора для определения операционной семантики языка. [24]
Функции Р и Р ф вычислять чуть труднее, поскольку они используются для представления непрошитых деревьев. Читателю настоятельно рекомендуется проработать упр. [25]
Понятие длины пути дерева имеет большое значение при анализе алгоритмов, поскольку эта величина часто непосредственно связана с временем выполнения алгоритма. Прежде всего рассмотрим длину пути бинарных деревьев, так как они имеют особенно тесное отношение к представлению деревьев в компьютере. [26]
Заметим, что конструкторы также могут быть карринговыми, и это объясняет синтаксис данного определения. Символ:: аналогичен символу в языке Норе, а аналогичен Заметим, что имена конструкторов по правилам языка Miranda начинаются с большой буквы. Функция для представления деревьев в виде списков, которая была определена на языке Норе в гл. [27]
Помимо рассмотренного в предыдущем пункте метода LLINK - - RLINK ( левый сын - правый брат), существует еще много способов представления древовидных структур в компьютере. Обычно надлежащий выбор представления в большой степени определяется видом операций над деревьями, которые нам предстоит выполнить. В этом пункте из многих возможных методов представления деревьев мы рассмотрим несколько, полезность которых уже доказана практикой. [28]
Пусть дан Лес, имеющий п узлов, m из которых концевые. H RLINK, которые нужно хранить в памяти, в двух вышеприведенных методах представления деревьев. [29]
Мы увидим ниже, что эти три способа расстановки узлов бинарного дерева в последовательность чрезвычайно важны, поскольку они используются во многих вычислительных методах, применяемых к деревьям. Название прямой порядок отражает тот факт, что каждый корень проходится прежде своего левого поддерева); при обратном порядке каждый корень проходится после своего левого поддерева. Эта терминология оправдывается тем особым значением, которое придается левым поддеревьям, когда для представления обычных деревьев используются бинарные деревья. Об этом более подробно будет сказано в следующем пункте. [30]
Страницы: 1 2 3