Дерево (структура данных)

Общая и, следовательно, небинарная, несортированная, с дублированием некоторых меток, произвольная диаграмма дерева. На этой диаграмме узел с меткой 7 имеет трех дочерних узлов с меткой 2, 10 и 6 и один родительский элемент с меткой 2. Корневой узел наверху не имеет родителя.

В информатике , А дерево широко используется абстрактный тип данных , который имитирует иерархическую древовидную структуру , со значением корня и поддеревами детей с родительским узлом , представленное в виде набора связанных узлов .

Структура данных дерева может быть определена рекурсивно как набор узлов (начиная с корневого узла), где каждый узел представляет собой структуру данных, состоящую из значения вместе со списком ссылок на узлы («дочерние элементы»), с ограничения, что никакая ссылка не дублируется и не указывает на корень.

В качестве альтернативы дерево может быть определено абстрактно в целом (глобально) как упорядоченное дерево со значением, присвоенным каждому узлу. Обе эти точки зрения полезны: хотя дерево может быть проанализировано математически в целом, когда оно фактически представлено как структура данных, оно обычно представляется и обрабатывается отдельно по узлам (а не как набор узлов и список смежности ребер между узлами). , например, как орграф ). Например, глядя на дерево в целом, можно говорить о «родительском узле» данного узла, но в целом, как структура данных, данный узел содержит только список своих дочерних узлов, но не содержит ссылки. своему родителю (если есть).

Обычное использование [ править ]

• Представление иерархических данных, таких как:
  • Абстрактные синтаксические деревья для компьютерных языков
  • Разбирать деревья для человеческих языков
  • Объектные модели документов XML и HTML документов
  • Документы JSON и YAML обрабатываются
• В деревьях поиска данные хранятся таким образом, что возможен эффективный алгоритм поиска через обход дерева.
  • Бинарное дерево поиска представляет собой тип бинарного дерева
• Представление отсортированных списков данных
• В качестве рабочего процесса для композитинга цифровых изображений для визуальных эффектов ^{[ править ]}
• Хранение деревьев Barnes-Hut, используемых для моделирования галактик

Терминология [ править ]

Узел представляет собой структуру , которая может содержать значение или состояние, или представлять собой отдельную структуру данных (который может быть деревом самостоятельно). Каждый узел в дереве имеет ноль или более дочерних узлов , которые находятся под ним в дереве (по соглашению деревья рисуются растущими вниз). Узел, имеющий дочерний узел, называется родительским узлом дочернего (или вышестоящим ). Узел имеет не более одного родителя, но возможно много узлов-предков , таких как родительский родитель. Дочерние узлы с одним и тем же родителем являются узлами-братьями .

Внутренний узел (также известный как внутренний узел , индексный дескриптор для короткого или узла ветви ) является любым узлом дерева , который имеет дочерние узлы. Точно так же внешний узел (также известный как внешний узел , листовой узел или конечный узел ) - это любой узел, не имеющий дочерних узлов.

Самый верхний узел в дереве называется корневым узлом . В зависимости от определения может потребоваться, чтобы у дерева был корневой узел (в этом случае все деревья непустые), или может быть разрешено быть пустым, и в этом случае оно не обязательно имеет корневой узел. Будучи самым верхним узлом, корневой узел не будет иметь родителя. Это узел, с которого начинаются алгоритмы в дереве, поскольку в качестве структуры данных можно переходить только от родителей к потомкам. Обратите внимание, что некоторые алгоритмы (например, поиск в глубину после упорядочения) начинаются с корня, но сначала посещают листовые узлы (получают доступ к значению листовых узлов), посещают корень только последним (т. , но только доступ к значению корня последним). Все остальные узлы могут быть доступны из него по ребрам или ссылкам. (В формальном определении каждый такой путь также уникален.) На диаграммах корневой узел обычно рисуется вверху. В некоторых деревьях, например в кучах , корневой узел имеет особые свойства. Каждый узел в дереве можно рассматривать как корневой узел поддерева, укорененного в этом узле.

Высота узла длина самого длинного пути вниз к листу из этого узла. Высота корня - это высота дерева. Глубина узла является длиной пути к корню (т.е. его корень путь ). Это обычно требуется при манипулировании различными самобалансирующимися деревьями, в частности деревьями AVL . Корневой узел имеет нулевую глубину, листовые узлы имеют нулевую высоту, а дерево только с одним узлом (следовательно, и корнем, и листом) имеет нулевую глубину и высоту. Обычно пустое дерево (дерево без узлов, если таковые разрешены) имеет высоту -1.

Поддерево дерева T представляет собой дерево , состоящее из узла Т и всех его потомков в T . ^{[a] [1]} Узлы, таким образом, соответствуют поддеревьям (каждый узел соответствует своему поддереву и всем его потомкам) - поддерево, соответствующее корневому узлу, является всем деревом, а каждый узел является корневым узлом поддерева, которое он определяет. ; поддерево, соответствующее любому другому узлу, называется собственным поддеревом (по аналогии с собственным подмножеством ).

Другие термины, используемые с деревьями:

Сосед

Родитель или ребенок.

Предок

Узел, достижимый путем повторного перехода от дочернего к родительскому.

Потомок

Узел, достижимый при повторном переходе от родителя к потомку. Также известен как дочерний ребенок .

Узел отделения

Внутренний узел

Узел по крайней мере с одним дочерним элементом.

Степень

Для данного узла его количество дочерних элементов. Лист обязательно имеет нулевую степень.

Степень дерева

Степень дерева - это максимальная степень узла в дереве.

Расстояние

Количество ребер на кратчайшем пути между двумя узлами.

Уровень

Уровень узла - это количество ребер на уникальном пути между ним и корневым узлом. ^{[2] [ необходима страница ]}

Ширина

Количество узлов на уровне.

Ширина

Количество листьев.

лес

Набор из n ≥ 0 непересекающихся деревьев.

Заказанное дерево

Корневое дерево, в котором для дочерних элементов каждой вершины указан порядок.

Размер дерева

Количество узлов в дереве.

Предварительное определение [ править ]

Дерево - это нелинейная структура данных по сравнению с массивами, связными списками, стеками и очередями, которые являются линейными структурами данных. Дерево может быть пустым без узлов или дерево представляет собой структуру, состоящую из одного узла, называемого корнем, и нуля или одного или нескольких поддеревьев.

Рисование деревьев [ править ]

Деревья часто рисуют в плоскости. Упорядоченные деревья могут быть представлены по существу однозначно на плоскости и поэтому называются плоскими деревьями следующим образом: если зафиксировать обычный порядок (скажем, против часовой стрелки) и расположить дочерние узлы в этом порядке (сначала входящее родительское ребро, затем первое дочернее ребро и т. д.), это дает вложение дерева в плоскость, единственное с точностью до объемлющей изотопии . И наоборот, такое вложение определяет порядок дочерних узлов.

Если поместить корень вверху (родители выше детей, как в семейном дереве ) и поместить все узлы, которые находятся на заданном расстоянии от корня (с точки зрения количества ребер: «уровень» дерева) на заданном горизонтальной линией получается стандартный рисунок дерева. Для двоичного дерева первый дочерний элемент находится слева («левый узел»), а второй дочерний элемент - справа («правый узел»).

