Упорядоченное дерево

Cтраница 4

Деревья, эквивалентные набору вложенных множеств, называют ориентированными деревьями. В этом случае получают упорядоченное дерево. Поскольку получена линейная упорядоченность множества В, упорядоченное дерево можно представить линейным списком. [46]

Определение 9.2. Дерево называется пирамидально упорядоченным ( heap-ordered), если ключ в каждом его узле больше или. Эквивалентная формулировка: ключ в каждом узле пирамидально упорядоченного дерева меньше или равен ключу узла, который является родителем данного узла. [47]

В иерархической модели данных ограничения на связи являются еще более жесткими. Структурная диаграмма иерархической базы данных должна быть упорядоченным деревом. Кроме того, дуги, соответствующие функциональным связям, всегда направлены от корня к листьям дерева. На рис. 7.2.1 изображено дерево определения медицинской базы данных. [48]

Трудность установления изоморфизма деревьев заключается в том, что ребра, инцидентные произвольной вершине, не имеют фиксированного порядка. Если бы нам удалось преобразовать любое дерево к некоторому каноническому упорядоченному дереву, то проверка изоморфизма была бы простой - нужно проверить равенство канонических упорядоченных деревьев. [49]

Неупорядоченное дерево можно было бы представить в компьютере упорядоченным деревом; при этом приходится признать, что несколько различных упорядоченных деревьев могут представлять одно и то же неупорядоченное дерево. Действительно, обратная задача определения того, представляют ли два различные упорядоченные дерева одно и то же неупорядоченное дерево ( задача изоморфизма дерева) трудно подается решению. [50]

Оценим общую сложность алгоритма сортировки данных рассматриваемым методом. Процедура SURFACE всплытия Флойда выполняется п раз сначала для формирования исходного почти упорядоченного дерева ( процедура применяется для каждой вершины дерева) и затем п раз для всплытия каждого наибольшего ( наименьшего) элемента в почти упорядоченном дереве. [51]

Основные компоненты мифологической модели. [52]

К наиболее простым структурно определенным относится иерархическая модель. В этой модели данных связи между ее частями являются жесткими, а ее структурная диаграмма должна быть упорядоченным деревом. [53]

Страницы: 1 2 3 4