🗊Презентация Случайные бинарные деревья поиска. (Лекция 8.2)

Алгоритмы и структуры данных Лекция 8.2 Часть 2 0. дополнить – числа Каталана Случайные бинарные деревья поиска (БДП) (продолжение) Операции вращения в БДП Случайные БДП c рандомизацией

Начальное условие b0 = 1. Далее Начальное условие b0 = 1. Далее b1 = b0 b0 = 1, b2 = b0 b1 + b1 b0 = 2, b3 = b0 b2 + b1 b1 + b2 b0 = 5. b4 = b0 b3 + b1 b2 + b2 b1 + b3 b0 = 14. Оказывается [7, с. 393], что решением этого рекуррентного уравнения являются так называемые числа Каталана bk = Сk , где Сk =(2 k | k) / (k +1), а запись (n | m) обозначает биномиальный коэффициент (n | m) = n!/(m! (n – m)!). См. также 1.6.10 и 1.7.4 в книге

Тогда для чисел Каталана при больших значениях n справедливо Тогда для чисел Каталана при больших значениях n справедливо

Пусть во входном потоке находится последовательность элементов, Пусть во входном потоке находится последовательность элементов, по которой функция SearchAndInsert строит БДП: b = Create(); while (infile2 >> c) { SearchAndInsert (c, b); } БДП, построенное таким способом, называется случайным БДП

Случайные бинарные деревья поиска Входная последовательность (например, из файла):

Случайные бинарные деревья поиска Входная последовательность (например, из файла):

Случайные бинарные деревья поиска Входная последовательность (например, из файла):

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

Расширенное дерево строго бинарное. Такие деревья фактически уже рассматривались в задаче кодирования. Было показано, что в расширенном бинарном дереве из n внутренних узлов имеется ровно n + 1 внешний узел. Определим 2 понятия: длину внешних путей E(T) дерева T и длину внутренних путей I(T). Обозначим уровень узла b или длину пути от корня до него как l(b). При этом l(корень) = 0. Тогда длина внешних путей E(T) определяется как

Длина внутренних путей I(T) определяется аналогично как Длина внутренних путей I(T) определяется аналогично как

Доказательство проведем по индукции. Доказательство проведем по индукции. Пусть в дереве T из n внутренних узлов левое поддерево есть Tl , а число внутренних узлов в нем есть nl . Аналогично для правого поддерева – Tr, nr. Очевидно, nl + nr = n 1. Тогда E(T) = E(Tl) + E(Tr) + (n + 1), I(T) = I(Tl) + I(Tr) + (n  1). Рассмотрим разность D(T) = E(T)  I(T). Вычитая из рекуррентного соотношения для E(T) рекуррентное соотношение для I(T), получим D(T) = D(Tl) + D(Tr) + 2. Теперь покажем по индукции, что D(T) = 2n. Действительно, так как по индуктивному предположению D(Tl) = 2nl  и D(Tr) = 2nr, то D(T) = 2nl + 2nr + 2 = 2 (nl + nr + 1) = 2n, что и завершает доказательство.

Среднее расстояние до внешнего узла равно E(T) / (n + 1), Среднее расстояние до внешнего узла равно E(T) / (n + 1), а среднее расстояние до внутреннего узла равно I(T) / n. Обозначим для заданного БДП среднее число сравнений при удачном (т. е. закончившемся во внутреннем узле) поиске как C(n), а среднее число сравнений при неудачном (т. е. закончившемся во внешнем узле) поиске как C*(n). Если считать все исходы поиска равновероятными, то имеем

Поскольку E(T) = I(T) + 2n, то отсюда следует, что в среднем по дереву Поскольку E(T) = I(T) + 2n, то отсюда следует, что в среднем по дереву

Затраты на поиск в случайном БДП Число сравнений, среднее по всем n! перестановкам входных данных, т. е. по всем возможным случайным БДП. (Замечание. Вариант по всем структурно различным – иной результат) Уже есть одно соотношение (см. слайд 15) для двух неизвестных нам величин C(n) и C*(n). Это соотношение верно для заданного дерева в среднем по всем предъявлениям элемента для поиска.

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

При поиске в случайном БДП При поиске в случайном БДП среднее число сравнений всего лишь на 39 % больше, чем в идеально сбалансированном дереве. Это отражает тот факт (см. пример на прошлой лекции «abcd»), что среди случайных деревьев чаще встречаются хорошо сбалансированные (относительно «ровные») деревья, чем вырожденные.