Общие операции [ править ]

• Перечисление всех предметов
• Нумерация раздела дерева
• Поиск предмета
• Добавление нового элемента в определенную позицию в дереве
• Удаление объекта
• Обрезка : удаление целой части дерева.
• Прививка : добавление целого участка к дереву
• Нахождение корня для любого узла
• Нахождение наименьшего общего предка двух узлов

Методы обхода и поиска [ править ]

Переход по элементам дерева посредством связей между родителями и детьми называется ходьбой по дереву , а действие - обходом дерева. Часто операция может выполняться, когда указатель достигает определенного узла. Обход, при котором каждый родительский узел проходит до его дочерних узлов, называется обходом по предварительному заказу ; прогулка, при которой дети проходят путь до того, как пройдут их соответствующие родители, называется прогулкой после заказа ; обход левого поддерева узла, затем самого узла и, наконец, его правого поддерева, называется обходом по порядку . (Этот последний сценарий, относящийся к ровно двум поддеревьям, левому поддереву и правому поддереву, предполагает, в частности,бинарное дерево .) Обход по уровням эффективно выполняет поиск в ширину по всему дереву; узлы проходят уровень за уровнем, где сначала посещается корневой узел, за ним следуют его прямые дочерние узлы и их братья и сестры, за ними следуют его внучатые узлы и их братья и сестры, и т.д., пока не будут пройдены все узлы в дереве.

Представления [ править ]

Есть много разных способов представления деревьев; общие представления представляют узлы как динамически выделяемые записи с указателями на их дочерние элементы, их родители или и то, и другое, или как элементы в массиве , отношения между которыми определяются их позициями в массиве (например, двоичная куча ).

Действительно, двоичное дерево может быть реализовано как список списков (список, в котором значения являются списками): заголовок списка (значение первого члена) является левым дочерним элементом (поддеревом), а хвост (список второго и последующих членов) является правым потомком (поддеревом). Это также можно изменить, чтобы разрешить значения, как в S-выражениях Лиспа , где голова (значение первого члена) - это значение узла, голова хвоста (значение второго члена) - это левый дочерний элемент, а хвостик хвоста (список третьего и последующих терминов) - правый ребенок.

Как правило, узел в дереве не имеет указателей на своих родителей, но эта информация может быть включена (расширена структура данных, чтобы также включить указатель на родительский элемент) или сохранена отдельно. В качестве альтернативы восходящие ссылки могут быть включены в данные дочернего узла, как в многопоточном двоичном дереве .

Обобщения [ править ]

Диграфы [ править ]

Если ребра (к дочерним узлам) рассматриваются как ссылки, тогда дерево является частным случаем орграфа, и древовидная структура данных может быть обобщена для представления ориентированных графов путем удаления ограничений, что узел может иметь не более одного родителя, и что никакие циклы не допускаются. Ребра по-прежнему абстрактно рассматриваются как пары узлов, однако термины родительский и дочерний обычно заменяются другой терминологией (например, источник и цель ). Различные стратегии реализациисуществует: орграф может быть представлен той же локальной структурой данных, что и дерево (узел со значением и список дочерних элементов), при условии, что «список дочерних элементов» является списком ссылок, или глобально такими структурами, как списки смежности .

В теории графов , А дерево является связным ациклическим графом ; если не указано иное, в теории графов деревья и графы считаются неориентированными. Между такими деревьями и деревьями, как структура данных, нет однозначного соответствия. Мы можем взять произвольное неориентированное дерево, произвольно выбрать одну из его вершин в качестве корня , сделать все его ребра направленными, направив их в сторону от корневого узла, создавая древообразование, и назначить порядок всем узлам. Результат соответствует древовидной структуре данных. Выбор другого корня или другой порядок приводит к другому.

Для данного узла в дереве его дочерние элементы определяют упорядоченный лес (объединение поддеревьев, заданных всеми дочерними элементами, или, что эквивалентно, взятие поддерева, данное самим узлом, и стирание корня). Подобно тому, как поддеревья естественны для рекурсии (как при поиске в глубину), леса естественны для коркурсии (как и при поиске в ширину).

Посредством взаимной рекурсии лес можно определить как список деревьев (представленных корневыми узлами), где узел (дерева) состоит из значения и леса (его дочерние элементы):

f: [n [1], ..., n [k]]n: vf

Тип данных в сравнении со структурой данных [ править ]

Существует различие между деревом как абстрактным типом данных и конкретной структурой данных, аналогичное различию между списком и связанным списком .

Как тип данных дерево имеет значение и дочерние элементы, а сами дочерние элементы являются деревьями; значение и дочерние элементы дерева интерпретируются как значение корневого узла и поддеревьев дочерних элементов корневого узла. Чтобы разрешить конечные деревья, нужно либо разрешить список дочерних элементов быть пустым (в этом случае деревья могут быть непустыми, а «пустое дерево» вместо этого будет представлено лесом из нулевых деревьев), либо разрешить деревьям быть пустым, и в этом случае список дочерних элементов может иметь фиксированный размер ( коэффициент ветвления , особенно 2 или «двоичный»), если желательно.

В качестве структуры данных связанное дерево представляет собой группу узлов , где каждый узел имеет значение и список ссылок на другие узлы (его дочерние элементы). Также существует требование, чтобы никакие две «нисходящие» ссылки не указывали на один и тот же узел. На практике узлы в дереве обычно включают в себя и другие данные, такие как следующие / предыдущие ссылки, ссылки на их родительские узлы или почти что угодно.

Из-за использования ссылок на деревья в структуре данных связанного дерева деревья часто обсуждаются неявно, предполагая, что они представлены ссылками на корневой узел, поскольку часто именно так они и реализуются. Например, вместо пустого дерева может быть пустая ссылка: дерево всегда непусто, но ссылка на дерево может быть пустой.

Рекурсивный [ править ]

Рекурсивно, как тип данных, дерево определяется как значение (некоторого типа данных, возможно, пустое) вместе со списком деревьев (возможно, пустой список), поддеревья его дочерних элементов; символически:

t: v [t [1], ..., t [k]]

(Дерево t состоит из значения v и списка других деревьев.)

Более элегантно, с помощью взаимной рекурсии , одним из основных примеров которой является дерево, дерево может быть определено в терминах леса (списка деревьев), где дерево состоит из значения и леса (поддеревья его дети):

f: [t [1], ..., t [k]]

т: vf

Обратите внимание, что это определение дано в терминах значений и подходит для функциональных языков (оно предполагает ссылочную прозрачность ); разные деревья не имеют связей, поскольку представляют собой просто списки значений.

В качестве структуры данных дерево определяется как узел (корень), который сам состоит из значения (некоторого типа данных, возможно, пустого) вместе со списком ссылок на другие узлы (список, возможно, пустой, ссылки, возможно, нулевые ); символически:

n: v [& n [1], ..., & n [k]]

(Узел n состоит из значения v и списка ссылок на другие узлы.)

