Розовое дерево

В вычислительной технике розовое дерево — это термин, обозначающий значение древовидной структуры данных с переменным и неограниченным количеством ветвей на узел. ^[1] Этот термин чаще всего используется в сообществе функционального программирования , например, в контексте формализма Бёрда-Меертенса . ^[2] Помимо свойства разветвленности, наиболее важной характеристикой розовых деревьев является совпадение сходства с идентичностью : два разных розовых дерева никогда не бывают двуподобными.

Мы

Название «розовое дерево» было придумано Ламбертом Мертенсом, с таким же названием и аналогичной структурой чтобы напомнить о рододендроне обыкновенном . ^[3]

Мы будем называть такие деревья розовыми деревьями , буквальным переводом рододендрона (греч. ῥόδον = роза, δένδρον = дерево), из-за сходства с габитусом этого кустарника, за исключением того, что последний в Северном полушарии не растет вверх тормашками.

Рекурсивное определение

Хорошо обоснованные деревья роз можно определить путем рекурсивного построения сущностей следующих типов:

Базовый объект — это элемент заранее определенного основного набора $значений V$ («верхние» значения). ^[3]).
( Разветвляющийся объект альтернативно разветвляющийся объект или объект леса ) относится к одному из следующих подтипов:
1. Набор сущностей .
2. Последовательность . сущностей
3. Частичное отображение заранее определенного $набора$ имен сущностей .
Любой из (a)(b)(c) может быть пустым. Обратите внимание, что (б) можно рассматривать как частный случай (в) — последовательность — это просто отображение начального сегмента множества. $\mathbb {N}$ натуральных чисел.
Сопряженный объект — это упорядоченная пара $(F, x),$ такая что $F$ является ветвящимся объектом, а $x$ является элементом предопределенного набора $L$ значений «метки». Поскольку спаривающийся объект может содержать в качестве компонента только ветвящийся объект, происходит индуцированное разделение на подтипы (3a), (3b) или (3c), соответствующие подтипам ветвящихся объектов.

Обычно для построения используются лишь некоторые комбинации типов сущностей. Оригинальная бумага ^[3] учитываются только 1+2b («разветвляющиеся последовательности» розовые деревья) и 1+2a («разветвляющиеся множества» розовые деревья).В более поздней литературе вариант 1+2b обычно представлен следующим определением:

data Tree a = Leaf a | Node [Tree a]

Розовое дерево [...] — это либолист, содержащий значение, или узел, который может иметь произвольный список поддеревьев . ^[4]

Наиболее распространенное определение, используемое в функциональном программировании (особенно в Haskell ), объединяет 3+2b:

data Rose α = Node α [Rose α]

Элемент Rose α состоит из помеченного узла вместе со списком поддеревьев . ^[1]То есть розовое дерево представляет собой парный объект (тип 3), чей ветвящийся объект представляет собой последовательность (таким образом, типа 2b) розовых деревьев.

Иногда рассматривается даже комбинация 1+3b. ^[5]^[6]В следующей таблице представлена сводка наиболее распространенных комбинаций объектов.

Терминология	Используемые сущности
Хорошо обоснованный набор	(2а)
Обоснованное вложенного списка значение	(2б)(1)
Хорошо обоснованное вложенного словаря значение	(2в)(1)
Обоснованное вложенных данных значение	(2б)(2в)(1)
L $,$ - имя известное по принуждению	(2а)(3) ^{[в 1]}
Хорошо обоснованное розовое дерево в самом здравом смысле.	(3)(2б) ^{[в 1]}

Примечания:

^ Перейти обратно: ^а ^б Для комбинаций (2a)(3) и (3)(2b) второй заявленный тип объекта является только промежуточным - он просто используется для определения «конечного» объекта, который относится к первому указанному типу. При этом типы строго чередуются, т.е. ветвящаяся сущность может содержать в качестве своего члена только парную сущность.

Общее определение

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

В соответствии с типами объектов, используемых в рекурсивном определении, каждому узлу apq присваивается тип (1), (2a), (2b), (2c) или (3).На apqs распространяются условия, имитирующие свойства рекурсивно созданных сущностей.

