Сортировка с помощью двоичного дерева

Сортировка с помощью двоичного дерева

Сортировка с помощью дерева осуществляется на основе бинарного дерева поиска.

Бинарное (двоичное) дерево поиска – это бинарное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):

  • оба поддерева – левое и правое, являются двоичными деревьями поиска;
  • у всех узлов левого поддерева произвольного узла X значения ключей данных меньше, чем значение ключа данных самого узла X;
  • у всех узлов правого поддерева произвольного узла X значения ключей данных не меньше, чем значение ключа данных узла X.

Данные в каждом узле должны обладать ключами, на которых определена операция сравнения меньше.

Для сортировки с помощью дерева исходная сортируемая последовательность представляется в виде структуры данных «дерево».

Например, исходная последовательность имеет вид:

4, 3, 5, 1, 7, 8, 6, 2

Корнем дерева будет начальный элемент последовательности. Далее все элементы, меньшие корневого, располагаются в левом поддереве, все элементы, большие корневого, располагаются в правом поддереве. Причем это правило должно соблюдаться на каждом уровне.

После того, как все элементы размещены в структуре «дерево», необходимо вывести их, используя инфиксную форму обхода.

Реализация сортировки с помощью дерева на C++

Результат выполнения

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

Для улучшения этой статьи желательно ? :

  • Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.
Алгоритмы сортировки
Теория
Алгоритмы

Wikimedia Foundation . 2010 .

Смотреть что такое "Сортировка с помощью двоичного дерева" в других словарях:

Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия

Двоичное дерево поиска — Тип Дерево Временная сложность в О символике В среднем В худшем случае Расход памяти O(n) O(n) Поиск O(h) O(n) Вставка O(h) O(n) Удаление O(h) O(n) где h высота дерева … Википедия

Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях… … Википедия

Программируемые алгоритмы — Служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавл … Википедия

Двоичная куча — У этого термина существуют и другие значения, см. Куча (значения). Имеется викиучебник по теме « … Википедия

Красно-чёрное дерево — Тип дерево поиска Изобретено в 1972 году Изобретено Рудольф Байер Временная сложность в О символике В среднем В худшем случае Расход памяти O(n) O(n) Поиск O(log n) O(log n) Вставка O(log n) O(log n) Удаление O(log n) O(log n) Красно чёрное… … Википедия

Standard Template Library — Стандартная библиотека шаблонов (STL) (англ. Standard Template Library) набор согласованных обобщенных алгоритмов, контейнеров, средств доступа к их содержимому и различных вспомогательных функций. Стандартная библиотека шаблонов до включения в… … Википедия

Стандартная библиотека шаблонов — Стандартная библиотека языка программирования C++ fstream iomanip ios iostream sstream Стандартная библиотека шаблонов … Википедия

Ссылка на основную публикацию
Сколько рублей получают ютуберы
Видеохостинг YouTube — не только развлекательная площадка, но и хороший источник дохода. Тысячи пользователей выкладывают ролики, пытаясь привлечь внимание аудитории....
Самый дорогой самсунг 2018
Samsung / Самсунг - южнокорейская компания, ведущий производитель смартфонов в мире. В первом квартале 2018 года доля Самсунг на мировом...
Самый лучший smart tv
Ежегодные обновления телевизионных технологий делают телевизоры уже больше, чем обычным экраном для демонстрации каналов. Растет популярность функции Smart TV, которая...
Сколько света мотает компьютер
Выбирая комплектующие для персонального компьютера (ПК) обычно обращают внимание на производительность и объем памяти, порой забывая о том, сколько же...
Adblock detector