Эта структура данных определяет ориентированный граф ^[b], и для того, чтобы он был деревом, необходимо добавить условие к его глобальной структуре (его топологии), а именно, что не более одной ссылки может указывать на любой данный узел (узел имеет не более единственный родитель), и ни один узел в дереве не указывает на корень. Фактически, каждый узел (кроме корня) должен иметь ровно одного родителя, а корень не должен иметь родителей.

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

Теория типов [ править ]

В качестве абстрактного типа данных тип абстрактного дерева T со значениями некоторого типа E определяется с использованием типа абстрактного леса F (список деревьев) функциями:

значение: T → E

дети: T → F

ноль: () → F

узел: E × F → T

с аксиомами:

значение (узел ( e , f )) = e

дети (узел ( e , f )) = f

С точки зрения теории типов , дерево - это индуктивный тип, определяемый конструкторами nil (пустой лес) и node (дерево с корневым узлом с заданным значением и дочерними элементами).

Математическая терминология [ править ]

В целом древовидная структура данных представляет собой упорядоченное дерево , как правило, со значениями, прикрепленными к каждому узлу. Конкретно это (если требуется, чтобы он был непустым):

• Корневое дерево с направлением «от корня» (более узкое понятие является « древовидный »), что означает:
  • Ориентированный граф ,
  • базовый неориентированный граф которого является деревом (любые две вершины соединены ровно одним простым путем),
  • с выделенным корнем (одна вершина обозначается как корень),
  • который определяет направление на ребрах (стрелки указывают в сторону от корня; для данного ребра узел, на который указывает край, называется родительским, а узел, на который указывает ребро, называется дочерним ),

вместе с:

• упорядочение дочерних узлов данного узла и
• значение (некоторого типа данных) на каждом узле.

Часто деревья имеют фиксированный (точнее, ограниченный) фактор ветвления ( исходящую степень ), в частности, всегда есть два дочерних узла (возможно, пустые, следовательно, не более двух непустых дочерних узлов), следовательно, «двоичное дерево».

Разрешение пустых деревьев делает некоторые определения более простыми, некоторые - более сложными: корневое дерево должно быть непустым, следовательно, если пустые деревья разрешены, приведенное выше определение вместо этого становится «пустым деревом или корневым деревом такое, что ...». С другой стороны, пустые деревья упрощают определение фиксированного коэффициента ветвления: с разрешенными пустыми деревьями двоичное дерево - это дерево, в котором каждый узел имеет ровно два дочерних элемента, каждый из которых является деревом (возможно, пустым). Полный набор операций с деревом должен включать операцию разветвления.

Математическое определение [ править ]

Неупорядоченное дерево [ править ]

Математически неупорядоченное дерево ^[3] (или «алгебраическое дерево») ^[4] может быть определено как алгебраическая структура ( X , родительский элемент), где X - непустой несущий набор узлов, а родительский элемент - это функция на X, которая назначает каждый узел x его "родительский" узел, parent ( x ) . Структура подчиняется условию, что каждая непустая подалгебра должна иметь одну и ту же неподвижную точку . То есть должен существовать уникальный «корневой» узел r , такой, что parent ( r) = r, и для каждого узла x некоторый итеративный родительский элемент приложения (parent (⋯ parent ( x ) ⋯)) равен r .

Есть несколько эквивалентных определений.

В качестве ближайшей альтернативы можно определить неупорядоченные деревья как частичные алгебры ( X , родительские), которые получаются из полных алгебр, описанных выше, если родительский элемент ( r ) не определен. То есть корень r является единственным узлом, на котором не определена родительская функция, и для каждого узла x корень доступен из x в ориентированном графе ( X , родительский) . Это определение фактически совпадает с определением антидревесценции . В книге TAoCP используется терминориентированное дерево . ^[5]

Поле справа описывает частичную алгебру ( X , родитель) как реляционную структуру ( X , ≺) . Если (1) заменить на

тогда условие (2) становится избыточным.

Используя это определение, можно предоставить специальную терминологию для обобщений неупорядоченных деревьев, которые соответствуют выделенным подмножествам перечисленных условий:

• (1,2,3) - направленное псевдодерево ,
• (3) - направленный псевдолес ,
• (3,4) - неупорядоченный лес (компоненты которого - неупорядоченные деревья),
• (4) - ориентированный ациклический граф при условии , что X конечно,
• (1 ', 4) - ациклический доступный точечный граф (тогда условие (2) выполняется неявно).

Другим эквивалентным определением неупорядоченного дерева является определение теоретико-множественного дерева с однокорневым корнем и высотой не более ω ("конечное" дерево). ^[6] То есть алгебраические структуры ( X , родительские) эквивалентны частичным порядкам ( X , ≤), которые имеют верхний элемент r и каждое главное нарушение (также известный как главный фильтр ) является конечной цепочкой . Чтобы быть точным, мы должны говорить об обратном теоретико-множественном дереве, поскольку в теоретико-множественном определении обычно используется противоположный порядок.

Соответствие между ( X , parent) и ( X , ≤) устанавливается через рефлексивное транзитивное замыкание / редукцию , при этом редукция приводит к «частичной» версии без корневого цикла.

Определение деревьев в дескриптивной теории множеств (DST) использует представление частичных порядков ( X , ≥) как порядков префикса между конечными последовательностями. Оказывается, что с точностью до изоморфизма существует взаимно однозначное соответствие между (обратными) деревьями DST и древовидными структурами, определенными до сих пор.

Мы можем ссылаться на четыре эквивалентных характеристики дерева как алгебры , дерева как частичной алгебры , дерева как частичного порядка и дерева как префиксного порядка . Существует также пятое эквивалентное определение - коренное дерево в теории графов, которое представляет собой просто связный ациклический корневой граф .

Выражение деревьев как (частичных) алгебр (также называемых функциональными графами ) ( X , родительский) непосредственно следует за реализацией древовидных структур с использованием родительских указателей . Обычно используется частичная версия, в которой корневой узел не имеет определенного родителя. Однако в некоторых реализациях или моделях устанавливается даже родительская ( r ) = r цикличность. Известные примеры:

• Linux VFS, где «корневой dentry имеет d_parent, который указывает на себя». ^[7]
• Концепция дерева создания экземпляров ^{[8] [9] [10]}

из объектно-ориентированного программирования . В этом случае корневой узел - это верхний метакласс - единственный класс, который является прямым экземпляром самого себя.

Обратите внимание, что приведенное выше определение допускает бесконечные деревья. Это позволяет описывать бесконечные структуры, поддерживаемые некоторыми реализациями, с помощью ленивых вычислений . Ярким примером является бесконечная регрессия собственных классов из объектной модели Ruby . ^[11] В этой модели дерево, устанавливаемое посредством superclassсвязей между нетерминальными объектами, является бесконечным и имеет бесконечную ветвь (единственную бесконечную ветвь объектов-спиралей - см. Диаграмму ).

Братья и сестры [ править ]

В каждом неупорядоченном дереве ( X , родительском) есть выделенное разбиение множества X узлов на одноуровневые множества . Два некорневых узла x , y принадлежат одному набору братьев и сестер, если parent ( x ) = parent ( y ) . Корневой узел r образует одноэлементный родственный набор { r }. ^[c] Дерево называется локально конечным или конечно ветвящимся, если каждое из его родственных множеств конечно.

Каждая пара различных братьев и сестер несравнима в ≤ . Вот почему в определении используется слово « неупорядоченный» . Такая терминология может ввести в заблуждение, когда все одноуровневые множества являются одиночными, т.е. когда множество X всех узлов полностью упорядочено (и, следовательно, хорошо упорядочено ) на ≤. В таком случае мы могли бы вместо этого говорить об одинарном ветвящемся дереве .

Использование включения набора [ править ]

Как и любое частично упорядоченное множество, древовидные структуры ( X , ≤) могут быть представлены порядком включения - системами множеств, в которых ≤ совпадает с ⊆ , индуцированным порядком включения . Рассмотрим структуру ( U , ℱ) такую, что U - непустое множество, а ℱ - множество подмножеств U , для которых выполняются следующие условия ( согласно определению вложенной коллекции множеств ):

1. ∅ ∉ ℱ . (То есть ( U , ℱ) - гиперграф .)
2. U ∈ ℱ .
3. Для любых X , Y из ℱ , X ∩ Y ∈ {∅, X , Y }. (То есть ℱ - ламинарное семейство .) ^[12]
4. Для каждого X из ℱ , существует лишь конечное число Y от ℱ такое , что X ⊆ Y .

Тогда структура (ℱ, ⊆) является неупорядоченным дерево, корень которого равен U . Наоборот, если ( U , ≤) - неупорядоченное дерево, а ℱ - множество {↓ x | х ∈ U } все главные идеалы из ( U , ≤) , то множество системы ( U , ℱ) удовлетворяют указанные выше свойства.

Представление древовидной структуры в виде системы наборов обеспечивает семантическую модель по умолчанию - в большинстве наиболее популярных случаев древовидные структуры данных представляют собой иерархию включения . Это также предлагает обоснование для направления порядка с корнем наверху: корневой узел является большим контейнером, чем любой другой узел. Известные примеры:

• Структура каталогов файловой системы. Каталог содержит свои подкаталоги.
• DOM-дерево . Части документа, соответствующие узлам DOM, находятся во взаимосвязи частей согласно древовидной структуре.
• Единичное наследование в объектно-ориентированном программировании. Экземпляр класса также является экземпляром суперкласса.
• Иерархическая таксономия, такая как Десятичная классификация Дьюи, с частями возрастающей специфичности.
• BSP-деревья , квадродеревья , октодеревья , R-деревья и другие древовидные структуры данных, используемые для рекурсивного разделения пространства .

Хорошо обоснованные деревья [ править ]

Неупорядоченное дерево ( X , ≤) является хорошо обоснованным, если строгий частичный порядок < является хорошо обоснованным отношением . В частности, каждое конечное дерево хорошо обосновано. Если принять аксиому о зависимом выборе, дерево является хорошо обоснованным тогда и только тогда, когда у него нет бесконечной ветви.

Хорошо обоснованные деревья можно определять рекурсивно - путем формирования деревьев из несвязного объединения меньших деревьев. Для точного определения предположим, что X - это набор узлов. Используя рефлексивность частичных порядков, мы можем определить любое дерево ( Y , ≤) на подмножестве X с его частичным порядком (≤) - подмножество X × X . Множество ℛ всех отношений R , образующих обоснованное дерево ( Y , R ) на подмножестве Y в X , определяется на этапах ℛ_i , так что ℛ = ⋃ {ℛ _i | i - порядковый номер }. Для каждого порядкового номера i пусть R принадлежит i -й ступени ℛ _i тогда и только тогда, когда R равно

⋃ℱ ∪ ((dom (⋃ℱ) ∪ { x }) × { x })

где ℱ - подмножество ⋃ {ℛ _k | k < i } такое, что элементы ℱ попарно не пересекаются, а x - узел, не принадлежащий dom (⋃ℱ) . (Мы используем DOM ( S ) , чтобы обозначить область в виде отношения S ) . Заметим , что самая низкая ступень ℛ ₀ состоит из одного узла деревьев {( х , х )} , так как только пустой ℱ возможно. На каждом этапе (возможно) строятся новые деревья R , взяв лес ⋃ℱс компонентами ℱ из более низких ступеней и присоединением нового корня x поверх ⋃ℱ .

В отличие от высоты дерева, которая не превосходит ω, ранг хорошо обоснованных деревьев неограничен ^[13], см. Свойства « разворачивания ».

Использование рекурсивных пар [ править ]

В вычислениях общий способ определения хорошо обоснованных деревьев - через рекурсивные упорядоченные пары ( F , x ) : дерево - это лес F вместе со «свежим» узлом x . ^[14] лес Р , в свою очередь , возможно , является пустым множеством деревьев с попарно непересекающихся множеств узлов. Для точного определения действуйте так же, как при построении имен, используемых в теоретико-множественной технике принуждения. Пусть X - набор узлов. В надстройке над X определите множества T , ℱ деревьев и лесов соответственно и картуузлы: T → ℘ ( X ) присваивая каждому дереву t его базовый набор узлов так, чтобы:

(деревья над X )		t ∈ T	↔	t - пара ( F , x ) из ℱ × X такая, что для всех s ∈ F , x ∉ узлов ( s ) ,
(леса над X )		F ∈ ℱ	↔	F - это подмножество T такое, что для любых s , t ∈ F , s ≠ t , nodes ( s ) ∩ nodes ( t ) = ∅ }},
(узлы деревьев)		y ∈ узлов ( t )	↔	t = ( F , x ) ∈ T и либо y = x, либо y ∈ node ( s ) для некоторого s ∈ F }}.

Окружности в вышеуказанных условиях можно устранить , разделив каждый из T , ℱ и узлов на этапы, как в предыдущем подразделе. Впоследствии определим отношение «поддерево» ≤ на T как рефлексивное транзитивное замыкание отношения «непосредственного поддерева» ≺, определенного между деревьями формулой

с ≺ т

↔

s ∈ π 1 ( t )

где π ₁ ( т ) является проекцией из т на первую координату; то есть, это лес F такое , что т = ( F , х ) для некоторого х ∈ X . Можно заметить, что ( T , ≤) - многодерево : для любого t ∈ T главный идеал ↓ t, упорядоченный по ≤, является хорошо обоснованным деревом как частичный порядок. Более того, для любого дерева t ∈ T , его структура порядка «узлов» (nodes ( t ), ≤ _t ) задается формулой x ≤ _t y тогда и только тогда, когда существуют леса F , G ∈ ℱ такие, что и ( F , x ), и ( G , y ) являются поддеревьями t и ( F , x ) ≤ ( G , y ) .

Использование стрелок [ править ]

Другая формализация, а также обобщение неупорядоченных деревьев может быть получена путем материализации родительско-дочерних пар узлов. Каждую такую ​​упорядоченную пару можно рассматривать как абстрактную сущность - «стрелку». В результате получается мультидиграф ( X , A , s , t ), где X - набор узлов, A - набор стрелок , а s и t - функции от A до X, назначающие каждой стрелке ее источник и цель., соответственно. На конструкцию распространяются следующие условия:

1. ( A , s ○ t ^–1 ) - неупорядоченное дерево как полная алгебра.
2. Карта t - это взаимно однозначное соответствие стрелок и узлов.

В (1) символ композиции ○ следует интерпретировать слева направо. Условие говорит, что обратная последовательность стрелок ^[d] - это полное отображение дочерних элементов в родительские. Обозначим это родительское отображение между стрелками p , т.е. p = s ○ t ⁻¹ . Тогда у нас также есть s = p ○ t , поэтому мультидиграф, удовлетворяющий (1,2), также может быть аксиоматизирован как ( X , A , p , t ) с родительским отображением p вместо sкак определяющая составляющая. Обратите внимание, что корневая стрелка обязательно представляет собой петлю, т.е. ее источник и цель совпадают.

Важное обобщение вышеупомянутой структуры устанавливается, позволяя целевой карте t быть «многие к одному». Это означает, что (2) ослабляется до

(2 ') t- карта сюръективна - каждый узел является целью некоторой стрелки.

Обратите внимание, что условие (1) утверждает, что только листовые стрелки могут иметь одну и ту же цель. То есть, ограничение на т в диапазоне от р до сих пор инъективны .

Мультидиграфы, удовлетворяющие (1,2 '), можно назвать «деревьями стрелок» - их характеристики дерева накладываются на стрелки, а не на узлы. Эти структуры можно рассматривать как наиболее существенную абстракцию Linux VFS, поскольку они отражают жесткую структуру файловых систем. Узлы называются inodes , стрелки - dentries (или жесткими ссылками ). Родитель и целевой отображает р и т соответственно представлен d_parentи d_inodeполя в структуре dentry данных. ^[15] Каждому inode назначается фиксированный тип файла, для которого тип каталога играет особую роль «спроектированных родителей»:

Использование пунктирного стиля для первой половины корневого цикла означает, что, как и в случае с родительской картой, существует частичная версия для исходной карты s, в которой источник корневой стрелки не определен. Этот вариант используется для дальнейшего обобщения, см. # Использование путей в мультидиграфе .

Использование путей в орграфе [ править ]

Неупорядоченные деревья естественным образом возникают в результате «развертывания» доступных точечных графов . ^[16]

Пусть ℛ = ( X , R , r ) - указанная реляционная структура , то есть такая, что X - это набор узлов, R - отношение между узлами (подмножество X × X ), а r - выделенный «корневой» узел. . Предположим далее , что ℛ является доступным , что означает , что Х равно прообраза из { г } при рефлексивном транзитивного замыкания R , и вызвать такую структуру , в доступной заостренный граф или APGДля короткого (⁎) Тогда можно вывести другой попутный газ. ℛ '= ( X ' R ' , г ' ) - The разворачивающийся из ℛ - следующий образом :

• X ' - это набор обратных путей к r , то есть набор непустых конечных последовательностей p узлов (элементов X ) таких, что (a) последовательные элементы p имеют обратную R-связь , и (b) первый член из p - корень r ,
• R « представляет собой соотношение между дорожками из X» , таким образом, что пути р и д являются R» , о связанных тогда и только тогда , когда р = д ⁎ [ х ] для некоторого узла х (т.е. д является максимальным собственно префикс из р , то" Popped " p ), и
• r ' - одноэлементная последовательность [ r ] .

Очевидно, структура ( X ' , R ' ) является неупорядоченным деревом в версии «частичной алгебры»: R ' - это частичное отображение, которое связывает каждый некорневой элемент X ' с его родителем путем извлечения пути. Корневой элемент, очевидно, r ' . Кроме того, выполняются следующие свойства:

• ℛ изоморфна ее разворачивания ℛ» тогда и только тогда , когда ℛ дерево (⁑). (В частности, развертывание идемпотентно с точностью до изоморфизма.)
• Разворачивание сохраняет обоснованность: если R хорошо обосновано, то R ' тоже .
• Развертывание сохраняет ранг: если R хорошо обосновано, то ранги R и R ' совпадают.

Примечания:

(⁎) Чтобы установить соответствие между R и родительской картой, представленное определение использует обратную доступность: r достижимо из любого узла. В первоначальном определении по П. Aczél , ^[16] каждый узел достижим из г (таким образом, вместо того , чтобы «прообраза», слово «изображение» применяется). ^[e]

(⁑) Мы неявно ввели определение неупорядоченных дерев как АПГ: вызовите APG ℛ = ( X , R , R ) на дерево , если редукт ( X , R ) представляет собой неупорядоченное дерево в качестве частичной алгебры. Это можно перевести как: Каждый узел доступен только по одному пути.

Использование путей в мультидиграфе [ править ]

Как показано на примере жестко-связанной структуры файловых систем, многие структуры данных в вычислениях допускают множественные связи между узлами. Поэтому, для того , чтобы правильно выставить внешний вид неупорядоченных деревьев среди структур данных, необходимо обобщить доступные остроконечные графики для multidigraph настройки. Чтобы упростить терминологию, мы используем термин « колчан», который является устоявшимся синонимом слова «мультиграф».

Пусть доступный остроконечный колчан или для краткости apq определен как структура

ℳ = ( X , A , s , t )

куда

X - это набор узлов ,

A - это набор стрелок ,

s - это частичная функция от A до X ( исходная карта), а

t - это общая функция от A до X ( целевая карта).

Таким образом, ℳ - это «частичный мультииграф».

На конструкцию распространяются следующие условия:

1. Существует ровно одна «корневая» стрелка a _r , источник которой s ( a _r ) не определен.
2. Каждый узел x ∈ X достижим с помощью конечной последовательности последовательных стрелок, начинающихся с корневой стрелки a _r .

ℳ называется деревом, если целевая карта t является биекцией между стрелками и узлами. Разворачивание из ℳ образована последовательности , указанных в (2) - которые являются путями доступности (см Пути алгебра ). В качестве apq развертывание можно записать как

ℳ '= ( X ' , A ' , s ' , t ' )

куда

X ' - это набор путей доступности,

A ' совпадает с X' ,

s ' совпадает с появлением пути, а

t ' - тождество на X' .

Как и в случае с apgs, развертывание идемпотентно и всегда приводит к дереву.

, Лежащая в основе APG получается как структура

( X , R , t ( a _r ))

куда

R = {( t ( a ), s ( a )) | ∈ \ { _г }} .

На диаграмме выше показан пример APQ со стрелками 1 + 14. В JavaScript , Python или Ruby структуру можно создать с помощью следующего (точно такого же) кода:

г  =  {};  г [ 1 ]  =  {};  г [ 2 ]  =  г [ 1 ];  г [ 3 ]  =  {};  г [ 4 ]  =  {};  г [ 1 ] [ 5 ]  =  {};  г [ 1 ] [ 14 ]  =  г [ 1 ] [ 5 ]; г [ 3 ] [ 7 ]  =  {};  р[ 3 ] [ 8 ]  =  г [ 3 ] [ 7 ];  г [ 3 ] [ 13 ]  =  {}; г [ 4 ] [ 9 ]  =  г [ 4 ];  г [ 4 ] [ 10 ]  =  г [ 4 ];  г [ 4 ] [ 11 ]  =  {}; г [ 3 ] [ 7 ] [ 6 ]  =  г[ 3 ];  г [ 3 ] [ 7 ] [ 12 ]  =  г [ 1 ] [ 5 ];

Использование имен [ править ]

Неупорядоченные деревья и их обобщения составляют сущность систем именования . Есть два ярких примера систем именования: файловые системы и (вложенные) ассоциативные массивы . Структуры на основе нескольких графов из предыдущих подразделов обеспечивали анонимные абстракции для обоих случаев. Чтобы получить возможность именования, стрелки должны быть снабжены именами в качестве идентификаторов . Имя должно быть локально уникальным - внутри каждого родственного набора стрелок ^[f] может быть не более одной стрелки, помеченной данным именем.

Это можно формализовать как структуру

ℰ = ( X , Σ , A , s , σ , t )

куда

X - это набор узлов ,

Σ - это набор имен ,

A - это набор стрелок ,

s - частичная функция от A до X ,

σ - частичная функция от A до Σ , и

т является полной функцией от А до X .

Для стрелкой , составляющие тройной ( с ( ), σ ( ), т ( )) , соответственно , «с источником , имя и целевой . На конструкцию распространяются следующие условия:

1. Редукт ( X , A , s , t ) - это остроконечный колчан с доступом (apq), как определено ранее.
2. Функция имени σ не определена только для корневой стрелки без источника.
3. Именная функция σ инъективна в ограничении на каждый родственный набор стрелок, т. Е. Для любых некорневых стрелок a , b , если s ( a ) = s ( b ) и σ ( a ) = σ ( b ), то a = б .

Эту структуру можно назвать вложенным словарем или apq . В вычислительной технике такие структуры встречаются повсеместно. Приведенная выше таблица показывает, что стрелки можно считать «невещественными» как множество A ' = {( s ( a ), σ ( a ), t ( a )) | a ∈ A \ { a _r }} троек источник-имя-цель. Это приводит к реляционной структуре ( X , Σ, A ' ), которую можно рассматривать как таблицу реляционной базы данных . Подчеркивание в sourceиnameуказать первичный ключ .

Структуру можно перефразировать как детерминированную систему помеченных переходов : X - это набор «состояний», Σ - набор «меток», A ' - набор «помеченных переходов». (Более того, корневой узел r = t ( a _r ) является «начальным состоянием», а условие доступности означает, что каждое состояние достижимо из начального состояния.)

На диаграмме справа показан вложенный словарь ℰ, который имеет тот же базовый мультидиграф, что и в примере в предыдущем подразделе. Структура может быть создана с помощью кода ниже. Как и раньше, точно такой же код применяется для JavaScript, Python и Ruby.

Во- первых, подструктуры , ℰ ₀ , создается с помощью одного присвоения литерала {...} к r. Эта структура, изображенная сплошными линиями, представляет собой « дерево стрелок » (следовательно, это остовное дерево ). Буквальное , в свою очередь , как представляется, JSON сериализации E эл ₀ .

Впоследствии остальные стрелки создаются путем присвоения уже существующих узлов. Стрелки, вызывающие циклы, отображаются синим цветом.

r  =  { "a" : { "a" : 5 , "b" : 5 }, "c" : { "a" : { "w" : 5 }, "c" : {}}, "d" : { "w" : 1.3 }}г [ "б" ]  =  г [ "а" ];  r [ "c" ] [ "b" ]  =  r [ "c" ] [ "a" ] r [ "c" ] [ "a" ] [ "p" ]  =  r [ "c" ];  r [ "d" ] [ "e" ]  =  r [ "d" ] [ "self" ]  =  r [ "d"]

В Linux VFS функция имени σ представлена d_nameполем в структуре данных dentry. ^[15] Приведенная выше структура ℰ ₀ демонстрирует соответствие между JSON-представляемыми структурами и жестко связанными структурами файловых систем. В обоих случаях существует фиксированный набор встроенных типов «узлов», один из которых является типом контейнера, за исключением того, что в JSON на самом деле существует два таких типа - Object и Array. Если последний игнорируется (а также различие между отдельными примитивными типами данных), то предоставленные абстракции файловых систем и данных JSON одинаковы - оба являются деревьями стрелок, снабженными наименованием σ и различием узлов-контейнеров.

Пути [ править ]

Функция именования σ вложенного словаря ℰ естественным образом распространяется от стрелок до путей стрелок. Каждой последовательности p = [ a ₁ , ..., a _n ] последовательных стрелок неявно назначается путь (см. Pathname ) - последовательность σ ( p ) = [ σ ( a ₁ ), ..., σ ( a _n )] названий стрелок. ^[грамм]Локальная уникальность переносится на пути стрелок: разные одноуровневые пути имеют разные имена. В частности, пути стрелок, ведущих к корню, находятся во взаимно однозначном соответствии со своими именами путей. Это соответствие обеспечивает «символическое» представление развертывания ℰ через имена путей - узлы в ℰ глобально идентифицируются через дерево имен путей.

Упорядоченное дерево [ править ]

Структуры, представленные в предыдущем подразделе, образуют лишь базовую «иерархическую» часть древовидных структур данных, которые появляются в вычислениях. В большинстве случаев существует также дополнительное «горизонтальное» упорядочение между братьями и сестрами. В деревьях поиска порядок обычно устанавливается «ключом» или значением, связанным с каждым из братьев и сестер, но во многих деревьях это не так. Например, документы XML, списки в файлах JSON и многие другие структуры имеют порядок, который не зависит от значений в узлах, но сам является данными - сортировка абзацев романа по алфавиту приведет к потере информации. ^{[ сомнительно - обсудить ]}

Соответствующее расширение ранее описанных древовидных структур ( X , ≤) можно определить, наделив каждый одноуровневый набор линейным порядком следующим образом. ^{[18] [19]}

Альтернативное определение по Кубояме ^[3] представлено в следующем подразделе.

Заказал дерево представляет собой структуру ( X , ≤ _V , ≤ _S ) , где Х представляет собой непустое множество узлов и ≤ _V и ≤ _S являются отношения на X называется v ertical (или также иерархическое ^[3] ) порядок и ы ibling порядок соответственно. На конструкцию распространяются следующие условия:

1. ( X , ≤ _V ) - это частичный порядок, который является неупорядоченным деревом, как определено в предыдущем подразделе.
2. ( X , ≤ _S ) - частичный порядок.
3. Отдельные узлы сравнимы в < _S тогда и только тогда, когда они являются братьями и сестрами:

   (< _S ) ∪ (> _S ) = ((≺ _V ) ○ (≻ _V )) ∖ идентификатор Х .

4. Каждый узел имеет только конечное число предыдущих братьев и сестер, т.е. каждый главный идеал ( X , ≤ _S ) конечен. (Это условие можно опустить в случае конечных деревьев.)

Условия (2) и (3) говорят, что ( X , ≤ _S ) является покомпонентным линейным порядком, каждый компонент является родственным набором. Условие (4) утверждает, что если одноуровневое множество S бесконечно, то ( S , ≤ _S ) изоморфно (ℕ, ≤) , обычному порядку натуральных чисел.