1. Узел типа (1) является элементом заданного множества $V$ основных значений.
2. Узел типа (1) не отображается как источник стрелки.
1. Узел типа (3) выступает источником ровно одной стрелки.
2. Целью стрелки, упомянутой в (а), является узел типа (2).
Две разные стрелки с одним и тем же исходным узлом типа (2a) имеют разные цели.
Узел помечен тогда и только тогда, когда он имеет тип (3). Метка принадлежит предопределённому $L.$ множеству
1. Стрелка помечена индексом от $\mathbb {N}$ если его исходный узел имеет тип (2b).
2. Стрелка помечается именем из предопределенного множества $Σ$ , если ее исходный узел имеет тип (2c).
3. В противном случае стрелка не имеет метки.
Метки стрелок с одним и тем же исходным узлом различны.
Метки стрелок с одинаковым исходным узлом типа (2б) образуют начальный сегмент $\mathbb {N}$ .

Бисходство между apqs $𝒳 = (X, ...)$ и $𝒴 = (Y, ...)$ — это отношение $R \subseteq X \times Y$ между узлами такое, чтокорни $𝒳$ и $𝒴$ -родственны $R$ идля каждой пары $(x, y)$ узлов $, связанных с R$ , выполняются следующие условия:

Узлы $x$ и $y$ имеют один и тот же тип.
Если $x$ и $y$ имеют тип (1), то они идентичны.
Если $x$ и $y$ имеют тип (3), то они имеют одинаковую метку.
Для каждой стрелки a из 𝒳 , исходным узлом которой является x, существует стрелка b из 𝒴 , источником которой является y и
1. целевые узлы $a$ и b связаны $с R$ ,
2. метки $a$ и b , если они определены, идентичны.
Условие симметрии выполняется при $перестановке 𝒳$ и $𝒴$ .

Два apq $𝒳$ и $𝒴$ называются биподобными существует отношение биподобия $R.$ , если для них Это устанавливает отношение эквивалентности на классе всех apq.

Тогда розовое дерево — это некоторое фиксированное представление класса $𝒞$ apq, которое биподобно некоторому заданному apq $𝒳$ .Если корневой узел $𝒳$ имеет тип (1), то $𝒞 = {𝒳$ }, таким образом, $𝒞$ может быть представлен этим корневым узлом. В противном случае $𝒞$ является правильным классом представление может - в этом случае с помощью трюка Скотта быть множеством тех элементов $𝒞$ , которые имеют наименьший ранг.

В результате приведенной выше теоретико-множественной конструкции класс $ℛ$ всех розовых деревьев определяется в зависимости от множеств $V$ (основные значения), $Σ$ (имена стрелок) и $L$ (метки узлов) в качестве определяющих составляющих.Впоследствии структура apqs может быть перенесена в структуру помеченного мультиорграфа над $ℛ$ . То есть элементы $ℛ$ сами по себе могут рассматриваться как «узлы» с индуцированным присвоением типа, маркировкой узлов и стрелками. Класс $𝒜$ стрелки являются подклассом $\mathbb {N}$ , то есть стрелки представляют собой либо пары источник-цель, либо тройки источник-метка-цель в зависимости от типа источника.

Для каждого элемента $r$ из $ℛ$ существует индуцированный apq $𝒳 = (X, A, r, ...)$ такой, что $r$ является корневым узлом $𝒳$ , а соответствующие множества $X$ и $A$ узлов и стрелок $𝒳$ образованы теми элементы $ℛ$ и $𝒜$ , доступные по пути стрелок, начинающемуся с $r$ . Индуцированный apq $𝒳$ биподобен apqs, используемому для построения $r$ .

Карты имен путей

Розовые деревья, которые не содержат узлов ветвления множества (тип 2а), могут быть представлены картами имен путей.Путь — это просто конечная последовательность меток стрелок. Для пути стрелки $a \to = [a 1, ..., an n]$ (конечная последовательность последовательных стрелок) имя пути $p$ — это соответствующая последовательность $σ (а \to) знак равно [σ (а 1), ..., σ (а п)]$ меток со стрелками.Здесь предполагается, что каждая стрелка помечена ( $σ$ обозначает функцию маркировки). В общем, каждый путь стрелки необходимо сначала уменьшить, удалив все его стрелки, исходящие из узлов спаривания (тип 3).

Имя пути $p$ разрешимо тогда и только тогда, когда существует корневой путь стрелки $a \to,$ имя пути которого равно $p$ . Такой $\to .$ однозначно присваивается возможной немаркированной последней стрелке (полученной из узла спаривания) Целевым узлом непустого разрешимого пути является целевой узел последней стрелки соответствующего пути стрелки, исходящего из корня, который не заканчивается немаркированной стрелкой.Целью пустого пути является корневой узел.

Учитывая розовое дерево $r$ , которое не содержит узлов ветвления множества, пути карта $r$ представляет собой карту $t$ , которая присваивает каждому разрешимому имени пути $p$ его значение $t (p)$ в соответствии со следующей общей схемой:

$\mathbb {N}$ т ——— → $(V \cup {⊥} \cup L) \times Т$

Напомним, что $\mathbb {N}$ — множество стрелочных меток ( $\mathbb {N}$ — набор натуральных чисел, а $Σ$ — набор названий стрелок) $L$ — набор меток узлов,и $V$ — набор основных значений.Дополнительные символы $⊥$ и $T$ соответственно означают индикатор разрешимого имени пути и набора тегов типа $T = {'1', '2b', '2c', '3b', '3c'$ }.Карта $t$ определяется следующим предписанием ( $x$ обозначает цель $p$ ):

$т (п) знак равно$	$(х, '1')$	если $x$ имеет тип (1),
	$(⊥, '2b')$ или $(⊥, '2c')$	если $x$ имеет соответствующий тип (2b) или (2c),
	$(ℓ, '3b')$ или $(ℓ, '3c')$	если $x$ имеет соответствующий тип (3b) или (3c) и $ℓ \in L$ — метка $x$ .

Можно показать, что разные деревья роз имеют разные карты путей. Для «однородных» розовых деревьев нет необходимости в маркировке типов, и их карту пути $t$ можно определить, как показано ниже:

Терминология	Схема
Значение вложенного списка	$\mathbb {N}$ т ——— → $V \cup {⊥$ }
Вложенное значение словаря	$С ⁎ \supseteq dom(т)$ т ——— → $V \cup {⊥$ }
Розовое дерево от Haskell, дерево над буквой $L.$ ^[7]^[8]	$\mathbb {N}$ т ——— → $L$ ^{[стр 1]}
$L$ -значное дерево, ^[9] дерево с надписью $L$ ^[10]	$С ⁎ \supseteq dom(т)$ т ——— → $L$ ^{[стр 1]}

В каждом случае существует простая аксиоматизация имен путей:

$dom(t)$ — непустое закрытое префиксом подмножество $\mathbb {N}$ или $Σ ⁎$ . В случае $\mathbb {N}$ , $dom(t)$ также должен быть «закрытым по левому брату», чтобы сформировать древовидный домен , см. Кодирование последовательностями .
В случае вложенного списка или значения вложенного словаря, если $p$ — это путь, который не является максимальным в $dom(t)$ , то $t (p) = ⊥$ . ^{[стр. 2]}

В частности, розовое дерево в наиболее распространенном смысле «Haskell» — это просто отображение непустого, замкнутого по префиксу и замкнутого по левому брату множества конечных последовательностей натуральных чисел в множество $L$ .Такое определение чаще всего используется за пределами раздела функционального программирования, см. Дерево (теория автоматов) .Обычно в документах, в которых используется это определение, термин «розовое дерево» вообще не упоминается.

Примечания:

^ Перейти обратно: ^а ^б Если $dom(t) = M ⁎$ для подмножества $\mathbb {N}$ или $Σ$ , то карта пути $t$ представляет собой отображение последовательностей входных символов в выходные символы машины Мура . В частности, каждая машина Мура, у которой множество $M$ входных символов является начальным сегментом $\mathbb {N}$ и со всеми достижимыми состояниями он похож на розовое дерево в смысле Haskell, см. пример необоснованного розового дерева.Аналогичные отношения можно наблюдать между вложенными словарями (или списками) и машинами Мили , см. Вложенный словарь .
^ Чтобы гарантировать, что вложенный список или вложенный словарь в первую очередь являются списком или словарем соответственно, $условия t (p) = ⊥$ необходимо явно потребовать выполнения $для пустого пути p$ . Это утверждает, что такие случаи, как x = 5 не считаются «деревовидными значениями».

Примеры

На диаграммах ниже показаны два примера розовых деревьев вместе с соответствующим кодом Haskell. В обоих случаях модуль Data.Tree ^[11] используется в том виде, в котором он предоставляется пакетом контейнеров Haskell. ^[12]Модуль представляет розовые деревья как парные объекты по следующему определению:

data Tree a = Node {        rootLabel :: a,         -- ^ label value        subForest :: [Tree a]   -- ^ zero or more child trees    }

Оба примера придуманы, чтобы продемонстрировать концепцию «совместного использования подструктур». ^[13] что является отличительной чертой розовых деревьев.В обоих случаях функция разметки инъективна. (чтобы метки 'a', 'b', 'c' или 'd' однозначно идентифицировать поддерево/узел), что в целом не обязательно должно выполняться.Натуральные числа (0,1,2 или 3) вдоль стрелок обозначают позицию с отсчетом от нуля, в которой дерево появляется в subForest последовательность определенного «супердерева».В результате возможных повторений в subForest, между узлами может быть несколько стрелок.В каждом из примеров рассматриваемое розовое дерево помечено 'a' и равен значению a переменная в коде. На обеих диаграммах дерево указано стрелкой без источника.

Хорошо построенное розовое дерево

import Data.Treemain :: IO ()main = dolet d = Node { rootLabel = 'd', subForest = [] }let c = Node { rootLabel = 'c', subForest = [d] }let b = Node { rootLabel = 'b', subForest = [d,c] }let a = Node { rootLabel = 'a', subForest = [b,c,c,c] }print a

Неосновательное розовое дерево

import Data.Treemain :: IO ()main = dolet root x = case x of     'a' -> (x,[x,'b'])     'b' -> (x,[x,'c'])     'c' -> (x,[x,'a'])let a = unfoldTree root 'a'putStrLn (take 900 (show a)  ++ " ... (and so on)")

В первом примере представлено хорошо обоснованное розовое дерево. a получено путем поэтапного построения. Первый d построено, то c затем b и наконец a. Розовое дерево можно представить с помощью карты имен путей, показанной слева.

Во втором примере представлено некрепкое розовое дерево. a построенный конструктором в ширину unfoldTree. Розовое дерево — это машина Мура, см. примечания выше. Его карта пути $т : {0,1} ⁎ \to {'a','b','c'$ }определяется как $t (p)$ и соответственно равно $'a'$ , $'b'$ или $'c'$ в соответствии с $n mod 3,$ где $n$ - количество вхождений $1$ в $p$ .

Связь с древовидными структурами данных

Общее определение обеспечивает связь с древовидными структурами данных:

Розы представляют собой древовидные структуры по модулю биподобия.

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

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

На диаграмме справа показан пример такого сопоставления структуры со значением. В верхней части диаграммы упорядоченное дерево $T$ отображается с обозначением узлов, содержащее 23 узла. В нижней части показано розовое дерево $R$ которое соответствует значению $T.$ , (И в $T$ , и $в R$ родственные стрелки неявно упорядочены слева направо.)Существует индуцированное сопоставление поддерева с подзначениями, которое частично показано синими стрелками.

Обратите внимание, что отображение осуществляется по принципу «многие к одному»: разные древовидные структуры данных могут иметь одно и то же значение. Как конкретное следствие, розовое дерево в целом не является деревом с точки зрения «подценностных» отношений между его подзначениями, см. #Terminological_controversy .

Тип данных дерева

Описанное выше сопоставление значений можно использовать для пояснения разницы между терминами «деревовидная структура данных» и «деревовидный тип данных»:

Тип данных дерева — это набор значений древовидных структур данных . ^{[дт 1]}

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

Например, для набора $L = {'a','b','c','d'$ } меток набор розовых деревьев в смысле Haskell (3b) с метками, взятыми из $L,$ представляет собой данные одного дерева. тип. Все приведенные выше примеры розовых деревьев относятся к этому типу данных.

Примечания:

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

Терминологические разногласия

Как видно из приведенного выше текста и диаграмм, термин «розовое дерево» является спорным.Есть две взаимосвязанные проблемы:

Неясное значение слова «узел».
Несоответствие между «деревом» и «совместным использованием подструктур».

Интересно, что термин «узел» не встречается в оригинальной статье. ^[3] за исключением одного появления «узлов» в неофициальном абзаце на странице 20.В более поздней литературе это слово широко используется.Это можно наблюдать уже в цитируемых комментариях к определениям:

Розовое дерево [...] — это либо лист [...], либо узел [...] . ^[4]
Элемент Rose α состоит из помеченного узла [...] . ^[1]

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

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

Различные виды структур данных, называемые в информатике деревьями, имеют в основе графы, которые в теории графов являются деревьями [...]

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

Байесовское розовое дерево

Существует по крайней мере один вариант использования термина «розовое дерево» в информатике, при котором «совместное использование подструктур» исключено. Концепция байесовского розового дерева основана на следующем определении розового дерева:

$T$ является розовым деревом, если либо $T = {x$ } для некоторой точки данных $x,$ либо $T = {T 1, ... , T n T$ }, где $T i$ - розовые деревья над непересекающимися наборами точек данных. ^[14]

Ссылки

^ Перейти обратно: ^а ^б ^с Берд, Ричард (1998). Введение в функциональное программирование с использованием Haskell . Хемел Хемпстед, Хартфордшир, Великобритания: Prentice Hall Europe. п. 195. ИСБН 0-13-484346-0 .
^ Малькольм, Грант (1990). «Структуры данных и трансформация программ» . Наука компьютерного программирования . 14 (2): 255–279. дои : 10.1016/0167-6423(90)90023-7 .
^ Перейти обратно: ^а ^б ^с ^д Меертенс, Ламберт (январь 1988 г.). «Первые шаги к теории розовых деревьев» (PDF) . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Перейти обратно: ^а ^б Берд, Ричард; Гиббонс, Джереми (2020). Проектирование алгоритмов на Haskell . Издательство Кембриджского университета. ISBN 9781108491617 .
^ Скиликорн, Дэвид Б. (1996). «Параллельная реализация скелетов деревьев» (PDF) . Журнал параллельных и распределенных вычислений . 39 (2): 115–125. дои : 10.1006/jpdc.1996.0160 .
^ Зееманн, Марк. «Церковное розовое дерево» .
^ Моравец, Франк (2008). Двухэтапные подходы к формализму естественного языка . Вальтер де Грюйтер. ISBN 9783110197259 .
^ Коски, Энтони (1995). Преобразование баз данных с помощью рекурсивных структур данных (Диссертация).
^ Нивинский, Дамиан (1997). «Характеристика фиксированной точки бесконечного поведения систем с конечным состоянием» (PDF) . Теоретическая информатика . 189 (1–2): 1–69. дои : 10.1016/S0304-3975(97)00039-X .
^ Дагнино, Франческо (2020). «Коаксиомы: гибкие коиндуктивные определения с помощью систем вывода» . Логические методы в информатике . 15 . arXiv : 1808.02943 . дои : 10.23638/LMCS-15(1:26)2019 . S2CID 51955443 .
^ «Данные.Дерево» .
^ «контейнеры: различные типы бетонных контейнеров» .
^ Гиббонс, Джереми (1991). Алгебры для древовидных алгоритмов (PDF) (доктор философии). Оксфордский университет.
^ Бланделл, Чарльз; Почему, да; Хеллер, Кэтрин А. (2010). Байесовские розы (PDF) . 26-я конференция по неопределенности в искусственном интеллекте.

[PairingCombined-7] Перейти обратно: ^а ^б Для комбинаций (2a)(3) и (3)(2b) второй заявленный тип объекта является только промежуточным - он просто используется для определения «конечного» объекта, который относится к первому указанному типу. При этом типы строго чередуются, т.е. ветвящаяся сущность может содержать в качестве своего члена только парную сущность.

[Moore-11] Перейти обратно: ^а ^б Если $dom(t) = M ⁎$ для подмножества $\mathbb {N}$ или $Σ$ , то карта пути $t$ представляет собой отображение последовательностей входных символов в выходные символы машины Мура . В частности, каждая машина Мура, у которой множество $M$ входных символов является начальным сегментом $\mathbb {N}$ и со всеми достижимыми состояниями он похож на розовое дерево в смысле Haskell, см. пример необоснованного розового дерева.Аналогичные отношения можно наблюдать между вложенными словарями (или списками) и машинами Мили , см. Вложенный словарь .

[NonContainerRoot-14] Чтобы гарантировать, что вложенный список или вложенный словарь в первую очередь являются списком или словарем соответственно, $условия t (p) = ⊥$ необходимо явно потребовать выполнения $для пустого пути p$ . Это утверждает, что такие случаи, как x = 5 не считаются «деревовидными значениями».