Операции вращения в БДП В любом БДП горизонтальный порядок узлов фиксирован*, однако расположение узлов по уровням дерева зависит от способа его построения. Можно ли изменять относительное расположение узлов дерева по вертикали, сохраняя при этом инвариант дерева поиска? ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- * перечисление узлов БДП «слева направо», порождаемое ЛКП-обходом, дает упорядоченную последовательность.

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

Вставка в корень БДП Рекурсивный способ 1. Если вставляемый элемент больше корня БДП, то его место в правом поддереве. Поэтому сначала рекурсивно вставим этот элемент в качестве корня правого поддерева, а затем с помощью левого вращения поднимем его в корень дерева. 2. Если вставляемый элемент меньше корня БДП, то его место в левом поддереве. Поэтому сначала рекурсивно вставим этот элемент в качестве корня левого поддерева, а затем с помощью правого вращения поднимем его в корень дерева.

// вставка в корень void insInRoot (binSTree &b, base x) { if (b==NULL) { b = new node; if ( b != NULL) { b ->info = x; b ->count = 1; } else {cerr << "1 Memory not enough\n"; exit(1);} } else if (x < b->info) {insInRoot (b->lt, x); rotateR (b);} else if (x > b->info) {insInRoot (b->rt, x); rotateL (b);} else b->count++; }

Прокладка трассы от корня до нового листа 2. Подъём по трассе с вращениями

Пример вставки в корень

Здесь остановились 14 октября

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

Рандомизация в случайных БДП Идея модификации случайных БДП – чередование обычной вставки в дерево поиска и вставки в корень. Чередование происходит случайным (рандомизированным) образом с использованием компьютерного генератора псевдослучайных чисел (например, функции rand() в C++). Цель такого чередования – сохранить хорошие свойства случайного БДП в среднем и исключить (сделать маловероятным) появление «худшего случая» (поддеревьев большой высоты).

Рандомизированная вставка элемента x в БДП Пусть в дереве имеется n узлов. Считаем, что после добавления еще одного узла любой узел (теперь из n +1 узла) с равной вероятностью может быть корнем дерева. Пусть абстрактная булевская функция chance (k) выдает значение true с вероятностью 1/k. Тогда, если chance (n +1) = true, то осуществим вставку в корень, иначе рекурсивно используем рандомизированную вставку в левое или правое поддерево в зависимости от значения ключа x.

Набросок процедуры рандомизированной вставки в БДП void randomInsert (binSTree &b, base x) { if (b==NULL) { b = new node; if ( b != NULL) { b ->info = x; b ->count = 1; b ->number = 1; return; } else {cerr << "1 Memory not enough\n"; exit(1);} } if (chance(b ->number + 1)) {insInRoot (b, x); return;} if (x < b->info) randomInsert (b->lt, x); else randomInsert (b->rt, x); b ->number ++; }

Здесь остановились!!!

Здесь предполагалось, что Здесь предполагалось, что в каждом узле дерева в поле number хранится количество узлов поддерева, корнем которого является данный узел осуществляется «чистая» вставка, т. е. заранее известно, что элемент x в дереве отсутствует процедуры insInRoot, rotateR и rotateL изменены так, что они при своей работе правильно корректируют поле number в соответствующих узлах дерева

Выводы Оказывается [16], что случайные БДП с рандомизацией имеют в среднем примерно такие же характеристики, что и случайные БДП, однако в тех случаях, когда нарушается предположение о случайном порядке вставки элементов в БДП, т. е. когда характеристики случайного БДП значительно ухудшаются, деревья с рандомизацией сохраняют свои хорошие характеристики за счет «принудительной» рандомизации своей структуры.

Выводы Можно сказать, что в просто случайных БДП степень «случайности» регулируется порядком элементов входной последовательности узлов, а в случайных БДП с рандомизацией – генератором псевдослучайных чисел.

Примечание Термин «в среднем» имеет разный смысл в случайных БДП и в БДП с рандомизацией. Среднее по разным «ансамблям»: в случайных БДП – по разным входным последовательностям в БДП с рандомизацией – для одной входной последовательности по значениям Random

КОНЕЦ ЛЕКЦИИ КОНЕЦ ЛЕКЦИИ