В информатике и теории вероятностей , случайная бинарное дерево представляет собой бинарное дерево выбирается случайным образом из некоторого распределения вероятностей на бинарных деревьев. Обычно используются два разных распределения: бинарные деревья, сформированные путем вставки узлов по одному в соответствии со случайной перестановкой , и бинарные деревья, выбранные из однородного дискретного распределения, в котором все различные деревья равновероятны. Также возможно сформировать другие распределения, например, путем многократного разбиения. Добавление и удаление узлов непосредственно в случайном двоичном дереве, как правило, нарушает его случайную структуру, но treapи связанные структуры данных рандомизированного двоичного дерева поиска используют принцип двоичных деревьев, сформированных из случайной перестановки, чтобы динамически поддерживать сбалансированное двоичное дерево поиска при вставке и удалении узлов.
Для случайных деревьев, которые не обязательно являются двоичными, см. Случайное дерево .
Бинарные деревья из случайных перестановок
Для любого набора чисел (или, в более общем смысле, значений из некоторого общего порядка ) можно сформировать двоичное дерево поиска, в котором каждое число вставляется последовательно как лист дерева без изменения структуры ранее вставленных чисел. Позиция, в которую должно быть вставлено каждое число, однозначно определяется двоичным поиском в дереве, образованном предыдущими числами. Например, если три числа (1,3,2) вставляются в дерево в этой последовательности, число 1 будет находиться в корне дерева, число 3 будет помещено в качестве его правого дочернего элемента, а число 2 как левый потомок числа 3. Существует шесть различных перестановок чисел (1,2,3), но из них можно построить только пять деревьев. Это потому, что перестановки (2,1,3) и (2,3,1) образуют одно и то же дерево.
Ожидаемая глубина узла
Для любого фиксированного выбора значения x в заданном наборе из n чисел, если один случайным образом переставляет числа и формирует из них двоичное дерево, как описано выше, ожидаемое значение длины пути от корня дерева до x самое большее 2 лог п + O (1) , где « журнал » означает натуральный логарифм функции и O вводит большое обозначение вывода . Ибо ожидаемое количество предков x по линейности ожидания равно сумме по всем другим значениям y в наборе вероятности того, что y является предком x . И значение y является предком x именно тогда, когда y является первым элементом, который нужно вставить из элементов в интервале [ x , y ] . Таким образом, значения, смежные с x в отсортированной последовательности значений, имеют вероятность 1/2 того, что они являются предком x , значения, расположенные на один шаг, имеют вероятность 1/3 и т. Д. Сложение этих вероятностей для всех позиций в отсортированной последовательности дает удвоенное число гармоники , что приводит к приведенной выше оценке. Граница этой формы сохраняется также для ожидаемой длины поиска пути к фиксированному значению x , которое не является частью данного набора. [1]
Самый длинный путь
Хотя анализировать не так просто, как среднюю длину пути, было проведено много исследований по определению математического ожидания (или границ высокой вероятности) длины самого длинного пути в двоичном дереве поиска, созданном на основе случайного порядка вставки. Теперь известно, что эта длина для дерева с n узлами почти наверняка
где β - единственное число в диапазоне 0 < β <1, удовлетворяющее уравнению
Ожидаемое количество листьев
В модели случайной перестановки каждое из чисел из набора чисел, используемых для формирования дерева, за исключением наименьшего и наибольшего чисел, имеет вероятность 1/3 быть листом в дереве, поскольку это лист, когда он вставлен после двух своих соседей и любой из шести перестановок этих двух соседей, и это одинаково вероятно. По аналогичным соображениям наименьшее и наибольшее из чисел имеют вероятность 1/2 быть листом. Следовательно, ожидаемое количество листьев - это сумма этих вероятностей, которая для n ≥ 2 составляет в точности ( n + 1) / 3 .
Номер Strahler
Число Стрелера дерева является более чувствительной мерой расстояния от листа, на котором узел имеет номер Стрелера i, если у него есть либо дочерний элемент с этим номером, либо два дочерних элемента с номером i - 1 . Для n- узловых случайных деревьев двоичного поиска моделирование предполагает, что ожидаемое число Стрелера равно. Однако только верхняя границадействительно было доказано. [3]
Treaps и рандомизированные бинарные деревья поиска
В приложениях структур данных двоичного дерева поиска редко значения в дереве вставляются без удаления в случайном порядке, что ограничивает непосредственное применение случайных двоичных деревьев. Однако разработчики алгоритмов разработали структуры данных, которые позволяют выполнять вставки и удаления в двоичном дереве поиска, на каждом шаге сохраняя в качестве инварианта свойство, что форма дерева является случайной величиной с тем же распределением, что и случайный двоичный поиск. дерево.
Если данному набору упорядоченных чисел назначены числовые приоритеты (отдельные числа, не связанные с их значениями), эти приоритеты могут использоваться для построения декартова дерева для чисел, двоичного дерева, которое имеет в качестве своей последовательности обхода в порядке сортировки отсортированную последовательность чисел. и это упорядочено по приоритетам. Хотя известны более эффективные алгоритмы построения, полезно думать о декартовом дереве как о построенном путем вставки заданных чисел в двоичное дерево поиска в порядке приоритета. Таким образом, выбирая приоритеты либо как набор независимых случайных действительных чисел в единичном интервале, либо выбирая их как случайную перестановку чисел от 1 до n (где n - количество узлов в дереве), и, поддерживая свойство упорядочивания кучи с использованием вращения дерева после любой вставки или удаления узла, можно поддерживать структуру данных, которая ведет себя как случайное двоичное дерево поиска. Такая структура данных известна как treap или рандомизированное двоичное дерево поиска. [4]
Равномерно случайные двоичные деревья
Количество двоичных деревьев с n узлами является каталонским числом : для n = 1, 2, 3, ... эти числа деревьев равны
Таким образом, если одно из этих деревьев выбрано равномерно случайным образом, его вероятность является обратной величиной каталонского числа. Деревья в этой модели имеют ожидаемую глубину, пропорциональную квадратному корню из n , а не логарифму. [5] Однако ожидаемое число Стрелера для равномерно случайного двоичного дерева с n узлами равно[6] ниже, чем ожидаемое число Стрелера для случайных деревьев двоичного поиска.
Из - за их больших высотах, эта модель равновероятных случайных деревьев обычно не используется для бинарных деревьев поиска, но она была применена к задачам моделирования деревьев разбора из алгебраических выражений в компиляторе конструкции [7] (где указанная выше , связанного на Число Стрелера переводится в количество регистров, необходимых для вычисления выражения [8] ) и для моделирования эволюционных деревьев . [9] В некоторых случаях анализ случайных бинарных деревьев в рамках модели случайной перестановки может быть автоматически перенесен в унифицированную модель. [10]
Случайное разделение деревьев
Devroye & Kruszewski (1996) генерируют случайные двоичные деревья с n узлами, генерируя действительную случайную величину x в единичном интервале (0,1) , присваивая первые xn узлов (с округлением до целого числа узлов) слева поддерево, следующий узел к корню и оставшиеся узлы к правому поддереву, и рекурсивно продолжается в каждом поддереве. Если x выбирается равномерно случайным образом в интервале, результат будет таким же, как и случайное двоичное дерево поиска, сгенерированное случайной перестановкой узлов, поскольку любой узел с равной вероятностью будет выбран в качестве корня; однако эта формулировка позволяет использовать вместо этого другие дистрибутивы. Например, в модели равномерно случайного двоичного дерева после того, как корень зафиксирован, каждое из его двух поддеревьев также должно быть равномерно случайным, поэтому равномерно случайная модель также может быть сгенерирована с помощью другого выбора распределения для x . Как показывают Деврой и Крушевски , выбирая бета-распределение по x и используя соответствующий выбор формы для рисования каждой из ветвей, математические деревья, сгенерированные этим процессом, можно использовать для создания реалистичных ботанических деревьев.
Заметки
- ^ Хиббард (1962) ; Кнут (1973) ; Махмуд (1992) , стр. 75.
- ^ Робсон (1979) ; Питтель (1985) ; Деврой (1986) ; Махмуд (1992) , стр. 91–99; Рид (2003) .
- ^ Kruszewski (1999)
- ^ Мартинес и Роура (1998) ; Зайдель и Арагон (1996) .
- ↑ Knuth (2005) , стр. 15.
- ^ , Devroye & Kruszewski (1995)
- ↑ Махмуд (1992) , стр. 63.
- ^ Flajolet, Raoult & Vuillemin (1979) .
- ^ Олдос (1996) .
- ↑ Махмуд (1992) , стр. 70.
Рекомендации
- Олдос, Дэвид (1996), «Распределения вероятностей на кладограммах», в Олдосе, Дэвид; Пемантл, Робин (ред.), Случайные дискретные структуры , Объемы IMA по математике и ее приложениям, 76 , Springer-Verlag, стр. 1–18..
- Devroye, Люк (1986), "Замечание о высоте бинарных деревьев поиска", Журнал ACM , 33 (3): 489-498, DOI : 10,1145 / 5925,5930.
- Деврой, Люк; Крушевски, Пол (1995), «Заметка о числе Хортона-Стрелера для случайных деревьев», Письма об обработке информации , 56 (2): 95–99, DOI : 10.1016 / 0020-0190 (95) 00114-R.
- Деврой, Люк; Крушевски, Пауль (1996), «Ботаническая красота случайных бинарных деревьев», в Бранденбурге, Франц Й. (ред.), Graph Drawing: 3rd Int. Symp, GD'95, Пассау, Германия, 20-22 сентября, 1995. , Lecture Notes в области компьютерных наук, 1027 , Springer-Verlag, стр 166-177,. Дои : 10.1007 / BFb0021801 , ISBN 978-3-540-60723-6.
- Дрмота, Майкл (2009), Случайные деревья: взаимодействие между комбинаторикой и вероятностью , Springer-Verlag, ISBN 978-3-211-75355-2.
- Flajolet, P .; Рауль, JC; Vuillemin, J. (1979), "Число регистров , необходимых для оценки арифметических выражений", Теоретическая информатика , 9 (1): 99-125, DOI : 10,1016 / 0304-3975 (79) 90009-4.
- Hibbard, Томас Н. (1962), «Некоторые комбинаторные свойства некоторых деревьев с приложениями к поиску и сортировке», журнал АКМ , 9 (1): 13-28, DOI : 10,1145 / 321105,321108.
- Кнут, Дональд Э. (1973), «6.2.2 Поиск двоичного дерева», Искусство компьютерного программирования , III , Аддисон-Уэсли, стр. 422–451..
- Кнут, Дональд Э. (2005), «Проект раздела 7.2.1.6: Создание всех деревьев» , Искусство компьютерного программирования , IV..
- Крушевски, Пол (1999), «Заметка о числе Хортона-Стрелера для случайных двоичных деревьев поиска», Письма об обработке информации , 69 (1): 47–51, DOI : 10.1016 / S0020-0190 (98) 00192-6.
- Махмуд, Хосам М. (1992), Эволюция случайных деревьев поиска , John Wiley & Sons.
- Мартинес, Конрадо; Roura, Salvador (1998), "Рандомизированные бинарные деревья поиска" , журнал ACM , 45 (2): 288–323, CiteSeerX 10.1.1.17.243 , doi : 10.1145 / 274787.274812.
- Pittel, В. (1985), "Асимптотическое рост класса случайных деревьев", Анналы вероятности , 13 (2): 414-427, DOI : 10,1214 / AOP / 1176993000.
- Рид, Брюс (2003), "Высота случайного двоичного дерева поиска", Журнал ACM , 50 (3): 306-332, DOI : 10,1145 / 765568,765571.
- Робсон, Дж. М. (1979), «Высота деревьев двоичного поиска», Австралийский компьютерный журнал , 11 : 151–153..
- Зайдель, Раймунд; Арагон, Сесилия Р. (1996), "рандомизированное Поиск Деревья" , Algorithmica , 16 (4/5): 464-497, DOI : 10.1007 / s004539900061.
Внешние ссылки
- Структуры открытых данных - Глава 7 - Случайные деревья двоичного поиска , Пат Морин