Упорядоченные деревья
Cтраница 1
Упорядоченные деревья, так же как и массивы, являются многомерными упорядоченными множествами. Это позволяет найти эффективный подход к описанию последовательного размещения узлов дерева: во-первых, необходимо представить дерево как упорядоченное множество и, во-вторых, использовать уже имеющееся отображение полученного упорядоченного множества на вектор данных. [1]
Упорядоченные деревья эквивалентны согласованным парам круглых скобок: упорядоченное дерево - это либо нуль, либо последовательность упорядоченных деревьев, заключенных в круглые скобки. [2]
 |
Схема узла п-арного дерева. [3] |
Упорядоченные деревья, имеющие степень не менее 3, называются сильно ветвящимися деревьями. Если считать, что степень некоторого узла равна п, то он должен содержать / 1) ключей и п указателей. [4]
В каждом семействе упорядоченные деревья, соответствующие некоторому ( 1, q) - изомеру, встречаются одинаковое число раз, так как независимо от выбора корня определенной / с-ады и порядка расположения входящих в нее вершин, остальные вершины ( 1, q) - мера можно переставить одним и тем же числом способов. Поскольку произведение вероятности любого такого дерева на степень его корня, согласно ( ИЛ), есть величина постоянная, то такое же свойство выполняется для вероятностей упорядоченных / с-ад. [6]
Особенно важную роль играют упорядоченные деревья второй степени. [7]
 |
Другое дерево. [8] |
Сама природа представления данных в компьютере устанавливает точный порядок для всякого дерева, и поэтому в большинстве случаев наибольший интерес для нас представляют упорядоченные деревья. Таким образом, мы будем подразумевать, что все рассматриваемые нами деревья являются упорядоченными, если только явно не оговорено противное. Согласно сказанному, деревья, изображенные на рис. 15 и 16, будут считаться различными, хотя как ориентированные деревья они считались бы одинаковыми. [9]
Сопоставим теперь каждому дереву клона все различные упорядоченные корневые деревья ( см. рис. 1.8), переставляя разными способами его вершины. Упорядоченные деревья, отличающиеся только порядком расположения вершин, будем по определению считать равновероятными, их суммарная вероятность совпадает с вероятностью корневого дерева, из которого они получены. [10]
В своей следующей работе Кэли перечислил непомеченные упорядоченные деревья; эквивалентная задача была по - tставлена и решена 100 годами раньше И. [11]
УпорндичЕпиие fordvreti) jicpcii - то дерева с корнем, в котором определен порядок следования дочерни ч уз юй каждого узла, Упорядоченные деревья - есгестенное nptJitTa icnite; например, при рисовании дерена дочерние узлы размешаются и определенном порядке. [12]
В определенных приложениях способ упорядочения дочерних узлов каждого узла имеет значение; в других это не важно. Упорядоченное ( ordered) дерево - это дерево с корнем, в котором определен порядок следования дочерних узлов каждого узла. Упорядоченные деревья - естественное представление: например, при рисовании дерева дочерние узлы размещаются в определенном порядке. [13]
После т проходов вершины k - ro уровня лексикографически упорядочены по их индексным спискам. Эти вер шины, получили номера от 1 до Nk для некоторого числа N не превышающего W, двум вершивам приписан один и тот же номер, если их индексные списки совпадают. Этим завершается процесс на k - м уровне. После того как вершины на каждом уровне упорядочены, легко построить канонические упорядоченные деревья, после чего установление изоморфизма сводится к определению простого равенства. [14]
Страницы: 1