Динамические структуры данных (язык Си). Тема 6. Деревья - презентация, доклад, проект скачать

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

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №1

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №2

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №3

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №4

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №5

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №6

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №7

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №8

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №9

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №10

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №11

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №12

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №13

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №14

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №15

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №16

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №17

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №18

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №19

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №20

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №21

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №22

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №23

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №24

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №25

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №26

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №27

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №28

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №29

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №30

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №31

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №32

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №33

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №34

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №35

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №36

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №37

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №38

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №39

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №40

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №41

Динамические структуры данных (язык Си). Тема 6. Деревья, слайд №42

Содержание ▲

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

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

Слайд 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

Слайд 15

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

Добавление элемента Дано: дерево Т и пара (K,V). Задача: добавить пару (K, V) в дерево Т. Алгоритм: Если дерево пусто, заменить его на дерево с одним корневым узлом ((K,V), null, null) и остановиться. Иначе сравнить K с ключом корневого узла X. Если K>=X, рекурсивно добавить (K,V) в правое поддерево Т. Если K

Слайд 16

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

Удаление узла Дано: дерево Т с корнем n и ключом K. Задача: удалить из дерева Т узел с ключом K (если такой есть). Алгоритм: Если дерево T пусто, остановиться Иначе сравнить K с ключом X корневого узла n. Если K>X, рекурсивно удалить K из правого поддерева Т. Если K

Слайд 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 деревья сбалансированы, то есть каждое левое, правое, и центральное поддерево одинаковой высоты, и таким образом содержат равное (или почти равное) число данных.