Сортировка бинарным деревом :: Binary Tree Sort
Алгоритм
Из элементов массива формируется бинарное дерево поиска. Первый элемент - корень дерева, остальные добавляются по следующему методу. Начиная с корня дерева, элемент сравнивается с узлами. Если элемент меньше чем узел - то спускаемся по левой ветке, если не меньше - то по правой. Спустившись до конца, элемент сам становится узлом.
Построенное таким образом дерево можно легко обойти так, чтобы двигаться от узлов с меньшими значениями к узлам с большими значениями. При этом получаем все элементы в возрастающем порядке.
Характеристики алгоритма
| Название | Сортировка двоичным деревом (Tree Binary sort) | |
|---|---|---|
| Класс | Сортировки вставками | |
| Сложность по времени | Худшая | O(n2) |
| Средняя | O(n log n) | |
| Лучшая | O(n log n) | |
| Сложность по памяти | Дополнительная | Θ(n) |
Сортировка с помощью двоичного дерева