Учитывая это, есть три (другие) выделенные частичные приказы, которые однозначно задаются следующими предписаниями:

(< H )	знак равно	(≤ V ) ○ (< S ) ○ (≥ V )	( ч порядка orizontal ),
(< L⁻ )	знак равно	(> V ) ∪ (< H )	( "несогласный" л в порядке ),
(< L⁺ )	знак равно	(< V ) ∪ (< H )	( «согласный» л в порядке приема ).

Это составляет систему «VSHL ^± » из пяти частичных порядков ≤ _V , ≤ _S , ≤ _H , ≤ _L⁺ , ≤ _L⁻ на одном и том же множестве узлов X , в которой, за исключением пары {≤ _S , ≤ _H }, любые два отношения однозначно определяют остальные три, см. таблицу определенности .

Примечания об условных обозначениях:

• Композиция отношение символ ○ используемая в этом пункте должны быть интерпретировано влево-вправо (как ).${\ displaystyle \ circ _ {l}}$
• Символы < и ≤ обозначают строгую и нестрогую версии частичного порядка.
• Символы > и ≥ выражают обратные отношения.
• ≺ символ используется для покрывающей связи с ≤ который является непосредственной версией частичного порядка.

Это дает шесть версий ≺, <, ≤, ≻,>, ≥ для одного отношения частичного порядка. За исключением ≺ и ≻ , каждая версия однозначно определяет другие. Для перехода от ≺ к < требуется, чтобы < был транзитивно приводимым. Это всегда выполняется для всех < _V , < _S и < _H, но может не выполняться для < _L⁺ или < _L⁻, если X бесконечно.

Частичные порядки ≤ _V и ≤ _H являются дополнительными:

(< _V ) ⊎ (> _V ) ⊎ (< _Н ) ⊎ (> _Н ) = Х × Х ∖ идентификатор _Х .

Как следствие, «согласные» линейный порядок < _L⁺ является линейным расширением по < _V . Точно так же, < _L⁻ является линейным расширением > _V .

Накрытия Отношения ≺ _L⁻ и ≺ _L⁺ соответствуют предварительно порядка обхода и после заказа обхода , соответственно. Если x ≺ _L⁻ y, то, в зависимости от того, есть ли у y предыдущий брат или нет, узел x является либо «самым правым» нестрогим потомком предыдущего брата y, либо, в последнем случае, x является первым дочерним элементом. из y . Пары последнего случая образуют отношение (≺ _L⁻ ) ∖ (< _H ), которое является частичным отображением, которое присваивает каждому нелистовому узлу его${\ Displaystyle (х, у)}$первый дочерний узел. Аналогичным образом (≻ _L⁺ ) _∖ (> _H ) назначает каждому нелистовому узлу конечное число потомков его последний дочерний узел.

Определение с использованием горизонтального порядка [ править ]

Определение Кубоямы «упорядоченных деревьев с корнями» ^[3] использует горизонтальный порядок ≤ _H в качестве определяющего отношения. ^[h] (См. также Suppes. ^[20] )

Используя введенные обозначения и терминологию, определение можно выразить следующим образом.

Заказал дерево представляет собой структуру ( X , ≤ _V , ≤ _Н ) таким образом, что условия (1-5) удовлетворены:

1. ( X , ≤ _V ) - частичный порядок, являющийся неупорядоченным деревом . (The v ertical порядок.)
2. ( X , ≤ _H ) - частичный порядок. (The ч orizontal заказ.)
3. Частичных порядков ≤ _V и ≤ _Н дополняют друг друга: (< _V ) ⊎ (> _V ) ⊎ (< _Н ) ⊎ (> _Н ) = Х × Х ∖ идентификатор _Х .

   (То есть пары узлов, которые несравнимы в (< _V ) , сопоставимы в (< _H ) и наоборот.)

4. Частичные порядки ≤ _V и ≤ _H являются «согласованными»: (< _H ) = (≤ _V ) ○ (< _H ) ○ (≥ _V ) .

   (То есть для любых узлов x , y таких, что x < _H y , все потомки x должны предшествовать всем потомкам y .)

5. У каждого узла есть только конечное число предыдущих братьев и сестер. (То есть для каждого бесконечного одноуровневого множества S , ( S , ≤ _H ) имеет порядковый тип натуральных чисел.) (Как и раньше, это условие можно опустить в случае конечных деревьев.)

Порядок братьев и сестер (≤ _S ) получается следующим образом: (< _S ) = (< _H ) ∩ ((≺ _V ) ○ (≻ _V )) , т.е. два различных узла находятся в порядке братьев и сестер тогда и только тогда, когда они расположены в горизонтальном порядке и братья и сестры.

Таблица детерминации [ править ]

В следующей таблице показана детерминированность системы «VSHL ^± ». Выражения отношения в теле таблицы равны одному из < _V , < _S , < _H , < _L⁻ или < _{L⁺ в} зависимости от столбца. Отсюда следует, что, за исключением пары {≤ _S , ≤ _H }, упорядоченное дерево ( X , ...) однозначно определяется любыми двумя из пяти отношений.

В последних двух строках, инф _L⁻ ( Y ) обозначает нижнюю грань из Y в ( X , ≤ _L⁻ ) , и вечерять _L⁺ ( Y ) обозначает грань из Y в ( X , ≤ _L⁺ ) . В обеих строках (≤ _S ) соотв. (≥ _S ) может быть эквивалентно заменено родственной эквивалентностью (≤ _S ) ○ (≥ _S ). В частности, разбиение на одноуровневые множества вместе с любым из ≤ _L⁻ или ≤ _L⁺ также достаточно для определения упорядоченного дерева. Первое предписание для ≺ _V может быть прочитано так: родитель некорневого узла x равен точной нижней грани множества всех непосредственных предшественников братьев и сестер x , где слова «infimum» и «предшественники» имеют в виду ≤ _L⁻ . Аналогично второму рецепту, просто используйте «супремум», «преемники» и ≤ _L⁺ .

Очевидно, что отношения ≤ _S и ≤ _H не могут образовывать определяющую пару. В качестве простейшего примера рассмотрим упорядоченное дерево ровно с двумя узлами - тогда нельзя сказать, какой из них является корнем.

Оси XPath [ править ]

В таблице справа показано соответствие введенных отношений осям XPath , которые используются в системах структурированных документов для доступа к узлам, которые имеют определенные отношения упорядочения к начальному «контекстному» узлу. Для узла контекста ^[21] х , его ось назван спецификатором в левой колонке есть множество узлов, равно изображение из { х } под корреспондентскими связями. Начиная с XPath 2.0 , узлы «возвращаются» в порядке документа , который является «несогласованным» линейным порядком ≤ _L⁻ . Было бы достигнуто "согласование",если вертикальный порядок ≤ _Vбыл задан противоположным образом, с направлением снизу вверх к корню, как в теории множеств в соответствии с естественными деревьями . ^[я]

Карты обхода [ править ]

