Найти-добавить-удалить - презентация, доклад, проект скачать

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

Содержание ▲

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

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

Слайд 1

«Найти-добавить-удалить»
© 2010, 2014, 2015, Serge Kashkevich

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

Слайд 2

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

Постановка задачи Задано множество S мощностью M. Требуется предложить структуру данных для хранения элементов этого множества, пригодную для выполнения следующих операций: поиск элемента по значению добавление нового (возможно, уникального) элемента (после поиска) удаление элемента (после поиска) Ни одна из этих операций не должна выполняться с трудоёмкостью O(N), где N – количество хранимых элементов!

Слайд 3

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

Допустимые структуры данных Основные: массив бинарное поисковое дерево хэш-таблица Дополнительные (сбалансированные деревья): АВЛ – деревья сильно ветвящиеся деревья красно-чёрные деревья

Слайд 4

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

Использование массивов Если величина M невелика, можно завести булевский массив из M элементов, и обозначать в этом массиве наличие или отсутствие соответствующего элемента. Вариант такого подхода – битовый массив. Если уникальности элементов не требуется, массив должен быть числовым, и в нём обозначается количество хранимых элементов.

Слайд 5

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

Корневое дерево Корневое дерево определяется как конечное множество T одного или более узлов со следующими свойствами: существует один корень дерева T ; остальные узлы (за исключением корня) распределены среди непересекающихся множеств T1,...,Tm, и каждое из множеств является корневым деревом; деревья T1,...,Tm называются поддеревьями корня T

Слайд 6

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

Обход дерева Обход дерева – операция, связанная с посещением его вершин (под посещением понимается любая операция над вершиной дерева, не затрагивающая структуру дерева) При обходе каждая вершина должна быть посещена ровно один раз

Слайд 7

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

Прямой обход дерева посетить корень обойти все поддеревья в направлении слева направо

Слайд 8

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

Обратный обход дерева обойти все поддеревья в направлении слева направо посетить корень

Слайд 9

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

Бинарное дерево Бинарное (двоичное) дерево — ориентированное дерево, в котором число сыновей каждой вершины не превосходят 2. На бинарном дереве основаны следующие структуры данных: бинарное поисковое дерево двоичная куча красно-чёрное дерево АВЛ-дерево Фибоначчиева куча

Слайд 10

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

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

Слайд 11

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

Концевой обход бинарного дерева Обойти левое поддерево Посетить корень Обойти правое поддерево Если под посещением понимать вывод хранящегося в вершине значения, то концевым обходом БПД можно вывести отсортированное содержимое дерева.

Слайд 12

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

Поиск значения в БПД Пусть K – искомое значение, T – значение в корне дерева if (K==T) поиск завершен успешно else if (K<T) if (есть левый сын) выполнить поиск в левом поддереве else поиск завершен неудачно else if (есть правый сын) выполнить поиск в правом поддереве else поиск завершен неудачно

Слайд 13

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

Добавление значения в БПД если БПД пусто, создаем единственную вершину и делаем ее корнем; иначе выполняем поиск вершины с добавляемым значением; если поиск успешен, вставка невозможна; в противном случае добавляем новую вершину и делаем ее сыном (левым или правым) той вершины, на которой мы остановились в процессе поиска

Слайд 14

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

Удаление вершины из БПД Выполняем поиск удаляемой вершины. Если он завершился неудачно, завершаем работу. Если удаляемая вершина – лист, попросту удаляем её и ссылку на неё

Слайд 15

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

Удаление вершины из БПД (продолжение) Если удаляемая вершина A имеет одного сына, делаем этого сына сыном отца вершины A (или корнем, если удаляемая вершина – корень). При этом тип сына (левый или правый) может измениться

Слайд 16

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

Удаление вершины из БПД (окончание) Если удаляемая вершина A имеет двух сыновей, находим самую правую вершину в левом поддереве, корнем которого является A (или самую левую – в правом поддереве) – вершину B. Информацию из вершины B переносим в A, а саму вершину B удаляем, как было сказано ранее.

Слайд 17

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

Реализация БПД Реализация бинарного поискового дерева на C# приведена в примере BST.zip

Слайд 18

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

Хэширование Пусть количество хранимых элементов N много меньше M (мощности множества S). Введём хэш-функцию h : S → [1..N] и создадим массив из N элементов (хэш-таблицу). Суть хэширования состоит в следующем: помещаем элемент s из множества S в хэш-таблицу по индексу h(s). Ситуация, когда необходимо поместить элементы s1 и s2, но h(s1) = h(s2), называется коллизией. Для разрешения коллизий применяют: открытое хэширование закрытое хэширование

Слайд 19

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

Открытое хэширование Элементы, находящиеся в коллизии друг с другом, образуют список. Хэш-таблица хранит лишь информацию о начале списка. Пусть хэш-функция возвращает остаток от деления на 10:

Слайд 20

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

Примеры хэш-функций остаток от деления на N – объём хэш-таблицы (N лучше сделать простым, нежелательно делать N = 10k при хранении числовых данных) остаток от деления старших разрядов на N сумма цифр числа сумма квадратов цифр числа Все эти хэш-функции некачественны, поскольку при определённых условиях вероятность коллизий будет велика!

Слайд 21

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

Примеры хэш-функций (продолжение) Полиномиальная хэш-функция Пусть дана строка S = s1s2 ...sT, состоящая из цифр от 0 до 9. Тогда значение полиномиальной хеш-функции H(S, x, N) вычисляется следующим образом: Расчёт контрольной суммы (CRC)

Слайд 22

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

Неудобные операции для хэш-таблиц найти минимальный (максимальный) элемент; вывести все элементы, соблюдая упорядоченность; найти элемент, ближайший к искомому (или отстоящий от искомого не более чем на K); выполнить поиск по началу строки.

Слайд 23

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

Недостаток бинарных поисковых деревьев При создании дерева последовательностью вставок длины различных ветвей могут сильно различаться:

Слайд 24

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

Недостаток хэш-таблиц При неудачном выборе хэш-функции все вставленные элементы вступят в коллизию друг с другом Пусть хэш-функция возвращает остаток от деления на 10, а добавляются элементы с одинаковой последней цифрой:

Слайд 25

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

Подходы к решению проблемы Создать древовидные структуры, у которых длины ветвей будут не сильно отличаться друг от друга (сбалансированные деревья) При этом поддержание сбалансированности должно выполняться с трудоёмкостью не большей, чем O(log N). Варианты решения: АВЛ-деревья; сильно ветвящиеся деревья; красно-чёрные деревья

Слайд 26

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

ДВОИЧНАЯ КУЧА

Слайд 27

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

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

Слайд 28

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

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

Слайд 29

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

Пример двоичной кучи

Слайд 30

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

Добавление нового элемента в двоичную кучу

Слайд 31

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

Добавление нового элемента в двоичную кучу (продолжение)

Слайд 32

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

Добавление нового элемента в двоичную кучу (продолжение)

Слайд 33

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

Добавление нового элемента в двоичную кучу (окончание)

Слайд 34

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

Удаление минимального элемента из двоичной кучи

Слайд 35

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

Удаление минимального элемента из двоичной кучи (продолжение)

Слайд 36

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

Удаление минимального элемента из двоичной кучи (продолжение)

Слайд 37

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

Удаление минимального элемента из двоичной кучи (продолжение)

Слайд 38

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

Удаление минимального элемента из двоичной кучи (продолжение)

Слайд 39

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

Удаление минимального элемента из двоичной кучи (окончание)

Слайд 40

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

Реализация двоичной кучи в виде массива Создаём одномерный массив из N элементов. Значение корня помещается в массив по индексу 0, а значения сыновей вершины, хранящейся по индексу k, помещаются по индексам 2k+1 и 2k+2. Это соответствует обходу дерева по уровням.