Tree Sort Сортировка двоичным деревом

Июль 30, 2022

Главная
Информатика
Tree Sort Сортировка двоичным деревом

Содержание

2. Что это? Сортировка с помощью двоичного дерева — универсальный алгоритм сортировки, заключающийся в построении двоичного дерева
3. Алгоритм 1. Построение двоичного дерева. 2. Сборка результирующего массива путём обхода узлов в необходимом порядке следования
4. При физическом развёртывании древовидной структуры в памяти требуется не менее чем 4n ячеек дополнительной памяти. Каждый
5. Эффективность Процедура добавления объекта в бинарное дерево имеет среднюю алгоритмическую сложность порядка O(log(n)). Однако, сложность добавления
6. В чем причина роста сложности алгоритма? Общее быстродействие метода O(nlogn). Почему? Поведение неестественно, устойчивости, вообще говоря,
7. Результаты работы алгоритма
8. График зависимости затраченного времени от размера массива.
9. График зависимости количества итераций от размера массива.
10. Применение TreeSort обычно применяют там, где – построенное дерево можно с успехом применить для таких задач;
12. Скачать презентацию

Слайд 2

Что это?
Сортировка с помощью двоичного дерева — универсальный алгоритм сортировки, заключающийся в построении двоичного

дерева поиска по ключам массива (списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей.

Слайд 3

Алгоритм
1. Построение двоичного дерева.
2. Сборка результирующего массива путём обхода узлов в

необходимом порядке следования ключей.

Слайд 4

При физическом развёртывании древовидной структуры в памяти требуется не менее чем

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

В чем недостаток алгоритма?

Слайд 5

Эффективность
Процедура добавления объекта в бинарное дерево имеет среднюю алгоритмическую сложность порядка

O(log(n)).
Однако, сложность добавления объекта в разбалансированное дерево может достигать O(n), что может привести к общей сложности порядка O(n²)!!!

Слайд 6

В чем причина роста сложности алгоритма?
Общее быстродействие метода O(nlogn). Почему?
Поведение

неестественно, устойчивости, вообще говоря, нет.
Требуется n операций на создание первоначального дерева, каждый по log n сравнений для выбора наименьшего и наибольшего.

Слайд 7

Результаты работы алгоритма

Слайд 8

График зависимости затраченного времени от размера массива.

Слайд 9

График зависимости количества итераций от размера массива.

Слайд 10

Применение
TreeSort обычно применяют там, где –
построенное дерево можно с успехом

применить для таких задач;
данные уже построены в 'дерево‘;
данные можно считывать непосредственно в дерево;
при потоковом вводе с консоли или из файла.

Tree Sort Сортировка двоичным деревом

Содержание

Что это?Сортировка с помощью двоичного дерева — универсальный алгоритм сортировки, заключающийся в построении двоичного

Алгоритм1. Построение двоичного дерева.2. Сборка результирующего массива путём обхода узлов в

При физическом развёртывании древовидной структуры в памяти требуется не менее чем

ЭффективностьПроцедура добавления объекта в бинарное дерево имеет среднюю алгоритмическую сложность порядка

В чем причина роста сложности алгоритма?Общее быстродействие метода O(nlogn). Почему? Поведение