Случайное двоичное дерево

Два случайных распределения на бинарных деревьях с тремя вершинами, деревья двоичного поиска по трем ключам a , b и c . Каждому из этих пяти деревьев присвоена вероятность 1/5 по равномерному распределению (вверху). Распределение, генерируемое случайным порядком вставки (внизу), присваивает вероятность центрального дерева 1/3, поскольку два из шести возможных порядков вставки генерируют одно и то же дерево; остальные четыре дерева имеют вероятность 1/6.

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

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

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

Информацию о случайных деревьях, которые не обязательно являются двоичными, см. в разделе « Случайное дерево» .

Фон

Расширенное двоичное дерево, в котором внутренние узлы показаны желтыми кружками, а внешние узлы - красными квадратами.

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

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

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

Из случайных перестановок

Двоичное дерево, созданное из 100-элементной случайной перестановки

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

Например, если три ключа 1,3,2 вставлены в двоичное дерево поиска в этой последовательности, число 1 будет находиться в корне дерева, число 3 будет помещено в качестве его правого дочернего элемента, а число 2 как левый дочерний элемент числа 3. Существует шесть различных перестановок ключей 1, 2 и 3, но из них можно построить только пять деревьев. Это потому, что перестановки 2,1,3 и 2,3,1 образуют одно и то же дерево. Таким образом, это дерево имеет вероятность ${\tfrac {2}{6}}={\tfrac {1}{3}}$ быть сгенерированным, тогда как каждое из четырех других деревьев имеет вероятность ${\tfrac {1}{6}}$.

Ожидаемая глубина узла

Для любого ключа $x$ в заданном наборе $n$ ключей, ожидаемое значение длины пути от корня до $x$ в случайном двоичном дереве поиска не более $2\log n+O(1)$, где " $\log$" обозначает функцию натурального логарифма , а $O$ вводит обозначение большого О. По линейности ожидания ожидаемое число предков $x$ равно сумме по другим ключам $y$, вероятности того, что $y$ является предком $x$. Ключ $y$ является предком $x$ именно когда $y$ это первый ключ, который будет вставлен из интервала $[x,y]$. Поскольку каждый ключ в интервале с равной вероятностью окажется первым, это происходит с вероятностью, обратной длине интервала. Таким образом, клавиши, расположенные рядом с $x$ в отсортированной последовательности ключей имеют вероятность ${\tfrac {1}{2}}$ быть предком $x$, ключи, находящиеся на расстоянии одного шага, имеют вероятность ${\tfrac {1}{3}}$и т. д. Сумма этих вероятностей образует две копии гармонического ряда, идущие от $x$ в обоих направлениях в отсортированной последовательности, что дает $2\log n+O(1)$ привязано выше. Эта граница также справедлива для ожидаемой длины пути поиска значения. $x$ это один из заданных ключей.

Самый длинный путь

Самый длинный путь от корня к листу в случайном двоичном дереве поиска длиннее ожидаемой длины пути, но только в постоянный коэффициент. Его длина, для дерева с $n$ узлов, с большой вероятностью приблизительно

$\displaystyle {\frac {1}{\beta }}\log n\approx 4.311\log n,$

где $\beta$ это уникальный номер в диапазоне $0<\beta <1$ удовлетворяющее уравнению

$\displaystyle 2\beta e^{1-\beta }=1.$

Ожидаемое количество листьев

В модели случайной перестановки каждый ключ, кроме наименьшего и наибольшего, имеет вероятность ${\tfrac {1}{3}}$ быть листом на дереве. Это происходит потому, что он является листом, когда он вставляется после двух своих соседей, что происходит для двух из шести перестановок его и двух его соседей, причем все они одинаково вероятны. По аналогичным рассуждениям наименьший и наибольший ключ имеют вероятность ${\tfrac {1}{2}}$ быть листом. Следовательно, ожидаемое количество листьев представляет собой сумму этих вероятностей, которые для $n\geq 2$ это точно $(n+1)/3$.

Номер прожектора

