Декартово дерево

Последовательность чисел и полученное из них декартово дерево.

Для метафоры дерева познания Декарта см. Дерево познания (философия) .

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

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

Определение

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

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

1. Декартово дерево последовательности — это двоичное дерево с одним узлом для каждого числа в последовательности.
2. Симметричный (по порядку) обход дерева приводит к исходной последовательности. Аналогично, для каждого узла числа в его левом поддереве находятся раньше его в последовательности, а числа в правом поддереве — позже.
3. Дерево имеет свойство min-heap : родительский элемент любого некорневого узла имеет меньшее значение, чем сам узел.

Эти два определения эквивалентны: дерево, определенное рекурсивно, как описано выше, является уникальным деревом, имеющим перечисленные выше свойства. Если последовательность чисел содержит повторения, для нее можно определить декартово дерево, следуя последовательному правилу разрешения конфликтов перед применением приведенной выше конструкции. Например, первый из двух равных элементов можно рассматривать как меньший из двух.

История

Декартовы деревья были введены и названы Вюлеменом (1980) , который использовал их как пример взаимодействия геометрической комбинаторики с проектированием и анализом структур данных . В частности, Вийемен использовал эти структуры для анализа средней сложности операций конкатенации и разделения на деревьях двоичного поиска . Название происходит от декартовой системы координат плоскости: в одной версии этой структуры, как в приложении для поиска двумерного диапазона, обсуждаемом ниже, декартово дерево для набора точек имеет отсортированный порядок точек по их расположению. $x$-координаты как его симметричный порядок обхода, и он обладает свойством кучи в соответствии с $y$-координаты точек. Вийемен описал как эту геометрическую версию структуры, так и приведенное здесь определение, в котором декартово дерево определяется из последовательности. Использование последовательностей вместо координат точек обеспечивает более общие настройки, которые позволяют применять декартово дерево и к негеометрическим задачам.

Эффективное строительство

Декартово дерево может быть построено за линейное время на основе входной последовательности.Один из методов заключается в обработке значений последовательности в порядке слева направо, сохраняя декартово дерево узлов, обработанных на данный момент, в структуре, позволяющей обход дерева как вверх, так и вниз. Для обработки каждого нового значения $a$, начните с узла, представляющего значение до $a$ в последовательности и следуйте по пути от этого узла к корню дерева, пока не найдете значение $b$ меньше, чем $a$. Узел $a$ становится правильным ребенком $b$, и предыдущий правый дочерний элемент $b$ становится новым левым ребенком $a$. Общее время этой процедуры линейно, поскольку время, потраченное на поиск родительского элемента $b$ каждого нового узла $a$ может взиматься за количество узлов, удаленных из крайнего правого пути в дереве.

Альтернативный алгоритм построения за линейное время основан на задаче всех ближайших меньших значений . Во входной последовательности определите левого соседа значения $a$ быть значением, которое возникает до $a$, меньше, чем $a$, и находится ближе по положению к $a$ чем любое другое меньшее значение. Правый сосед определяется симметрично. Последовательность левых соседей можно найти с помощью алгоритма, который поддерживает стек, содержащий подпоследовательность входных данных. Для каждого нового значения последовательности $a$, стек извлекается до тех пор, пока он не станет пустым или его верхний элемент не станет меньше, чем $a$, а потом $a$ помещается в стек. Левый сосед г. $a$ это верхний элемент в данный момент $a$ толкается. Правильных соседей можно найти, применив тот же алгоритм стека к обратной последовательности. Родитель $a$ в декартовом дереве является либо левым соседом $a$ или правый сосед $a$, в зависимости от того, что существует и имеет большее значение. Левый и правый соседи также могут быть эффективно построены с помощью параллельных алгоритмов , что делает эту формулировку полезной в эффективных параллельных алгоритмах построения декартовых деревьев.

Другой алгоритм построения декартова дерева с линейным временем основан на принципе « разделяй и властвуй» . Алгоритм рекурсивно строит дерево на каждой половине входных данных, а затем объединяет два дерева. В процессе слияния участвуют только узлы на левом и правом позвоночнике этих деревьев: левый позвоночник — это путь, полученный путем следования по левым дочерним ребрам от корня до достижения узла без левого дочернего узла, а правый позвоночник определяется симметрично. Как и в случае с любым путем в мини-куче, оба позвоночника имеют свои значения в отсортированном порядке: от наименьшего значения в корне до наибольшего значения в конце пути. Чтобы объединить два дерева, примените алгоритм слияния к правому позвоночнику левого дерева и левому позвоночнику правого дерева, заменив эти два пути в двух деревьях одним путем, содержащим одни и те же узлы. В объединенном пути преемник в отсортированном порядке каждого узла левого дерева помещается в его правый дочерний элемент, а преемник каждого узла из правого дерева помещается в его левый дочерний элемент, та же позиция, которая ранее использовалась для его преемник в позвоночнике. Левые дочерние элементы узлов левого дерева и правые дочерние элементы узлов правого дерева остаются неизменными. Алгоритм является распараллеливаемым, поскольку на каждом уровне рекурсии каждая из двух подзадач может вычисляться параллельно, а операция слияния может быть эффективно распараллеливается . также

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

Приложения

Поиск диапазона и самые

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

Декартовы деревья являются частью эффективной структуры данных для запросов минимального диапазона . Входные данные для этого типа запроса указывают непрерывную подпоследовательность исходной последовательности; выходные данные запроса должны быть минимальным значением в этой подпоследовательности. В декартовом дереве это минимальное значение можно найти у наименьшего общего предка самых левых и самых правых значений в подпоследовательности. Например, в подпоследовательности (12,10,20,15,18) примерной последовательности минимальное значение подпоследовательности (10) образует наименьшего общего предка самых левых и самых правых значений (12 и 18). Поскольку наименьшие общие предки могут быть найдены за постоянное время для каждого запроса, используя структуру данных, которая занимает линейное пространство для хранения и может быть построена за линейное время, те же границы справедливы и для задачи минимизации диапазона.

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

Той же задаче минимизации диапазона можно дать альтернативную интерпретацию с точки зрения двумерного поиска диапазона. Совокупность конечного числа точек на декартовой плоскости можно использовать для формирования декартова дерева путем сортировки точек по их значению. $x$-координаты и с помощью $y$-координаты в таком порядке, как последовательность значений, из которых формируется это дерево. Если $S$ - это подмножество входных точек внутри некоторой вертикальной плиты, определяемой неравенствами $L\leq x\leq R$, $p$ это самая левая точка в $S$ (тот, у которого минимум $x$-координата) и $q$ это самая правая точка в $S$ (тот, у которого максимум $x$-координата), то низший общий предок $p$ и $q$ в декартовом дереве — это самая нижняя точка плиты. Трехсторонний запрос диапазона, в котором задача состоит в том, чтобы перечислить все точки в области, ограниченной тремя неравенствами. $L\leq x\leq R$ и $y\leq T$, можно ответить, найдя эту самую нижнюю точку $b$, сравнивая его $y$-координировать $T$, и (если точка лежит внутри трехсторонней области) продолжая рекурсивно в двух плитах, ограниченных между $p$ и $b$ и между $b$ и $q$. Таким образом, после того, как крайняя левая и самая правая точки плиты определены, все точки в трехсторонней области могут быть перечислены в постоянном времени для каждой точки.

Та же самая конструкция наименьших общих предков в декартовом дереве позволяет построить структуру данных с линейным пространством, которая позволяет расстояния между парами точек в любом ультраметрическом пространстве запрашивать за постоянное время для каждого запроса. Расстояние внутри ультраметрики такое же, как минимаксный вес пути в минимальном остовном дереве метрики. Из минимального остовного дерева можно построить декартово дерево, корневой узел которого представляет собой самое тяжелое ребро минимального остовного дерева. Удаление этого ребра разделяет минимальное остовное дерево на два поддерева, и декартовы деревья, рекурсивно построенные для этих двух поддеревьев, образуют дочерние элементы корневого узла декартова дерева. Листья декартова дерева представляют собой точки метрического пространства, а самый низкий общий предок двух листьев в декартовом дереве - это самое тяжелое ребро между этими двумя точками в минимальном остовном дереве, вес которого равен расстоянию между двумя точками. . После того как минимальное остовное дерево найдено и веса его ребер отсортированы, декартово дерево можно построить за линейное время.

В виде двоичного дерева поиска

Основная статья: Треп

Декартово дерево отсортированной последовательности — это просто граф путей , корни которого лежат в самой левой конечной точке. Бинарный поиск в этом дереве перерождается в последовательный поиск по пути. Однако другая конструкция использует декартовы деревья для создания двоичных деревьев поиска логарифмической глубины из отсортированных последовательностей значений. Это можно сделать, генерируя номера приоритетов для каждого значения и используя последовательность приоритетов для создания декартова дерева. Эту конструкцию можно эквивалентным образом рассматривать в геометрической схеме, описанной выше, в которой $x$-координаты набора точек — это значения в отсортированной последовательности и $y$-координаты - их приоритеты.

Эту идею применили Зайдель и Арагон (1996) , которые предложили использовать случайные числа в качестве приоритетов. Самобалансирующееся двоичное дерево поиска, возникающее в результате этого случайного выбора, называется treap из-за комбинации функций двоичного дерева поиска и минимальной кучи. Вставку в треп можно выполнить, вставив новый ключ как лист существующего дерева, выбрав для него приоритет, а затем выполнив операции поворота дерева по пути от узла к корню дерева для устранения любых нарушений свойство кучи, вызванное этой вставкой; удаление аналогичным образом может быть выполнено путем внесения постоянного количества изменений в дерево с последующей последовательностью поворотов по одному пути в дереве. Вариант этой структуры данных, называемый zip-деревом, использует ту же идею случайных приоритетов, но упрощает случайное создание приоритетов и выполняет вставку и удаление другим способом, разделяя последовательность и связанное с ней декартово дерево на две подпоследовательности и два дерева, а затем их повторное объединение.

Если приоритеты каждого ключа выбираются случайным образом и независимо каждый раз, когда ключ вставляется в дерево, полученное декартово дерево будет иметь те же свойства, что и случайное дерево двоичного поиска , дерево, вычисляемое путем вставки ключей в случайно выбранную перестановку , начиная с из пустого дерева, при этом каждая вставка оставляет предыдущую древовидную структуру неизменной и вставляет новый узел в качестве листа дерева. Случайные двоичные деревья поиска изучаются гораздо дольше, чем поисковые алгоритмы, и известно, что они хорошо себя ведут как деревья поиска. Ожидаемая длина пути поиска к любому заданному значению не превышает $2\ln n$, и все дерево имеет логарифмическую глубину (максимальное расстояние от корня до листа) с высокой вероятностью . Более формально существует константа $C$ такая, что глубина $\leq C\ln n$ с вероятностью, стремящейся к единице, поскольку количество узлов стремится к бесконечности. Такое же хорошее поведение распространяется и на трепы. Также возможно, как предложили Арагон и Зайдель, изменить приоритеты часто используемых узлов, заставляя их перемещаться к корню ловушки и ускоряя будущие доступы для тех же ключей.

В сортировке

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

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

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

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

Как показывают Левкопулос и Петерссон, для входных последовательностей, которые уже почти отсортированы, размер приоритетной очереди останется небольшим, что позволяет этому методу использовать преимущества почти отсортированных входных данных и работать быстрее. В частности, наихудшее время работы этого алгоритма равно $O(n\log k)$, где $n$ длина последовательности и $k$ — это среднее по всем значениям в последовательности количества последовательных пар значений последовательности, заключающих в скобки данное значение (это означает, что данное значение находится между двумя значениями последовательности). Они также доказывают нижнюю оценку, утверждающую, что для любого $n$ и (непостоянный) $k$, любой алгоритм сортировки на основе сравнения должен использовать $\Omega (n\log k)$ сравнения для некоторых входных данных.

В сопоставлении с образцом

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

Ссылки

• Бендер, Майкл А.; Фарах-Колтон, Мартин (2000), «Возвращение к проблеме LCA», Труды 4-го Латиноамериканского симпозиума по теоретической информатике , Springer-Verlag, Конспекты лекций по информатике , 1776 г., стр. 88–94.
• Беркман, Омер; Шибер, Барух ; Вишкин, Узи (1993), «Оптимальные дважды логарифмические параллельные алгоритмы, основанные на поиске всех ближайших меньших значений», Journal of Algorithms , 14 (3): 344–370, doi : 10.1006/jagm.1993.1018
• Бялыницка-Бирула, Ивона; Гросси, Роберто (2006), «Амортизированная жесткость в динамических декартовых деревьях», Дюран, Бруно; Томас, Вольфганг (ред.), STACS 2006, 23-й ежегодный симпозиум по теоретическим аспектам информатики, Марсель, Франция, 23-25 ​​февраля 2006 г., Труды , конспекты лекций по информатике, том. 3884, Springer, стр. 80–91, номер документа : 10.1007/11672142_5 , ISBN.  978-3-540-32301-3
• Демейн, Эрик Д .; Ландау, Гад М.; Вейманн, Орен (2009), «О декартовых деревьях и запросах минимума диапазона», Автоматы, языки и программирование, 36-й международный коллоквиум, ICALP 2009, Родос, Греция, 5–12 июля 2009 г. , Конспекты лекций по информатике, том. 5555, стр. 341–353, doi : 10.1007/978-3-642-02927-1_29 , hdl : 1721.1/61963 , ISBN  978-3-642-02926-4
• Фишер, Йоханнес; Хойн, Волкер (2006), «Теоретические и практические улучшения проблемы RMQ с применением к LCA и LCE», Труды 17-го ежегодного симпозиума по комбинаторному сопоставлению с образцом , Конспекты лекций по информатике, том. 4009, Springer-Verlag, стр. 36–48, номер документа : 10.1007/11780441_5 , ISBN.  978-3-540-35455-0
• Фишер, Йоханнес; Хойн, Волкер (2007), «Новое краткое представление RMQ-информации и улучшения расширенного суффиксного массива», Труды Международного симпозиума по комбинаторике, алгоритмам, вероятностным и экспериментальным методологиям , Конспекты лекций по информатике, том. 4614, Springer-Verlag, стр. 459–470, номер doi : 10.1007/978-3-540-74450-4_41 , ISBN.  978-3-540-74449-8
• Габоу, Гарольд Н .; Бентли, Джон Луис ; Тарьян, Роберт Э. (1984), «Масштабирование и связанные с ним методы решения задач геометрии», STOC '84: Proc. 16-й симпозиум ACM. Теория вычислений , Нью-Йорк, Нью-Йорк, США: ACM, стр. 135–143, doi : 10.1145/800057.808675 , ISBN.  0-89791-133-4 , S2CID   17752833
• Харель, Дов; Тарьян, Роберт Э. (1984), «Быстрые алгоритмы поиска ближайших общих предков», SIAM Journal on Computing , 13 (2): 338–355, doi : 10.1137/0213024
• Ху, TC (1961), «Проблема маршрута максимальной пропускной способности», Operations Research , 9 (6): 898–900, doi : 10.1287/opre.9.6.898 , JSTOR   167055
• Ким, Сон Хван; Чо, Хван-Ге (2021), «Компактный индекс для сопоставления декартовых деревьев», у Гавриховского, Павел; Стариковская Татьяна (ред.), 32-й ежегодный симпозиум по комбинаторному сопоставлению с образцом, CPM 2021, 5–7 июля 2021 г., Вроцлав, Польша , LIPIcs, vol. 191, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, стр. 18:1–18:19, doi : 10.4230/LIPIcs.CPM.2021.18 , ISBN  9783959771863
• Леклерк, Бруно (1981), «Комбинаторное описание ультраметрики», Центр социальной математики. Практическая школа повышения квалификации. Математика и гуманитарные науки (на французском языке) (73): 5–37, 127, MR   0623034
• Левкопулос, Христос; Петерссон, Ола (1989), «Пирамичная сортировка, адаптированная для предварительно отсортированных файлов», WADS '89: Материалы семинара по алгоритмам и структурам данных , Конспекты лекций по информатике, том. 382, Лондон, Великобритания: Springer-Verlag, стр. 499–509, номер doi : 10.1007/3-540-51542-9_41 , ISBN.  978-3-540-51542-5
• Нисимото, Акио; Фудзисато, Норики; Накашима, Юто; Иненага, Сюнсуке (2021), «Кучи позиций для сопоставления декартовых деревьев на строках и попытках», в Лекроке, Тьерри; Тузе, Элен (ред.), Обработка строк и поиск информации — 28-й Международный симпозиум, SPIRE 2021, Лилль, Франция, 4–6 октября 2021 г., Материалы докладов , Конспекты лекций по информатике, том. 12944, Springer, стр. 241–254, arXiv : 2106.01595 , doi : 10.1007/978-3-030-86692-1_20 , ISBN  978-3-030-86691-4 , S2CID   235313506
• Оизуми, Цубаса; Кай, Такеши; Миено, Такуя; Иненага, Сюнсукэ; Аримура, Хироки (2022), «Сопоставление подпоследовательностей декартова дерева», в Баннаи, Хидео; Голуб, Ян (ред.), 33-й ежегодный симпозиум по комбинаторному сопоставлению с образцом, CPM 2022, 27–29 июня 2022 г., Прага, Чешская Республика , LIPIcs, vol. 223, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, стр. 14:1–14:18, doi : 10.4230/LIPIcs.CPM.2022.14 , ISBN  9783959772341 , S2CID   246679910
• Пак, Сон Гван; Амир, Дружелюбие; Ландау, Гад М.; Парк, Кунсу (2019), «Сопоставление и индексирование декартовых деревьев», в Пизанти, Надя; Писсис, Солон П. (ред.), 30-й ежегодный симпозиум по комбинаторному сопоставлению с образцом, CPM 2019, 18–20 июня 2019 г., Пиза, Италия , LIPics, vol. 128, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, стр. 16:1–16:14, arXiv : 1905.08974 , doi : 10.4230/LIPIcs.CPM.2019.16 , ISBN  9783959771030 , S2CID   162168587
• Пак, Сон Гван; Батаа, Магсарджав; Амир, Дружелюбие; Ландау, Гад М.; Парк, Кунсу (2020), «Нахождение закономерностей и периодов в сопоставлении декартовых деревьев», Theoretical Computer Science , 845 : 181–197, doi : 10.1016/j.tcs.2020.09.014 , S2CID   225227284
• Зейдель, Раймунд ; Арагон, Сесилия Р. (1996), «Рандомизированные деревья поиска» , Algorithmica , 16 (4/5): 464–497, doi : 10.1007/s004539900061 (неактивно 10 июня 2024 г.) {{citation}}: CS1 maint: DOI неактивен по состоянию на июнь 2024 г. ( ссылка )
• Шибер, Барух; Вишкин, Узи (1988), «О поиске наименьших общих предков: упрощение и распараллеливание», SIAM Journal on Computing , 17 (6): 1253–1262, doi : 10.1137/0217079
• Шун, Джулиан; Блеллок, Гай Э. (2014), «Простой алгоритм параллельного декартова дерева и его применение к построению параллельного суффиксного дерева», Транзакции ACM на параллельных вычислениях , 1 : 1–20, doi : 10.1145/2661653 , S2CID   1912378
• Сон, Сиу; Гу, Геонмо; Рю, Чоль; Фаро, Симона; Лекрок, Тьерри; Парк, Кунсу (2021), «Быстрые алгоритмы для сопоставления декартовых деревьев с одним и несколькими шаблонами», Theoretical Computer Science , 849 : 47–63, doi : 10.1016/j.tcs.2020.10.009 , S2CID   225142815
• Тарьян, Роберт Э .; Леви, Калеб С.; Тиммел, Стивен (2021), «Почтовые деревья», Транзакции ACM по алгоритмам , 17 (4): 34:1–34:12, arXiv : 1806.06726 , doi : 10.1145/3476830 , S2CID   49298052
• Вуйемен, Жан (1980), «Объединяющий взгляд на структуры данных», Communications of the ACM , 23 (4), Нью-Йорк, штат Нью-Йорк, США: ACM: 229–239, doi : 10.1145/358841.358852 , S2CID   10462194