Войти
В информатике и теории вероятностей, случайное двоичное дерево - это двоичное дерево, выбранное случайным образом из некоторого распределения вероятностей на двоичных деревьях. Обычно используются два разных распределения: двоичные деревья, сформированные путем вставки узлов по одному в соответствии с случайной перестановкой, и двоичные деревья, выбранные из равномерного дискретного распределения, в котором все отдельные деревья являются с равной вероятностью. Также возможно сформировать другие распределения, например, путем многократного разбиения. Добавление и удаление узлов непосредственно в случайном двоичном дереве, как правило, нарушает его случайную структуру, но treap и связанное с ним рандомизированное двоичное дерево поиска структуры данных используют принцип двоичных деревьев, сформированных из случайная перестановка для поддержания сбалансированного двоичного дерева поиска динамически по мере того, как узлы вставляются и удаляются.
Для случайных деревьев, которые не обязательно являются двоичными, см. случайное дерево.
Для любого набора чисел (или, в более общем смысле, значений из некоторого общего порядка ), можно сформировать двоичное дерево поиска в котором каждое число вставляется последовательно как лист дерева без изменения структуры ранее вставленных чисел. Позиция, в которую должно быть вставлено каждое число, однозначно определяется двоичным поиском в дереве, образованном предыдущими числами. Например, если три числа (1,3,2) вставляются в дерево в этой последовательности, число 1 будет находиться в корне дерева, число 3 будет помещено как его правый дочерний элемент, а число 2 как левый потомок числа 3. Есть шесть различных перестановок чисел (1,2,3), но только пять деревьев могут быть построены из них. Это потому, что перестановки (2,1,3) и (2,3,1) образуют одно и то же дерево.
Для любого фиксированного выбора значения x в заданном наборе из n чисел, если один случайным образом переставляет числа и формирует из них двоичное дерево, как описано выше, ожидаемое значение длины пути от корня дерева до x не превышает 2 log n + O (1), где «log» обозначает функцию натурального логарифма и O вводит нотацию большой O. Ибо ожидаемое количество предков x по линейности ожидания равно сумме по всем другим значениям y в наборе вероятности того, что y является предком x. И значение y является предком x именно тогда, когда y является первым элементом, который нужно вставить из элементов в интервале [x, y]. Таким образом, значения, смежные с x в отсортированной последовательности значений, имеют вероятность 1/2 того, что они являются предком x, значения, расположенные на один шаг, имеют вероятность 1/3 и т. Д. Сложение этих вероятностей для всех позиций в отсортированной последовательности дает дважды Гармоническое число, что приводит к приведенной выше оценке. Граница этой формы сохраняется также для ожидаемой длины поиска пути к фиксированному значению x, которое не является частью данного набора.
Хотя не так легко проанализировать Что касается средней длины пути, то также было проведено много исследований по определению математического ожидания (или границ высокой вероятности) длины самого длинного пути в двоичном дереве поиска, созданном из случайного порядка вставки. Теперь известно, что эта длина для дерева с n узлами почти наверняка
где β - уникальное число в диапазоне 0 < β < 1 satisfying the equation
В модели случайной перестановки каждое из чисел из набора чисел, используемых для формирования дерева, за исключением наименьшего и наибольшего числа, имеет вероятность 1 / 3 листа на дереве, потому что это лист, когда он вставлен после двух своих соседей, и любая из шести перестановок этих двух соседей, и это равновероятно. По аналогичным соображениям наименьшее и наибольшее числа имеют вероятность 1/2 быть листом. Следовательно, ожидаемое количество листьев - это сумма этих вероятностей, которая для n ≥ 2 равна точно (n + 1) / 3.
В приложениях, использующих структуры данных бинарного дерева поиска, значения в дерево редко вставляются без удаления в случайном порядке, что ограничивает непосредственные приложения случайных бинарных деревьев. Однако разработчики алгоритмов разработали структуры данных, которые позволяют выполнять вставки и удаления в двоичном дереве поиска, на каждом шаге сохраняя в качестве инварианта свойство, что форма дерева является случайной величиной с тем же распределением, что и случайный двоичный поиск. дерево.
Если данному набору упорядоченных чисел назначены числовые приоритеты (отдельные числа, не связанные с их значениями), эти приоритеты могут использоваться для построения декартова дерева для чисел, двоичного дерева, которое имеет в качестве своей неупорядоченной последовательности обхода отсортированную последовательность чисел, которая упорядочена в куче по приоритетам. Хотя известны более эффективные алгоритмы построения, полезно думать о декартовом дереве как о построенном путем вставки заданных чисел в двоичное дерево поиска в порядке приоритета. Таким образом, выбирая приоритеты либо как набор независимых случайных действительных чисел в единичном интервале, либо выбирая их как случайную перестановку чисел от 1 до n (где n - количество узлов в дереве), и, поддерживая свойство упорядочивания кучи с использованием поворота дерева после любой вставки или удаления узла, можно поддерживать структуру данных, которая ведет себя как случайное двоичное дерево поиска. Такая структура данных известна как treap или рандомизированное двоичное дерево поиска.
Количество двоичных деревьев с n узлами равно Каталонское число : для n = 1, 2, 3,... эти числа деревьев равны
Таким образом, если одно из этих деревьев выбрано равномерно случайным образом, его вероятность будет обратной величиной каталонского числа. Деревья в этой модели имеют ожидаемая глубина пропорциональна квадратному корню из n, а не логарифму; однако число Стрелера равномерно случайного двоичного дерева, более чувствительная мера расстояния от листа, в котором узел имеет Strahler число i, если у него есть дочерний элемент с этим номером или два дочерних элемента с номером i - 1, с высокой вероятностью логарифмический.
Из-за их большой высоты эта модель равновероятных случайных деревьев обычно не используется для двоичных поиск по деревьям, но это было применено d к проблемам моделирования деревьев разбора алгебраических выражений в конструкции компилятора (где вышеупомянутая граница числа Стрелера переводится в число регистры, необходимые для оценки выражения) и для моделирования эволюционных деревьев. В некоторых случаях анализ случайных бинарных деревьев в рамках модели случайных перестановок может быть автоматически перенесен в унифицированную модель.
Devroye Kruszewski (1996) генерируют случайные бинарные деревья с n узлов путем генерации случайной величины x с действительным знаком в единичном интервале (0,1), присвоения первых узлов xn (с округлением до целого числа узлов) левому поддереву, следующего узла корню и оставшимся узлов в правое поддерево и рекурсивно продолжаются в каждом поддереве. Если x выбирается равномерно случайным образом в интервале, результат будет таким же, как и случайное двоичное дерево поиска, сгенерированное случайной перестановкой узлов, поскольку любой узел с равной вероятностью будет выбран в качестве корня; однако эта формулировка позволяет использовать вместо этого другие дистрибутивы. Например, в модели равномерно случайного двоичного дерева после того, как корень зафиксирован, каждое из его двух поддеревьев также должно быть равномерно случайным, поэтому равномерно случайная модель также может быть сгенерирована с помощью другого выбора распределения для x. Как показывают Деврой и Крушевский, выбирая бета-распределение по x и используя соответствующий выбор формы для рисования каждой из ветвей, можно использовать математические деревья, сгенерированные этим процессом. для создания реалистичных ботанических деревьев.