Число вершин Стралера в любом дереве является мерой сложности поддеревьев под этими вершинами. Лист (внешний узел) имеет номер Стралера один. Для любого другого узла число Стралера определяется рекурсивно из чисел Стралера его дочерних узлов. В двоичном дереве, если два дочерних элемента имеют разные числа Стралера, число Стралера их родителя является большим из двух дочерних чисел. Но если у двух детей одинаковые числа Стралера, у их родителя число больше на единицу. Число Стралера всего дерева — это число в корневом узле. Для $n$-узловые деревья случайного двоичного поиска, моделирование показывает, что ожидаемое число Стралера равно $\log _{3}n+O(1)$. Более слабая верхняя граница $\log _{3}n+o(\log n)$ было доказано.

Treaps и рандомизированные двоичные деревья поиска

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

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

Варианты Treap, включая zip-дерево и zip-zip-дерево, заменяют вращение дерева операциями «сжатия», которые разделяют и объединяют деревья и ограничивают количество случайных битов, которые необходимо генерировать и хранить вместе с ключами. Результатом этих оптимизаций по-прежнему остается дерево со случайной структурой, но оно не совсем соответствует модели случайных перестановок.

Равномерно случайные бинарные деревья

Равномерно случайное двоичное дерево со 100 узлами.

Количество бинарных деревьев с $n$ nodes — каталонское число . Для $n=1,2,3,\dots$ это количество деревьев

1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ... (последовательность A000108 в OEIS ).

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

${\sqrt {\pi n}}-3+O\left({\frac {1}{\sqrt {n}}}\right)$.

Ожидаемое число Стралера равномерно случайной $n$-узловое двоичное дерево $\log _{4}n+O(1)$, что ниже ожидаемого количества случайных деревьев двоичного поиска Стралера.

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

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

Алгоритм Жана-Люка Реми генерирует равномерно случайное двоичное дерево заданного размера за линейное по размеру время с помощью следующего процесса. Начните с дерева, состоящего из одного внешнего узла. Затем, пока текущее дерево не достигло целевого размера, равномерно случайным образом повторно выберите один из его узлов (внутренний или внешний). Замените выбранный узел новым внутренним узлом, имея выбранный узел в качестве одного из его дочерних элементов (одинаково вероятно, левый или правый) и имея новый внешний узел в качестве другого дочернего элемента. Остановитесь, когда будет достигнут целевой размер.

Ветвящиеся процессы

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

• В версии, где корневой узел может быть внешним, с некоторой заданной вероятностью он выбирается внутренним. $p$ или внешний с вероятностью $1-p$. Если он внутренний, два его дочерних элемента — это деревья, рекурсивно созданные одним и тем же процессом.
• В версии, где корневой узел должен быть внутренним, его левый и правый дочерние элементы определяются как внутренние с вероятностью $p$ или внешний с вероятностью $1-p$, независимо друг от друга. В том случае, если они являются внутренними, они являются корнями деревьев, которые рекурсивно генерируются одним и тем же процессом.

Деревья, созданные таким способом, получили название бинарных деревьев Гальтона-Ватсона . В частном случае, когда $p={\tfrac {1}{2}}$ их называют критическими бинарными деревьями Гальтона–Ватсона .

Анализ

Вероятность $p={\tfrac {1}{2}}$ знаменует фазовый переход для бинарного процесса Гальтона – Ватсона: для $p\leq {\tfrac {1}{2}}$ полученное дерево почти наверняка конечно , тогда как для $p>{\tfrac {1}{2}}$ оно бесконечно с положительной вероятностью. Точнее, для любого $p$, вероятность того, что дерево останется конечным, равна

$\displaystyle \min \left\{1,{\frac {1-p}{p}}\right\}$.

Другой способ сгенерировать такие же деревья — создать последовательность подбрасываний монеты с вероятностью $p$ орел и вероятность $1-p$ решок, до тех пор, пока не произойдет первый подброс, при котором количество решок превысит количество орлов (для модели, в которой разрешен внешний корень) или не превысит единицу плюс количество орлов (когда корень должен быть внутренним), а затем используйте эта последовательность подбрасываний монеты определяет выбор, сделанный в процессе рекурсивной генерации, в порядке глубины.

