Рандомизированные bst-деревья

Чтобы проанализировать затраты для случая усредненной производительности при работе с BST-деревьями, было сделано допущение, что элементы вставляются в случайном порядке. Применительно к алгоритму с использованием BST-дерева главное следствие этого допущения заключается в том, что каждый узел дерева с равной вероятностью может оказаться корневым, причем это же справедливо и по отношению к поддеревьям. Как это ни удивительно, случайность можно включить в алгоритм, чтобы это свойство сохранялось без каких- либо допущений относительно порядка вставки элементов. Идея весьма проста: при вставке нового узла в дерево, состоящее из Nузлов, вероятность появления нового узла в корне должна быть равна 1/(N + 1), поэтому мы просто принимаем рандомизованное решение использовать вставку в корень с этой вероятностью. В противном случае мы рекурсивно используем метод для вставки новой записи в левое поддерево, если ключ записи меньше ключа в корне, и в правое поддерево — если он больше[3].

Если использовать нерекурсивный подход, выполнение рандомизованной вставки эквивалентно выполнению стандартного поиска ключа с принятием на каждом шаге рандомизованного решения о том, продолжить ли поиск или прервать его и выполнить вставку в корень. Таким образом, новый узел может быть вставлен в любое место на пути поиска. Это простое вероятностное объединение стандартного алгоритма BST-дерева с методом вставки в корень обеспечивает гарантированную в смысле вероятности производительность.

Лемма 21:Построение рандомизованного BST-дерева эквивалентно построению стандартного BST-дерева из случайно переставленных в исходном состоянии ключей. Для конструирования рандомизованного BST-дерева из N элементов используется около 2NlgN сравнений (независимо от порядка вставки элементов), а для выполнения поиска в таком дереве требуется приблизительно 2 lgN сравнений.

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

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

Программа 25: Вставка в рандомизованное BST-дерево.

В рандомизованном BST-дереве каждый из узлов с равной вероятностью является корнем; поэтому, помещая новый узел в корень дерева размера N с вероятностью 1/(N + 1), мы получаем рандомизованное дерево.

private: void insertR(links h. Item x)

{if (h == 0)

{ h = new node(x);

return; }

if (rand( ) N+l))

{ insertT(h, x);

return; }

if (x.key() item.key()) insertR(h-l, x);

else insertR(h-r, x);

h-N++;

}

public: void insert(Item x)

{ insertR(head, x) ;

}

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

Лемма 22: Вероятность того, что затраты на создание рандомизованного BST-дерева превышают усредненные затраты в ? раз, меньше в .

Этот результат совпадает с результатами, полученными из общего решения вероятностных соотношений, которые были разработаны Карпом (Karp) в 1995

Рисунок.37. Построение рандомизованного BST-дерева

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

Например, для построения рандомизованного BST-дерева, состоящего из 100000 узлов, требуется около 2.3 миллиона сравнений, но вероятность того, что количество сравнений превысит 23 миллиона, значительно меньше 0.01 процента. Подобная гарантия производительности более чем удовлетворяет практические требования, предъявляемые к обработке реальных наборов данных такого размера. Упомянутую гарантию нельзя обеспечить при использовании стандартного BST-дерева для выполнения такой задачи: например, придется столкнуться с проблемами снижения производительности, если данные в значительной степени упорядочены, что маловероятно для случайных данных, но по множеству причин достаточно часто имеет место при работе с реальными данными.

По тем же соображениям, утверждение, справедливо и по отношению к времени выполнения быстрой сортировки. Но в данном случае это еще более важно, поскольку отсюда следует, что затраты на поиск в дереве близки к усредненным. Независимо от дополнительных затрат на построение деревьев, стандартную реализацию BST-дерева можно использовать для выполнения операций search при затратах, которые зависят только от формы деревьев, при отсутствии вообще каких-либо дополнительных затрат на балансировку. Это свойство важно в типовых приложениях, в которых операции search гораздо более многочисленны, нежели любые другие. Например, описанное в предыдущем абзаце BST-дерево, состоящее из 100000 узлов, могло бы содержать телефонный справочник и использоваться для выполнения миллионов поисков. Можно быть почти уверенным, что каждый поиск потребует затрат, которые отличаются от усредненных затрат, равных приблизительно 23 сравнениям, лишь небольшим постоянным коэффициентом. Поэтому на практике можно не беспокоиться, что для большого количества поисков потребуется количество сравнений, приближающееся к 100000, в то время как при использовании стандартных BST-деревьев это было весьма актуально.

Рисунок.38. Большое рандомизованное BST-дерево.

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

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

Еще один потенциальный недостаток рандомизованных BST-деревьев — необходимость наличия в каждом узле поля количества узлов поддерева данного узла. Дополнительный объем памяти, требуемый для поддержки этого поля, может оказаться чрезмерной платой для больших деревьев. С другой стороны, это поле может требоваться по ряду других причин — например, для поддержки операции select или для обеспечения проверки целостности структуры данных. В подобных случаях рандомизованные BST-деревья не требуют никаких дополнительных затрат памяти и их использование представляется весьма привлекательным.

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

Для объединениядерева, состоящего из N узлов, с деревом, состоящим из М узлов, используется базовый метод, за исключением принятия рандомизованного решения о выборе корня исходя из того, что корень объединенного дерева должен выбираться из A-узлового дерева с вероятностью , а из М-узлового дерева — с вероятностью

Bushman Prank: The best reactions ever 😂😍🍀


Похожие статьи.

Понравилась статья? Поделиться с друзьями: