Сортировка с помощью двоичного дерева
Сортировка с помощью двоичного дерева (сортировка двоичным деревом, сортировка деревом, древесная сортировка, сортировка с помощью бинарного дерева, англ. tree sort) - универсальный алгоритм сортировки, заключающийся в построении двоичного дерева поиска по ключам массива (списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей. Данная сортировка является оптимальной при получении данных путём непосредственного чтения с потока (например с файла, сокета или консоли).
Алгоритм
1. Построение двоичного дерева.
2. Сборка результирующего массива путём обхода узлов в необходимом порядке следования ключей.
Пример двоичного дерева
Реализация сортировки с помощью двоичного дерева на С++
06 | template <typename iterator="Iterator"> |
07 | void binary_tree_sort(Iterator begin, Iterator end) |
09 | std::multiset<typename std::iterator_traits="">::value_type> tree(begin, end); |
10 | std::copy(tree.begin(), tree.end(), begin); |
Вывод по сортировке с помощью двоичного дерева
Процедура добавления объекта в бинарное дерево имеет среднюю алгоритмическую сложность порядка O(log(n)). Соответственно, для n объектов сложность будет составлять O(n log(n)), что относит сортировку с помощью двоичного дерева к группе "быстрых сортировок". Однако, сложность добавления объекта в разбалансированное дерево может достигать O(n), что может привести к общей сложности порядка O(n2).
При физическом развёртывании древовидной структуры в памяти требуется не менее чем 4n ячеек дополнительной памяти (каждый узел должен содержать ссылки на элемент исходного массива, на родительский элемент, на левый и правый лист), однако, существуют способы уменьшить требуемую дополнительную память.