[RawDelimitation-20] Однако не каждый набор значений древовидных структур данных является древовидным типом данных.

[Bird1988-1] Перейти обратно: ^а ^б ^с Берд, Ричард (1998). Введение в функциональное программирование с использованием Haskell . Хемел Хемпстед, Хартфордшир, Великобритания: Prentice Hall Europe. п. 195. ИСБН 0-13-484346-0 .

[2] Малькольм, Грант (1990). «Структуры данных и трансформация программ» . Наука компьютерного программирования . 14 (2): 255–279. дои : 10.1016/0167-6423(90)90023-7 .

[Meertens1988-3] Перейти обратно: ^а ^б ^с ^д Меертенс, Ламберт (январь 1988 г.). «Первые шаги к теории розовых деревьев» (PDF) . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[Bird2020-4] Перейти обратно: ^а ^б Берд, Ричард; Гиббонс, Джереми (2020). Проектирование алгоритмов на Haskell . Издательство Кембриджского университета. ISBN 9781108491617 .

[Skillicorn1996-5] Скиликорн, Дэвид Б. (1996). «Параллельная реализация скелетов деревьев» (PDF) . Журнал параллельных и распределенных вычислений . 39 (2): 115–125. дои : 10.1006/jpdc.1996.0160 .

[Seemann2020-6] Зееманн, Марк. «Церковное розовое дерево» .

[Morawietz2008-9] Моравец, Франк (2008). Двухэтапные подходы к формализму естественного языка . Вальтер де Грюйтер. ISBN 9783110197259 .

[Kosky1995-10] Коски, Энтони (1995). Преобразование баз данных с помощью рекурсивных структур данных (Диссертация).

[Niwinski1997-12] Нивинский, Дамиан (1997). «Характеристика фиксированной точки бесконечного поведения систем с конечным состоянием» (PDF) . Теоретическая информатика . 189 (1–2): 1–69. дои : 10.1016/S0304-3975(97)00039-X .

[Dagnino2020-13] Дагнино, Франческо (2020). «Коаксиомы: гибкие коиндуктивные определения с помощью систем вывода» . Логические методы в информатике . 15 . arXiv : 1808.02943 . дои : 10.23638/LMCS-15(1:26)2019 . S2CID 51955443 .

[HaskellDataTree-17] «Данные.Дерево» .

[HaskellContainers-18] «контейнеры: различные типы бетонных контейнеров» .

[Gibbons1991-19] Гиббонс, Джереми (1991). Алгебры для древовидных алгоритмов (PDF) (доктор философии). Оксфордский университет.

[Blundell2010-22] Бланделл, Чарльз; Почему, да; Хеллер, Кэтрин А. (2010). Байесовские розы (PDF) . 26-я конференция по неопределенности в искусственном интеллекте.

[1]

[2]

[3]

[4]

[5]

[6]

[в 1]

[7]

[8]

[стр 1]

[9]

[10]

[стр. 2]

[11]

[12]

[13]

[дт 1]

[14]

v т и Древовидные структуры данных
Поиск деревьев ( динамические наборы / ассоциативные массивы )	2–3 2–3–4 АА (а, б) АВЛ Б B+ Б* Б ^х ( Оптимально ) Бинарный поиск Танцы HTree Интервал Статистика заказов Палиндром ( Наклон влево ) Красно-черный козел отпущения Распространение Т Треп УБ Сбалансированный по весу
Кучи	Двоичный Биномиальный Мостовая долина д -и Фибоначчи Левый Сопряжение Наклонный бином Перекос от Эмде Боас Слабый
Пытается	Деревня C-trie (сжатый ADT) Хэш Радикс Суффикс Троичный поиск X-быстрый Y-быстро
пространственных данных Деревья разделения	Мяч БК БСП декартовский Гильберт Р. k -d ( неявный k -d ) М Метрика MVP Октри PH Приоритет Р Четырехместный Р Р+ Р* Сегмент вице-президент Х
Другие деревья	Крышка Экспоненциальный Фенвик Палец Индекс фрактального дерева Слияние хеш-календарь iDistance К-и Левый ребенок, правый брат Связать/вырезать Лог-структурированное слияние Меркле ПК Диапазон SPQR Вершина