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

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

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

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

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

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

• Представление иерархических данных, таких как:
  • Абстрактные синтаксические деревья для компьютерных языков
  • Разбирать деревья для человеческих языков
  • Объект Document Модели из 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 .

Окружности в вышеуказанных условиях можно устранить , разделив каждый из 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 назначается фиксированный тип файла, для которого тип каталога играет особую роль «спроектированных родителей»:

(a) только inodes каталогов могут отображаться как источник жесткой ссылки, и

(b) индексный дескриптор каталога не может быть целью более одной жесткой ссылки.

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

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

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

Пусть ℛ = ( X , R , r ) - указанная реляционная структура , т.е. такая, что X - это набор узлов, R - отношение между узлами (подмножество X × X ), а r - выделенный «корневой» узел. . Предположим далее , что ℛ является доступным , что означает , что Х равно прообраза из { г } при рефлексивном транзитивного замыкания R , и вызвать такую структуру , в доступной заостренный граф или APGкоротко. ^{[APG 2]} Тогда можно извлечь другой попутный газ ℛ '= ( 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 ' . Кроме того, выполняются следующие свойства:

• ℛ изоморфен ее разворачивание ℛ» тогда и только тогда , когда ℛ дерево. ^{[apg 3]} (В частности, развертывание идемпотентно с точностью до изоморфизма.)
• Развертывание сохраняет обоснованность: если R хорошо обосновано, то R ' тоже .
• Развертывание сохраняет ранг: если R хорошо обосновано, то ранги R и 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 ' совпадает с выталкиванием пути, и т 'есть тождество на X ' . Как и в случае с apgs, развертывание идемпотентно и всегда приводит к дереву.

Лежащий в основе APG получают в виде структуры ( Х , R , T ( _г )) , где R = {( т ( ), с ( )) | a ∈ A \ { a _r }} .

На диаграмме выше показан пример 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 ];

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

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

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

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

где X - набор узлов , Σ - набор имен , A - набор стрелок , s - частичная функция от A до X , σ - частичная функция от A до Σ , а t - полная функция от A для X . Для стрелки a составляющие тройки ( s ( a ), σ ( a ), t ( a ))соответственно «S источник , имя и цель .

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

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 ℰ ₀ .

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

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 одинаковы - оба являются деревьями стрелок, снабженными наименованием σ и различием узлов-контейнеров.

См. #Nested data для формального описания древовидных структур («JSON-деревьев») с различением и разделением узлов контейнера.

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

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

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

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

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

