Два - дерево
Cтраница 3
Для того чтобы вести разговор О деревьях, необходимо иметь хорошую описательную терминологию. На рис. 18 изображены два обычных типа генеалогических деревьев. Ясно, что эти два дерева абсолютно разные: родословная показывает прародителей данного лица, в то время как родовая схема показывает его потомков. [31]
Эта история так прекрасна, что я возвращаюсь к ней снова и снова. Бог сказал Адаму: Можешь наслаждаться всеми плодами этого сада, но есть два дерева - дерево жизни и дерево познания. [32]
Генератором с конечным числом состояний ( сокр. ГКС) для F называется ПР-алгоритм моделирования F, соответствующее которому дерево имеет конечное число неизоморфных поддеревьев, причем два дерева считаются изоморфными, если они отличаются друг от друга разве что перестановкой левых и правых ветвей в узлах разветвления. Например, бесконечное ПР-дерево, изображенное на рис. 6, б, имеет только шесть неизоморфных поддеревьев, как это показано на рис. 6, а, а именно поддерево ЗГ с ( или без) 0 или 1 в его корне, поддерево И с 0 или 1 в его корне и другие потомки У. На практике только три из этих шести типов поддеревьев соответствовали бы различным состояниям машинной программы, так как выходные цепочки могли бы быть связаны с переходами между состояниями. [33]
При другом подходе в качестве корня дерева Т можно выбрать одну из вершин, которая образует корневое дерево с минимальным рангом. Выбор вершины в этом случае не однозначен, а результирующее корневое дерево определяется однозначно. Независимо от метода определения корня два дерева идентичны тогда и только тогда, когда соответствующие им корневые деревья одинаковы. Первый метод кажется более простым. [34]
Описанный нами алгоритм ( в том виде, в каком мы его представили) после каждого шага увеличения начинает работу на пустом месте. Конечно, такое запоминание даст эффект, если эти два дерева не слишком велики. [35]
В оставшемся случае у отлично от а и и. Всякое дерево Г, вносящее вклад в ( а1 ( О) Ьу, имеет две компоненты - одна из них ( компонента X) растет из вершины а и содержит вершину (, а другая ( компонента У) растет из Ъ и содержит у. В У существует только одна дуга Е, входящая в вершину у. Удаляя Е из У, мы разбиваем У на два дерева - одно, дерево Уь растет из Ь и включает вершину ( ( Е), другое, дерево У2, растет из у ( см. теорему VI. Если теперь присоединить дугу О, то деревья X и У2 соединятся в одно дерево, растущее из а и содержащее у ( см. рис. VI. Нами установлено тем самым существование такого взаимно однозначного соответствия между вкладчиками в Р и вкладчиками в С. [36]
Задача состоит в том, чтобы найти такой способ представления ситуаций типа ( 12) - ( 14) в компьютере, чтобы можно было эффективно объединять классы вместе и проверять, будут два заданных элемента принадлежать одному и тому же классу или нет. В приводимом ниже алгоритме для этой цели используются древовидные структуры. Элементы множества S становятся узлами леса, и два узла эквивалентны относительно отношения эквивалентности, определяемого заданными парами, тогда и только тогда, когда они принадлежат одному и тому же дереву. А это проверить уже легко, так как два элемента принадлежат одному и тому же дереву тогда и только тогда, когда они расположены ниже одного и того же корня. Далее, два дерева легко объединять в одно, просто полагая одно из них новым поддеревом корня другого дерева. [37]
 |
Организация указателей в однородном красно-черном дереве поиска. [38] |
С другой стороны, дополнительное время, необходимое для изменения ссылок по уровню при выполнении операций над деревом, составляет лишь О ( 1) на одно локальное преобразование дерева ( типа показанных на рис. 19 и 20), и оценки приведенного времени для операций вставки, удаления, конкатенации и расщепления одни и те же для однородных и неоднородных деревьев. Более того, однородные деревья позволяют выполнить более масштабную операцию расщепления, так называемое тройное расщепление. Суть этой операции состоит в следующем. В дереве Т заданы два элемента х и у. Требуется удалить из Т подсписок элементов, начиная с л: и кончая у ( включительно), получив в результате два дерева. Первое дерево представляет удаленный подсписок, а второе - остальные элементы. Приведенное время выполнения операции тройного расщепления равно О ( 1 logmin d, п - d О), где d - число элементов в удаляемом подсписке. [39]
 |
Диаграмма дерева узлов. [40] |
Для создания диаграммы дерева узлов следует выбрать в меню пункт Diagram / Add Node Tree. Возникает эксперт создания диаграммы дерева узлов Node Tree Wizard. Поскольку дерево узлов не обязательно в качестве верхнего уровня должно иметь контекстную работу и произвольную глубину. В одной модели можно создавать множество диаграмм деревьев узлов. Имя дерева узлов по умолчанию совпадает с именем работы верхнего уровня, а номер диаграммы автоматически генерируется как номер узла верхнего уровя плюс литера N, например AON. Если в модели создается два дерева узлов, имеющие в качестве верхнего уровня одну и ту же работу, то по умолчанию диаграммы получат идентичные номер и имя. Поэтому рекомендуется при создании диаграммы дерева узлов внести имя диаграммы, отличное от значения по умолчанию. Второй диалог эксперта Node Tree Wizard ( рис. 1.2.25) позволяет задать свойства диаграммы дерева узлов. [41]
Страницы: 1 2 3