Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
42 слайда
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
1.58 MB
Просмотров:
72
Скачиваний:
1
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Динамические структуры данных
Деревья
№2 слайд
№3 слайд
№4 слайд
№5 слайд
№6 слайд
№7 слайд
Содержание слайда: Двоичные деревья
Многие полезные структуры данных основаны на двоичном дереве:
Двоичное дерево поиска
Двоичная куча
АВЛ-дерево
Красно-чёрное дерево
Матричное дерево
Дерево Фибоначчи
Суффиксное дерево
№8 слайд
№9 слайд
№10 слайд
№11 слайд
Содержание слайда: Несбалансированные двоичные деревья поиска (unbalanced)
Это такие деревья, высота правого и левого поддеревьев которых отличаются более, чем на 1.
Дерево двоичного поиска становится несбалансированным, когда в него постоянно добавляются элементы большего или меньшего размера
№12 слайд
Содержание слайда: Неполные двоичные деревья поиска (incomplete)
Каждый узел дерева двоичного поиска должен содержать не более 2 детей.
Но он может иметь 1 ребенка или не иметь детей.
Если в дереве есть такие хотя бы один такой узел, дерево называют неполным.
№13 слайд
Содержание слайда: Основные операции в двоичном дереве поиска
Базовый интерфейс двоичного дерева поиска состоит из трех операций:
Поиск узла, в котором хранится пара (key, value) с key = K.
Добавление в дерево пары (key, value) = (K, V).
Удаление узла, в котором хранится пара (key, value) с key = K.
№14 слайд
Содержание слайда: Поиск элемента
Дано: дерево Т и ключ K.
Задача: проверить, есть ли узел с ключом K в дереве Т, и если да, то вернуть ссылку на этот узел.
Алгоритм:
Если дерево пусто, сообщить, что узел не найден, и остановиться.
Иначе сравнить K со значением ключа корневого узла X.
Если K=X, выдать ссылку на этот узел и остановиться.
Если K>X, рекурсивно искать ключ K в правом поддереве Т.
Если K<X, рекурсивно искать ключ K в левом поддереве Т.
№15 слайд
Содержание слайда: Добавление элемента
Дано: дерево Т и пара (K,V).
Задача: добавить пару (K, V) в дерево Т.
Алгоритм:
Если дерево пусто, заменить его на дерево с одним корневым узлом ((K,V), null, null) и остановиться.
Иначе сравнить K с ключом корневого узла X.
Если K>=X, рекурсивно добавить (K,V) в правое поддерево Т.
Если K<X, рекурсивно добавить (K,V) в левое поддерево Т.
№16 слайд
Содержание слайда: Удаление узла
Дано: дерево Т с корнем n и ключом K.
Задача: удалить из дерева Т узел с ключом K (если такой есть).
Алгоритм:
Если дерево T пусто, остановиться
Иначе сравнить K с ключом X корневого узла n.
Если K>X, рекурсивно удалить K из правого поддерева Т.
Если K<X, рекурсивно удалить K из левого поддерева Т.
Если K=X, то необходимо рассмотреть три случая.
Если обоих детей нет, то удаляем текущий узел и обнуляем ссылку на него у родительского узла.
Если одного из детей нет, то значения полей второго ребёнка m ставим вместо соответствующих значений корневого узла, затирая его старые значения, и освобождаем память, занимаемую узлом m.
Если оба ребёнка присутствуют, то
найдём узел m, являющийся самым левым узлом правого поддерева с корневым узлом Right(n);
присвоим ссылке Left(m) значение Left(n)
ссылку на узел n в узле Parent(n) заменить на Right(n);
освободим память, занимаемую узлом n (на него теперь никто не указывает).
№17 слайд
№18 слайд
№19 слайд
№20 слайд
№21 слайд
Содержание слайда: Двоичная куча
№22 слайд
Содержание слайда: Двоичная куча
Двоичная куча (пирамида) — такое двоичное дерево, для которого выполнены три условия:
Значение в любой вершине больше, чем значения её потомков.
Каждый лист имеет глубину (расстояние до корня) либо d либо d-1. Иными словами, если назвать слоем совокупность листьев, находящемся на определённой глубине, то все слои, кроме, может быть, последнего, заполнены полностью.
Последний слой заполняется слева направо.
Существуют также кучи, где значение в любой вершине, наоборот, меньше, чем значения её потомков. Такие кучи называются min-heap, а кучи, описанные выше — max-heap.
№23 слайд
Содержание слайда: Кучи
Max-heap
Значение в любой вершине больше, чем значения ее потомков
№24 слайд
Содержание слайда: Красно-чёрное дерево
№25 слайд
Содержание слайда: Красно-чёрное дерево
Красно-чёрное дерево (Red-Black-Tree, RB-Tree) — это одно из самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и быстро выполняющее основные операции дерева поиска: добавление, удаление и поиск узла.
Сбалансированность достигается за счет введения дополнительного атрибута узла дерева — «цвет». Этот атрибут может принимать одно из двух возможных значений — «чёрный» или «красный».
Красно-чёрное дерево обладает следующими свойствами:
Все листья черные.
Все потомки красных узлов черные (т.е. запрещена ситуация с двумя красными узлами подряд).
На всех ветвях дерева, ведущих от его корня к листьям, число чёрных узлов одинаково. Это число называется чёрной высотой дерева.
При этом для удобства листьями красно-чёрного дерева считаются фиктивные «нулевые» узлы, не содержащие данных.
№26 слайд
Содержание слайда: АВЛ-дерево
АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962
№27 слайд
Содержание слайда: B-дерево
B-дерево (по-русски произносится как Б-дерево) — структура данных, дерево поиска. С точки зрения внешнего логического представления, сбалансированное, сильно ветвистое дерево во внешней памяти.
Сбалансированность означает, что длина пути от корня дерева к любому его листу одна и та же.
Ветвистость дерева — это свойство каждого узла дерева ссылаться на большое число узлов-потомков.
С точки зрения физической организации B-дерево представляется как мультисписочная структура страниц внешней памяти, то есть каждому узлу дерева соответствует блок внешней памяти (страница). Внутренние и листовые страницы обычно имеют разную структуру.
№28 слайд
№29 слайд
Содержание слайда: 2-3-дерево
2-3 дерево — структура данных являющаяся B-деревом степени 1, страницы которого могут содержать только 2-вершины (вершины с одним полем и 2-мя детьми) и 3-вершины (вершины с 2-мя полями и 3-мя детьми).
Листовые вершины являются исключением — у них нет детей (но может быть одно или два поля). 2-3 деревья сбалансированы, то есть каждое левое, правое, и центральное поддерево одинаковой высоты, и таким образом содержат равное (или почти равное) число данных.
№30 слайд
№31 слайд
№32 слайд
№33 слайд
№34 слайд
№35 слайд
№36 слайд
№37 слайд
№38 слайд
№39 слайд
№40 слайд
№41 слайд
№42 слайд