Ниже приведен список частичных карт , которые обычно используются для упорядоченного обхода дерева. ^[22] Каждая карта представляет собой выделенную функциональную подотношение ≤ _L⁻ или ее противоположность.

• ≺ _V ... частичное отображение родительского узла ,
• ≻ _S ... частичное отображение предыдущего брата ,
• ≺ _S ... частичное отображение следующего брата ,
• (≺ _L⁻ ) ∖ (< _H ) ... частичное отображение первого ребенка ,
• (≻ _L⁺ ) _∖ (> _H ) ... частичное отображение последнего ребенка ,
• ≻ _L⁻ ... частичное отображение предыдущего узла ,
• ≺ _L⁻ ... частичное отображение следующего узла .

Генерация структуры [ править ]

Карты обхода составляют частичную унарную алгебру ^[23] ( X , parent, previousSibling, ..., nextNode), которая формирует основу для представления деревьев как связанных структур данных . По крайней мере, концептуально существуют родительские ссылки, родственные связи смежности и первые / последние дочерние ссылки. Это также относится к неупорядоченным деревьям в целом, что можно наблюдать в структуре данных dentry в Linux VFS. ^[24]

Подобно системе частичных порядков "VSHL ^± ", существуют пары карт обхода, которые однозначно определяют всю упорядоченную древовидную структуру. Естественно, одна из таких генерирующих структур - это ( X , _V , _S ), которую можно записать как ( X , parent, nextSibling) - структуру родительских и соседних ссылок. Другой важной генерирующей структурой является ( X , firstChild, nextSibling), известная как двоичное дерево левого потомка и правого брата . Эта частичная алгебра устанавливает взаимно однозначное соответствие между бинарными деревьями и упорядоченными деревьями.

Определение с использованием бинарных деревьев [ править ]

Соответствие бинарным деревьям дает краткое определение упорядоченных деревьев как частичных алгебр.

Заказали дерево представляет собой структуру , где Х представляет собой непустое множество узлов, и LC , RS представляют собой частичные карты на X называются л eft- с Хильдами и г ight- с ibling , соответственно. На конструкцию распространяются следующие условия:${\ displaystyle (X, lc, rs)}$

1. Частичные отображения lc и rs не пересекаются, т.е. ( lc ) ∩ ( rs ) = ∅ .
2. Обратное к ( lc ) ∪ ( rs ) - это частичное отображение p такое, что частичная алгебра ( X , p ) является неупорядоченным деревом.

Структура частичного порядка ( X , ≤ _V , ≤ _S ) получается следующим образом:

(≺ S )	знак равно	( rs ) ,
(≻ V )	знак равно	( lc ) ○ (≤ S ) .

Кодирование последовательностями [ править ]

Упорядоченные деревья можно естественным образом закодировать конечными последовательностями натуральных чисел. ^{[25] [j]} Обозначим ω ^⁎ множество всех конечных последовательностей натуральных чисел. Тогда любое непустое подмножество W в ω ^⁎ , замкнутое относительно взятия префиксов, порождает упорядоченное дерево: возьмем порядок префиксов для ≥ _V и лексикографический порядок для ≤ _L⁻ . И наоборот, для упорядоченного дерева T = ( X , _V , ≤ _L⁻ ) назначьте каждому узлу x последовательность${\ Displaystyle ш (х)}$индексов братьев и сестер, т.е. корню присваивается пустая последовательность, и для каждого некорневого узла x пусть w ( x ) = w (parent ( x )) ⁎ [ i ], где i - количество предшествующих братьев и сестер x и ⁎ - оператор конкатенации . Положим W = { w ( x ) | x ∈ X }. Тогда W с индуцированными порядками ≤ _V (обратный к префиксному порядку) и ≤ _L⁻(лексикографический порядок), изоморфно T .

Поуровневый заказ [ править ]

В качестве возможного расширения системы «VSHL ^± » могут быть определены другие отличительные отношения между узлами, основанные на структуре уровней дерева . Во-первых, обозначим через ∼ _E отношение эквивалентности, определяемое как x ∼ _E y, тогда и только тогда, когда x и y имеют одинаковое количество предков. Это дает разбиение множества узлов на уровни L ₀ , L ₁ , ... (, L _n ) - грубое разбиение на одноуровневые множества . Затем определим отношения <_E , < _B⁻ и < _B⁺ по

${\ displaystyle {\ begin {align} \ left (<_ {\ mathrm {E}} \ right) & = \ left (<_ {\ mathrm {H}} \ right) \ cap \ left (\ sim _ { \ mathrm {E}} \ right) & {\ text {((по) порядку уровней),}} \\\ left (<_ {\ mathrm {B} ^ {-}} \ right) & = \ left ( <_ {\ mathrm {E}} \ right) \ cup \ left (\ left (\ sim _ {\ mathrm {E}} \ right) \ circ \ left (> _ {\ mathrm {V}} \ right) \ right) & {\ text {(порядок в ширину, порядок BFS),}} \\\ left (<_ {\ mathrm {B} ^ {+}} \ right) & = \ left (<_ {\ mathrm {E}} \ right) \ cup \ left (\ left ({<} _ {\ mathrm {V}} \ right) \ circ \ left (\ sim _ {\ mathrm {E}} \ right) \ right ) & {\ text {(постпорядок в ширину).}} \ end {выровнен}}}$

Можно заметить, что < _E - строгий частичный порядок, а < _B⁻ и < _B⁺ - строгие полные порядки. Кроме того, существует сходство между системами «VSL ^± » и «VEB ^± »: < _E покомпонентно линейно и ортогонально < _V , < _B⁻ является линейным продолжением < _E и > _V , а < _B⁺ является линейным продолжением < _E и < _V .

См. Также [ править ]

• Древовидная структура
• Дерево (теория графов)
• Дерево (теория множеств)
• Кардинальное дерево и Порядковое дерево
• Иерархия (математика)
• Диалоговое дерево
• Одиночное наследование
• Генеративная грамматика
• Иерархическая кластеризация
• Дерево разделов двоичного пространства
• Рекурсия
• Фенвик дерево

Другие деревья [ править ]

• Trie
• Алгоритм Дэй – Стаута – Уоррена
• Анфилады
• Бинарное дерево левого потомка и правого брата
• Иерархическая временная память

Примечания [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Дональд Кнут . Искусство программирования : основные алгоритмы , третье издание. Аддисон-Уэсли, 1997. ISBN 0-201-89683-4 . Раздел 2.3: Деревья, стр. 308–423. 
• Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Раздел 10.4: Представление корневых деревьев, стр. 214–217. Главы 12–14 (Деревья двоичного поиска, красно-черные деревья, дополнительные структуры данных), стр. 253–320. 

Внешние ссылки [ править ]

Викискладе есть медиафайлы по теме древовидных структур .

• Деревья данных как средство представления комплексного анализа данных Салли Книп, 8 августа 2013 г.
• Описание из Словаря алгоритмов и структур данных
• CRAN - Пакет data.tree, реализация древовидной структуры данных на языке программирования R
• WormWeb.org: интерактивная визуализация дерева клеток C. elegans - визуализация всего дерева происхождения клеток нематоды C. elegans (javascript)
• Бинарные деревья Л. Эллисон