Альтернативное определение по Кубояме ^[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 является первым дочерним элементом. от у . Пары последнего случая образуют отношение (≺ _L⁻ ) ∖ (< _H ), которое является частичным отображением, которое назначает каждому нелистовому узлу его${\ Displaystyle (х, у)}$первый дочерний узел. Точно так же (≻ _L⁺ ) _∖ (> _H ) назначает каждому нелистовому узлу конечное число дочерних узлов его последний дочерний узел.

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

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

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

Заказал дерево представляет собой структуру ( 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 , которые используются в системах структурированных документов для доступа к узлам, несущим особые отношения упорядочения к начальному «контекстному» узлу. Для узла контекста ^[20] х , его ось назван спецификатором в левой колонке есть множество узлов, равно изображение из { х } под корреспондентскими связями. Начиная с XPath 2.0 , узлы «возвращаются» в порядке документа , который является «несогласованным» линейным порядком ≤ _L⁻ . «Согласие» будет достигнуто,если вертикальный порядок ≤ _Vбыл задан противоположным образом, с направлением снизу вверх наружу от корня, как в теории множеств в соответствии с естественными деревьями . ^[час]

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

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

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

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

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

Подобно системе частичных порядков «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 ) .

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

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

${\displaystyle {\begin{aligned}\left(<_{\mathrm {E} }\right)&=\left(<_{\mathrm {H} }\right)\cap \left(\sim _{\mathrm {E} }\right)&{\text{((per) level order),}}\\\left(<_{\mathrm {B} ^{-}}\right)&=\left(<_{\mathrm {E} }\right)\cup \left(\left(\sim _{\mathrm {E} }\right)\circ \left(>_{\mathrm {V} }\right)\right)&{\text{(breadth-first order, BFS ordering),}}\\\left(<_{\mathrm {B} ^{+}}\right)&=\left(<_{\mathrm {E} }\right)\cup \left(\left({<}_{\mathrm {V} }\right)\circ \left(\sim _{\mathrm {E} }\right)\right)&{\text{(breadth-first post-order).}}\end{aligned}}}$

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

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

Упорядоченные деревья можно естественным образом закодировать конечными последовательностями натуральных чисел. ^{[24] [i]} Обозначим ℕ ^⁎ множество всех конечных последовательностей натуральных чисел. Непустая подмножество W из ℕ ^⁎ называется доменом дерева ^{[25] [26]} , если для всех U , V от ℕ ^⁎ и все я , J от ℕ имеет место следующего ( ⁎ представляет собой конкатенацию оператор):

1. Если у ⁎ v ∈ W ,   то   U ∈ W . ( W - это префикс -закрытый.)
2. Если у ⁎ [ я ] ∈ W и J < я ,   то   у ⁎ [ J ] ∈ W . ( W - закрытый левый брат.)

Индуцированная структура на W порождает упорядоченное дерево: возьмите префиксный порядок для ≥ _V и лексикографический порядок для ≤ _L⁻ . ^[j]

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

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

r  =  [[ 5 , 5 ], [[ 5 ], []], [[ 1.3 ]]] r [ 3 ]  =  r [ 0 ]  r [ 1 ] [ 2 ]  =  r [ 1 ] [ 0 ] r [ 1 ] [ 0 ] [ 1 ]  =  r [ 1 ]  r [ 2 ] [ 2 ]  =  r [ 2 ] [ 1 ] =  г [ 2 ]

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

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

Код применим к JavaScript и Ruby. В Python изменяющие присваивания запрещены из-за использования одноуровневых индексов, которых нет в исходной структуре. ^[k]

Вложенные данные [ править ]

Понятия вложенного словаря и вложенного списка (которые являются обобщениями неупорядоченных / упорядоченных деревьев соответственно) могут быть объединены в объединяющую концепцию вложенных данных . Такие структуры наиболее популярны в связи с форматом данных JSON . Эти структуры представляют собой мультидиграфы с выделенным набором узлов-контейнеров, каждый из которых является словарем или списком. В приведенном ниже тексте, наборы словарей и списков соответственно обозначены X _O и X _A . Это соответствует терминологии JSON, в которой два соответствующих типа контейнеров называются Object и Array. Дополнительный набор неконтейнерных узлов представляет «примитивные значения». Формализации, специфичные для JSON^{[27] [28]} обеспечивают дальнейшее уточнение в соответствии с поддерживаемыми типами данных .

Вложенные данные могут быть формализованы как структура ℳ = ( X , Σ , A , X _O , X _A , s , t , σ , ι ), где X - множество узлов , Σ - множество имен , A - множество из стрелок , Х _о и Х выделяются подмножества X , ы является частичной функцией от A до X( исходная карта), t - полная функция от A до X ( целевая карта), σ - частичная функция от A до Σ, присваивающая стрелке ее имя , а ι - частичная функция от A к множеству natural естественных числа, присваивающие стрелке ее родственный индекс .

Пусть ℳ называется вложенным деревом данных, если выполняются следующие условия:

1. Существует ровно одна «корневая» стрелка a _r , источник которой s ( a _r ) не определен.
2. К каждому узлу можно добраться по стрелке, начинающейся с корневой стрелки a _r .
3. Каждый узел из X _O  ∪  X _A является целью ровно одной стрелки.
4. Каждый узел , который является источником стрелки от X _O  ∪  X _A .
5. Множества X _O и X _A не пересекаются.
6. Функция обозначения стрелок σ удовлетворяет следующему для любых стрелок a , b .
   1. σ ( ) определяется тогда и только тогдакогда   s ( ) ∈  Х _О .
   2. Если σ ( a ) и σ ( b ) определены и равны, то либо a  =  b, либо s ( a ) ≠  s ( b ) .
7. Функция индексации стрелок ι удовлетворяет следующему для любых стрелок a , b .
   1. ι ( ) определяется тогда и только тогдакогда   s ( ) ∈ X .
   2. Если ι ( a ) и ι ( b ) определены и равны, то либо a  =  b, либо s ( a ) ≠  s ( b ) .
   3. Если ι ( a ) определено и не равно нулю, то ι ( a ) = ι ( a ′ ) + 1 для некоторой стрелки a ′ такой, что s ( a ) = s ( a ′ ) .

Обратите внимание, в частности, что (1) и (2) определяют доступные остроконечные колчаны ( X , A , s , t ) . Условия (1-4) обеспечивают аксиоматизацию стрелки деревьев с отличием контейнеров Х _О  ∪  Х . По (3) существуют уникальные ссылки на контейнеры, а по (4) неконтейнеры должны быть листовыми узлами (ср. Условия (b) и (a) для жестких ссылок в файловых системах). Важным следствием (1–4) является условие ацикличности :

1. Нет круговых траекторий последовательных стрелок.

Это условие является слабой альтернативой (3).

Общий заказ [ править ]

Хотя словари имеют семантику неупорядоченных коллекций, в средах программирования они часто оснащены внутренним упорядочением. Такой порядок поддерживается всеми Python, Ruby и JavaScript. ^[l]

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

Номенклатура [ править ]

Рассматривая только отдельные подмножества вышеуказанных условий и / или отдельные составляющие ℳ, мы получаем номенклатуру древовидных структур данных. Доступные заостренные колчаны ( X , A , s , t ) образуют «наименьший общий знаменатель» - всегда требуются условия (1) и (2). Условия (4–7) накладываются соответственно тому, определены ли X _O , X _A , σ или ι .

«Древовидная» атрибуция устанавливается условием (3).

		Требовать		Определять			Различать
		Уникальность (3)	Ацикличность (3 ')	Обозначение σ	Заказ ι		X O	Х А
					Семантический	Общее
Доступный остроконечный колчан
Неупорядоченное дерево
Заказанное дерево
Дерево стрелок с различием контейнеров							X O ∪ X A
Вложенный словарь Python: Словарь Рубин: хэш JavaScript: объект	Общий
	Ациклический
	Дерево
	Упорядоченный
Вложенный список Python: список Рубин, JavaScript: множество	Общий
	Ациклический
	Дерево
Вложенные данные	Общий
	Ациклический
	Дерево
	Упорядоченный

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

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

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

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

Заметки [ править ]

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

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

• Дональд Кнут . Искусство программирования : основные алгоритмы , третье издание. Аддисон-Уэсли, 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)
• Бинарные деревья Л. Эллисон