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

Нажмите для полного просмотра!

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №1

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №2

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №3

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №4

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №5

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №6

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №7

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №8

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №9

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №10

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №11

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №12

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №13

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №14

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №15

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №16

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №17

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №18

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №19

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №20

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №21

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №22

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №23

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №24

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №25

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №26

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №27

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №28

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №29

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №30

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №31

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №32

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №33

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №34

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №35

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №36

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №37

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №38

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №39

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №40

Случайные бинарные деревья поиска. (Лекция 8.2), слайд №41

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Случайные бинарные деревья поиска. (Лекция 8.2). Доклад-сообщение содержит 41 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

Слайд 3

Описание слайда:

Начальное условие 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 в книге

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

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

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

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

Слайд 12

Описание слайда:

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

Слайд 13

Описание слайда:

Доказательство проведем по индукции. Доказательство проведем по индукции. Пусть в дереве 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, что и завершает доказательство.

Слайд 14

Описание слайда:

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

Слайд 15

Описание слайда:

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

Слайд 16

Описание слайда:

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

Слайд 17

Описание слайда:

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

Слайд 18

Описание слайда:

Слайд 19

Описание слайда:

Слайд 20

Описание слайда:

Слайд 21

Описание слайда:

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

Слайд 22

Описание слайда:

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

Слайд 23

Описание слайда:

Слайд 24

Описание слайда:

Слайд 25

Описание слайда:

Слайд 26

Описание слайда:

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

Слайд 27

Описание слайда:

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

Слайд 28

Описание слайда:

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

Слайд 29

Описание слайда:

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

Слайд 30

Описание слайда:

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

Слайд 31

Описание слайда:

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

Слайд 32

Описание слайда:

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

Слайд 33

Описание слайда:

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

Слайд 34

Описание слайда:

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

Слайд 35

Описание слайда:

Набросок процедуры рандомизированной вставки в БДП 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 number + 1)) {insInRoot (b, x); return;} if (x < b->info) randomInsert (b->lt, x); else randomInsert (b->rt, x); b ->number ++; }

Слайд 36

Описание слайда:

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

Слайд 37

Описание слайда:

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

Слайд 38

Описание слайда:

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

Слайд 39

Описание слайда:

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

Слайд 40

Описание слайда:

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