Поскольку количество внутренних узлов равно количеству орлов в этой последовательности подбрасывания монеты, все деревья с заданным номером $n$ узлов генерируются из (уникальных) последовательностей подбрасывания монеты одинаковой длины и одинаково вероятны, независимо от $p$. То есть выбор $p$ влияет на изменение размера деревьев, генерируемых этим процессом, но для данного размера деревья генерируются равномерно и случайным образом. Для значений $p$ ниже критической вероятности $p={\tfrac {1}{2}}$, меньшие значения $p$ создаст деревья с меньшим ожидаемым размером, в то время как большие значения $p$ создаст деревья большего ожидаемого размера. При критической вероятности $p={\tfrac {1}{2}}$ не существует конечной границы ожидаемого размера деревьев, генерируемых этим процессом. Точнее, для любого $p$, ожидаемое количество узлов на глубине $i$ на дереве есть $(2p)^{i}$, а ожидаемый размер дерева можно получить путем суммирования ожидаемого количества узлов на каждой глубине. Для $p<{\tfrac {1}{2}}$ это дает геометрическую прогрессию

$\displaystyle 1+(2p)+(2p)^{2}+\cdots ={\frac {1}{1-2p}}$,

для ожидаемого размера дерева, но для $p={\tfrac {1}{2}}$ это дает 1 + 1 + 1 + 1 + ⋯ , расходящийся ряд .

Для $p={\tfrac {1}{2}}$, любое конкретное дерево с $n$ внутренние узлы создаются с вероятностью $1/2^{2n+1}$, а вероятность того, что случайное дерево имеет такой размер, равна этой вероятности, умноженной на каталонское число:

${\frac {C_{n}}{2^{2n+1}}}={\frac {1}{2n+1}}{\binom {2n+1}{n}}{\frac {1}{2^{2n+1}}}\approx {\frac {1}{{\sqrt {4\pi }}\,n^{3/2}}}\displaystyle$.

Приложения

Процессы Гальтона-Ватсона изначально были разработаны для изучения распространения и исчезновения человеческих фамилий и широко применялись в более общем плане к динамике популяций людей и животных. Эти процессы были обобщены на модели, в которых вероятность быть внутренним или внешним узлом на данном уровне дерева ( поколение в приложении динамики населения) не фиксирована, а зависит от количества узлов на предыдущем уровне. Вариант этого процесса с критической вероятностью ${\tfrac {1}{2}}$, был изучен как модель видообразования , где он известен как критический процесс ветвления . В этом процессе каждый вид имеет экспоненциально распределенную продолжительность жизни и в течение своей жизни производит дочерние виды со скоростью, равной продолжительности жизни. Когда рождается ребенок, родитель продолжает оставаться левой ветвью эволюционного дерева, а ребенок становится правой ветвью.

Другое применение критических деревьев Гальтона – Ватсона (в версии, где корень должен быть внутренним) возникает в алгоритме Каргера – Штейна для поиска минимальных разрезов в графах с использованием рекурсивного процесса сужения ребер . Этот алгоритм вызывает себя дважды рекурсивно, причем вероятность каждого вызова не менее ${\tfrac {1}{2}}$ сохранения правильного значения решения. Случайное дерево моделирует поддерево правильных рекурсивных вызовов. Алгоритм успешен на графе $n$ вершины всякий раз, когда это случайное дерево правильных рекурсивных вызовов имеет ветвь глубины не менее $2\log _{2}n$, достигая базового случая его рекурсии. Вероятность успеха равна $\Omega (1/\log n)$, производя один из логарифмических коэффициентов в алгоритме $O(n^{2}\log ^{3}n)$ время выполнения.

Святочный процесс

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

Двоичные попытки

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

Другая форма двоичного дерева, двоичное дерево или цифровое дерево поиска, имеет набор двоичных чисел, обозначающих некоторые из его внешних узлов. Внутренние узлы дерева представляют собой префиксы своих двоичных представлений, которые являются общими для двух или более чисел. Левый и правый дочерние элементы внутреннего узла получаются путем расширения соответствующего префикса еще на один бит, нулевой или один бит соответственно. Если это расширение не соответствует ни одному из заданных номеров или соответствует только одному из них, результатом является внешний узел; в противном случае это другой внутренний узел. Случайные двоичные попытки были изучены, например, для наборов случайных действительных чисел, сгенерированных независимо в единичном интервале . Несмотря на то, что эти деревья могут иметь пустые внешние узлы, они, как правило, лучше сбалансированы, чем деревья случайного двоичного поиска. Для $n$ равномерно случайные действительные числа в единичном интервале или, в более общем плане, для любого интегрируемого с квадратом распределения вероятностей на единичном интервале средняя глубина узла асимптотически равна $\log _{2}n$, а средняя высота всего дерева асимптотически равна $2\log _{2}n$. Анализ этих деревьев может быть применен к вычислительной сложности на основе деревьев алгоритмов сортировки .

Вариант дерева, базисное дерево или сжатое дерево, исключает пустые внешние узлы и их родительские внутренние узлы. Остальные внутренние узлы соответствуют префиксам, для которых оба возможных расширения, на ноль или на один бит, используются хотя бы одним из случайно выбранных чисел. Для поразрядного дерева для $n$ двоичные числа равномерно распределены, кратчайший путь от корня листа имеет длину $$\log _{2}n-\log _{2}\log n+o(\log \log n)$$ и самый длинный путь от корня листа имеет длину $$\log _{2}n+{\sqrt {2\log _{2}n}}+o({\sqrt {\log n}}),$$ и то, и другое с большой вероятностью .

Случайное разделение деревьев

Люк Деврой и Пол Крушевски описывают рекурсивный процесс построения случайных двоичных деревьев с помощью $n$ узлы. Он генерирует вещественную случайную величину $x$ в единичном интервале $(0,1)$, присваивает первый $xn$ узлы (округленные до целого числа узлов) в левом поддереве, следующий узел в корне и оставшиеся узлы в правом поддереве. Затем он продолжает рекурсивно использовать тот же процесс в левом и правом поддеревьях. Если $x$ выбирается равномерно случайным образом в интервале, результат тот же, что и случайное двоичное дерево поиска, созданное случайной перестановкой узлов, поскольку любой узел с равной вероятностью будет выбран в качестве корня. Однако эта формулировка позволяет использовать вместо этого другие распределения. Например, в модели равномерно случайного двоичного дерева, как только корень фиксирован, каждое из двух его поддеревьев также должно быть равномерно случайным, поэтому равномерно случайная модель также может быть создана с помощью другого выбора распределения (в зависимости от $n$) для $x$. Как они показывают, выбрав бета-дистрибутив на $x$ а используя соответствующий выбор формы для рисования каждой из ветвей, математические деревья, созданные в результате этого процесса, можно использовать для создания реалистично выглядящих ботанических деревьев.

Ссылки

