Рандомизированные 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() < RAND_MAX/(h->N+l))

{ insertT(h, x);

return; }

if (x.key() < h->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-дерева

На этих рисунках показана вставка ключей ABCDEF G Н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-узлового дерева с вероятностью , а из М-узлового дерева — с вероятностью