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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Сбалансированные деревья поиска, слайд №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 Последовательная вставка элементов дает дерево максимальной высоты:
Описание слайда:
Высота бинарного дерева Пусть бинарное дерево содержит элементы:10, 20, 30, 40, 50, 60, 70 Последовательная вставка элементов дает дерево максимальной высоты:

Слайд 8


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

Слайд 9


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

Слайд 10


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

Слайд 11


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

Слайд 12


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

Слайд 13


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

Слайд 14


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

Слайд 15


Пример 2-3 дерева
Описание слайда:
Пример 2-3 дерева

Слайд 16


Пример нарушения структуры 2-3 дерева
Описание слайда:
Пример нарушения структуры 2-3 дерева

Слайд 17


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

Слайд 18


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

Слайд 19


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

Слайд 20


Вставка элементов
Описание слайда:
Вставка элементов

Слайд 21


Вставка элементов
Описание слайда:
Вставка элементов

Слайд 22


Вставка элементов
Описание слайда:
Вставка элементов

Слайд 23


Вставка элементов
Описание слайда:
Вставка элементов

Слайд 24


Вставка элементов
Описание слайда:
Вставка элементов

Слайд 25


Вставка элементов
Описание слайда:
Вставка элементов

Слайд 26


Вставка элементов
Описание слайда:
Вставка элементов

Слайд 27


Удаление элементов
Описание слайда:
Удаление элементов

Слайд 28


Удаление элементов
Описание слайда:
Удаление элементов

Слайд 29


Удаление элементов
Описание слайда:
Удаление элементов

Слайд 30


Удаление элементов
Описание слайда:
Удаление элементов

Слайд 31


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

Слайд 32


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

Слайд 33


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

Слайд 34


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

Слайд 35


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

Слайд 36


Вставка элементов
Описание слайда:
Вставка элементов

Слайд 37


Вставка элементов
Описание слайда:
Вставка элементов

Слайд 38


Вставка элементов
Описание слайда:
Вставка элементов

Слайд 39


Вставка элементов
Описание слайда:
Вставка элементов

Слайд 40


Вставка элементов
Описание слайда:
Вставка элементов

Слайд 41


Вставка элементов
Описание слайда:
Вставка элементов

Слайд 42


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

Слайд 43


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

Слайд 44


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

Слайд 45


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

Слайд 46


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

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию