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

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

Сбалансированные деревья поиска, слайд №1

Сбалансированные деревья поиска, слайд №2

Сбалансированные деревья поиска, слайд №3

Сбалансированные деревья поиска, слайд №4

Сбалансированные деревья поиска, слайд №5

Сбалансированные деревья поиска, слайд №6

Сбалансированные деревья поиска, слайд №7

Сбалансированные деревья поиска, слайд №8

Сбалансированные деревья поиска, слайд №9

Сбалансированные деревья поиска, слайд №10

Сбалансированные деревья поиска, слайд №11

Сбалансированные деревья поиска, слайд №12

Сбалансированные деревья поиска, слайд №13

Сбалансированные деревья поиска, слайд №14

Сбалансированные деревья поиска, слайд №15

Сбалансированные деревья поиска, слайд №16

Сбалансированные деревья поиска, слайд №17

Сбалансированные деревья поиска, слайд №18

Сбалансированные деревья поиска, слайд №19

Сбалансированные деревья поиска, слайд №20

Сбалансированные деревья поиска, слайд №21

Сбалансированные деревья поиска, слайд №22

Сбалансированные деревья поиска, слайд №23

Сбалансированные деревья поиска, слайд №24

Сбалансированные деревья поиска, слайд №25

Сбалансированные деревья поиска, слайд №26

Сбалансированные деревья поиска, слайд №27

Сбалансированные деревья поиска, слайд №28

Сбалансированные деревья поиска, слайд №29

Сбалансированные деревья поиска, слайд №30

Сбалансированные деревья поиска, слайд №31

Сбалансированные деревья поиска, слайд №32

Сбалансированные деревья поиска, слайд №33

Сбалансированные деревья поиска, слайд №34

Сбалансированные деревья поиска, слайд №35

Сбалансированные деревья поиска, слайд №36

Сбалансированные деревья поиска, слайд №37

Сбалансированные деревья поиска, слайд №38

Сбалансированные деревья поиска, слайд №39

Сбалансированные деревья поиска, слайд №40

Сбалансированные деревья поиска, слайд №41

Сбалансированные деревья поиска, слайд №42

Сбалансированные деревья поиска, слайд №43

Сбалансированные деревья поиска, слайд №44

Сбалансированные деревья поиска, слайд №45

Сбалансированные деревья поиска, слайд №46

Содержание ▲

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

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

Слайд 1

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

Сбалансированные деревья поиска

Слайд 2

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

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

Слайд 3

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

Допустим задан текст «Сэр Исаак Ньютон по секрету признавался друзьям, что он знает, как гравитация ведет себя, но не знает почему»

Слайд 4

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

Текст в алфавитном порядке: ведет гравитация друзьям знает Исаак как не но Ньютон

Слайд 5

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

Построение дерева

Слайд 6

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

Дерево оптимальной структуры:

Слайд 7

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

Высота бинарного дерева Пусть бинарное дерево содержит элементы:10, 20, 30, 40, 50, 60, 70 Последовательная вставка элементов дает дерево максимальной высоты:

Слайд 8

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

Слайд 9

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

Слайд 10

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

Высота бинарного дерева Высота бинарного дерева зависит от порядка выполнения операций вставки и удаления элементов Высота бинарного дерева, состоящего из N элементов меняется от log2(N+1) до N

Слайд 11

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

Цель: Создание деревьев, не теряющих баланса при выполнении операций вставки и удаления Эффективность поиска в таких деревьев близка к максимальной

Слайд 12

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

2-3 дерево Каждый узел 2-3 дерева содержит одно или два значения Узлы дерева делятся на две категории: Листья Промежуточные узлы: Если промежуточный узел содержит одно значение, то он имеет два непустых поддерева (2-узел) Если он содержит два значения, то он имеет три непустых поддерева (3-узел) Все листья лежат на одном уровне

Слайд 13

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

2-3 дерево Принцип упорядоченности для 2-3 дерева: Для 2-узла – все значения, лежащие в левом поддереве, имеют значения, меньшие значений в узле, а значения, лежащие в правом поддереве – больше или равны значениям, хранящимся в узле

Слайд 14

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

Принцип упорядоченности для 2-3 дерева: Для 3-узла – упорядоченность означает следующее: Пусть А1 и А2– значения ключей элементов, хранящиеся в узле (А1 < А2), Т1 , Т2, Т3 – поддеревья этого узла. Тогда справедливо неравенство: K(Т1 )< А1

Слайд 15

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

Пример 2-3 дерева

Слайд 16

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

Пример нарушения структуры 2-3 дерева

Слайд 17

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

2-3 дерево 2-3 дерево не является бинарным Все листья 2-3 дерева находятся на одном и том же уровне Высота 2-3 дерева никогда не превышает минимальную высоту бинарного дерева, содержащего такое количество элементов

Слайд 18

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

Физическое представление 2-3 дерева

Слайд 19

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

Вставка элементов Вставка элементов осуществляется только в листья В случае, если после вставки элемента образуется переполненный узел, поступают следующим образом: Узел делится на два узла, при этом среднее значение поднимается на уровень выше и присоединяется к узлу на предыдущем уровне

Слайд 20

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

Вставка элементов

Слайд 21

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

Вставка элементов

Слайд 22

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

Вставка элементов

Слайд 23

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

Вставка элементов

Слайд 24

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

Вставка элементов

Слайд 25

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

Вставка элементов

Слайд 26

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

Вставка элементов

Слайд 27

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

Удаление элементов

Слайд 28

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

Удаление элементов

Слайд 29

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

Удаление элементов

Слайд 30

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

Удаление элементов

Слайд 31

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

Преимущества 2-3 дерева 2-3 дерево всегда сбалансировано Эффективность алгоритма поиска в таком дереве имеет порядок O(log2(N))

Слайд 32

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

2-3-4 деревья 2-3-4 дерево может содержать четырехместные узлы По сравнению с 2-3 деревом алгоритмы вставки и удаления элементов осуществляются за меньшее число шагов

Слайд 33

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

2-3-4 деревья 2-3-4 деревом высотой h называется дерево, которое пусто или имеет один из следующих видов:

Слайд 34

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

2-3-4 деревья Правила размещения данных

Слайд 35

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

Вставка элементов Четырехместный узел разделяется сразу после обнаружения, при этом один из его элементов перемещается в родительский узел

Слайд 36

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

Вставка элементов

Слайд 37

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

Вставка элементов

Слайд 38

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

Вставка элементов

Слайд 39

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

Вставка элементов

Слайд 40

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

Вставка элементов

Слайд 41

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

Вставка элементов

Слайд 42

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

Разделение четырехместных узлов при вставке Возможны случаи: Узел является корнем Узел имеет двухместого родителя Узел имеет трехместного родителя

Слайд 43

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

Удаление элементов Находим узел, содержащий данный элемент Заменяем элемент его симметричным преемником (самый левый узел в правом поддереве) Удаляем элемент из листа Замечание: в отличие от 2-3 дерева удаление можно осуществить за один проход дерева не перестраивая его

Слайд 44

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

Удаление элементов При проходе дерева во время поиска элемента, необходимо сразу преобразовать каждый двухместный узел в трех или четырехместный Замечание: преобразования производятся аналогично процедуре разделения, только в обратном порядке

Слайд 45

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

Заключение Достоинства 2-3 и 2-3-4 деревьев заключается в том, что они хорошо сохраняют баланс Алгоритмы вставки и удаления в 2-3-4 дерево выполняются за меньшее число шагов чем для 2-3 дерева

Слайд 46

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

Заключение Несмотря на то, что высота рассмотренных деревьев ниже, чем у бинарного дерева поиска, в алгоритмах поиска приходится делать большее число сравнений при посещении каждого узла Рассматривать деревья с числом дочерних узлов больше 4-х не имеет смысла, поскольку число сравнений будет очень велико. Их можно применять только если такие деревья реализованы на внешних носителях