• Олдос, Дэвид (1996), «Распределение вероятностей на кладограммах», Олдос, Дэвид; Пемантл, Робин (ред.), Случайные дискретные структуры , Тома IMA по математике и ее приложениям, том. 76, Springer-Verlag, стр. 1–18, номер документа : 10.1007/978-1-4612-0719-1_1.
• Атрея, Кришна Б.; Ней, Питер Э. (1972), Ветвящиеся процессы , Берлин: Springer-Verlag, стр. 199–206, номер домена : 10.1007/978-3-642-65371-1 , ISBN.  978-3-642-65371-1
• Бертин, Эрик (2021), Статистическая физика сложных систем: краткое введение , Серия Springer по синергетике (3-е изд.), Springer International Publishing, doi : 10.1007/978-3-030-79949-6 , ISBN  9783030799496
• Браун, Джеральд Г.; Шуберт, Бруно О. (1984), «О случайных двоичных деревьях» , Математика исследования операций , 9 : 43–65, doi : 10.1287/moor.9.1.43
• Броутен, Николя; Деврой, Люк ; Фрайман, Николас (апрель 2020 г.), «Рекурсивные функции на условных деревьях Гальтона – Ватсона» (PDF) , Случайные структуры и алгоритмы , 57 (2), Wiley: 304–316, doi : 10.1002/rsa.20921
• Бурд, Грегори А.; Уэймир, Эдвард К.; Винн, Рональд Д. (февраль 2000 г.), «Самоподобная инвариантность критических бинарных деревьев Гальтона – Ватсона» , Бернулли , 6 (1): 1–21, JSTOR   3318630
• Деврой, Люк (1984), «Вероятностный анализ высоты попыток и сложности тройной сортировки» (PDF) , Acta Informatica , 21 : 229–237, doi : 10.1007/BF00264248
• Деврой, Люк (1986), «Заметки о высоте двоичных деревьев поиска» (PDF) , Журнал ACM , 33 (3): 489–498, doi : 10.1145/5925.5930
• Деврой, Люк (январь 1992 г.), «Заметка о вероятностном анализе деревьев Патриции» (PDF) , Случайные структуры и алгоритмы , 3 (2): 203–214, doi : 10.1002/rsa.3240030209
• Деврой, Люк ; Крушевски, Пол (1995), «Заметки о числе Хортона – Стралера для случайных деревьев» (PDF) , Information Processing Letters , 56 (2): 95–99, doi : 10.1016/0020-0190(95)00114-R
• Деврой, Люк ; Крушевски, Пол (1996), «Ботаническая красота случайных бинарных деревьев» (PDF) , в Бранденбурге, Франц Дж. (ред.), Рисунок графика: 3-е межд. Symp., GD'95, Пассау, Германия, 20–22 сентября 1995 г. , Конспекты лекций по информатике, том. 1027, Springer-Verlag, стр. 166–177, doi : 10.1007/BFb0021801 , ISBN.  978-3-540-60723-6
• Деврой, Люк ; Робсон, Джон Майкл (декабрь 1995 г.), «О создании случайных бинарных деревьев поиска» (PDF) , SIAM Journal on Computing , 24 (6): 1141–1156, doi : 10.1137/s0097539792224954
• Дрмота, Майкл (2009), Случайные деревья: взаимодействие комбинаторики и вероятности , Springer-Verlag, doi : 10.1007/978-3-211-75357-6 , ISBN  978-3-211-75355-2
• Флажоле, П. ; Рауль, Дж.К.; Вуйемен, Дж. (1979), «Количество регистров, необходимых для оценки арифметических выражений» (PDF) , Theoretical Computer Science , 9 (1): 99–125, doi : 10.1016/0304-3975(79)90009-4
• Гила, Офек; Гудрич, Майкл Т .; Тарьян, Роберт Э. (2023), «Деревья-застежки-молнии: сделать деревья-застежки более сбалансированными, смещенными, компактными или постоянными», Морин, Пэт ; Сури, Субхаш (ред.), Алгоритмы и структуры данных – 18-й Международный симпозиум, WADS 2023, Монреаль, Квебек, Канада, 31 июля – 2 августа 2023 г., Материалы докладов , Конспекты лекций по информатике, том. 14079, Springer, стр. 474–492, arXiv : 2307.07660 , doi : 10.1007/978-3-031-38906-1_31.
• Харрис, Т.Э. (1952), «Первый проход и повторяющиеся распределения», Труды Американского математического общества , 73 (3): 471–486, doi : 10.1090/s0002-9947-1952-0052057-2
• Хиббард, Томас Н. (1962), «Некоторые комбинаторные свойства некоторых деревьев с применением к поиску и сортировке», Журнал ACM , 9 (1): 13–28, doi : 10.1145/321105.321108
• Ягерс, Питер (2011), «Вымирание, сохранение и эволюция», в Чалубе, Фабио АКК; Родригес, Хосе Франциско (ред.), Математика наследия Дарвина , Математика и биологические науки во взаимодействии, Базель: Биркхойзер, стр. 91–104, doi : 10.1007/978-3-0348-0122-5_5 , ISBN  9783034801225
• Каргер, Дэвид Р .; Стейн, Клиффорд (1996), «Новый подход к проблеме минимального разреза» (PDF) , Журнал ACM , 43 (4): 601, doi : 10.1145/234533.234534
• Кеннеди, Дуглас П. (1975), «Процесс Гальтона-Ватсона, обусловленный общим потомством», Journal of Applied Probability , 12 : 800–806, doi : 10.2307/3212730
• Кнут, Дональд Э. (1973), «6.2.2 Поиск в двоичном дереве», Искусство компьютерного программирования, Vol. III: Сортировка и поиск , Аддисон-Уэсли, стр. 422–451.
• Кнут, Дональд Э. (1997), «2.3.4.5 Длина пути», Искусство компьютерного программирования, Vol. I: Получисловые алгоритмы (3-е изд.), Аддисон-Уэсли, стр. 399–406.
• Кнут, Дональд Э. (2005), «Проект раздела 7.2.1.6: Создание всех деревьев» , Искусство компьютерного программирования , том. IV
• Крушевски, Пол (1999), «Заметки о числе Хортона – Стралера для случайных деревьев двоичного поиска», Information Processing Letters , 69 (1): 47–51, doi : 10.1016/S0020-0190(98)00192-6
• Мякинен, Эркки; Силтанева, Ярмо (2003), «Заметка об алгоритме Реми для генерации случайных двоичных деревьев», Missouri Journal of Mathematical Sciences , 15 (2): 103–109, doi : 10.35834/2003/1502103
• Махмуд, Хосам М. (1992), Эволюция деревьев случайного поиска , John Wiley & Sons
• Мартинес, Конрадо; Роура, Сальвадор (1998), «Рандомизированные двоичные деревья поиска», Журнал ACM , 45 (2): 288–323, CiteSeerX   10.1.1.17.243 , doi : 10.1145/274787.274812
• Морин, Пэт (22 марта 2014 г.), «Глава 7: Случайные двоичные деревья поиска», Структуры открытых данных (в псевдокоде) (PDF) (изд. 0.1Gβ), стр. 145–164
• Питтель, Б. (1985), «Асимптотический рост класса случайных деревьев», Annals of Probability , 13 (2): 414–427, doi : 10.1214/aop/1176993000
• Попович, Леа (ноябрь 2004 г.), «Асимптотическая генеалогия критического ветвящегося процесса», Annals of Applied Probability , 14 (4), arXiv : math/0503577 , doi : 10.1214/105051604000000486
• Рид, Брюс (2003), «Высота случайного двоичного дерева поиска», Журнал ACM , 50 (3): 306–332, doi : 10.1145/765568.765571
• Реми, Жан-Люк (1985), «Итеративный процесс подсчета двоичных деревьев и его применение к их случайной генерации» , RAIRO Theoretical Informatics (на французском языке), 19 : 179–195.
• Робсон, Дж. М. (1979), «Высота бинарных деревьев поиска», Australian Computer Journal , 11 : 151–153.
• Зейдель, Раймунд ; Арагон, Сесилия Р. (1996), «Рандомизированные деревья поиска», Algorithmica , 16 (4–5): 464–497, doi : 10.1007/s004539900061
• Седжвик, Роберт ; Флажоле, Филипп (2013), «Глава 6: Деревья», Введение в анализ алгоритмов (2-е изд.), Аддисон-Уэсли, ISBN  9780133373486
• Шрив, Рональд Л. (январь 1966 г.), «Статистический закон чисел потоков», The Journal of Geology , 74 (1): 17–37, JSTOR   30075174
• Тарьян, Роберт Э .; Леви, Калеб С.; Тиммел, Стивен (2021), «Почтовые деревья», Транзакции ACM по алгоритмам , 17 (4): 34:1–34:12, arXiv : 1806.06726 , doi : 10.1145/3476830
• Вийемен, Жан (1980), «Объединяющий взгляд на структуры данных», Communications of the ACM , 23 (4): 229–239, doi : 10.1145/358841.358852