Сортування двійковим деревом — Вікіпедія

Сортування двійковим деревом
Клас	Алгоритм сортування
Структура даних	Масив
Найгірша швидкодія
Найкраща швидкодія
Середня швидкодія
Просторова складність у найгіршому випадку

Сортування двійковим (бінарним) деревом (сортування з допомогою двійкового дерева, англ. tree sort) — алгоритм сортування, що полягає в побудові двійкового дерева пошуку за ключами масиву, а далі, в створенні результуючого масиву впорядокованих елементів виконуючи обхід дерева.

Алгоритм[ред. | ред. код]

Отримати елементи вхідного масиву.
Побудувати двійкове дерево вставляючи елементи вхідного масиву в двійкове дерево пошуку.
Виконати обхід дерева, щоб отримати результуючий масив з впорядкованими елементами.

Аналіз[ред. | ред. код]

Швидкодія[ред. | ред. код]

Процедура додавання об'єкта в збалансоване дерево має середню алгоритмічну складність $O(\log n)$ . Відповідно, для n об'єктів складність буде дорівнювати $O(n\log n)$ .

Однак, складність додавання об'єкта в незбалансоване дерево може досягати $O(n)$ , що може збільшити загальну алгоритмічну складність до $O(n^{2})$ .

Реалізація[ред. | ред. код]

C++[ред. | ред. код]

#include <iostream> #include <vector>  using namespace std;  struct Node {     int data;     struct Node *left, *right; };  struct Node *newnode(int key) {     struct Node *temp = new Node;     temp->data = key;     temp->left = NULL;     temp->right = NULL;     return temp; }  Node* insert(Node *node, int key) {     if (node == NULL) {         return newnode(key);     }     if (key < node->data) {         node->left = insert(node->left, key);     }     else {         node->right = insert(node->right, key);     }     return node; }  void store(Node *root, int a[], int &i) {     if (root != NULL)     {         store(root->left, a, i);         a[i++] = root->data;         store(root->right, a, i);     } }  void TreeSort(vector<int>& a) {     struct Node *root = NULL;     root = insert(root, a[0]);     for (size_t i = 1; i < a.size(); ++i) {         insert(root, a[i]);     }     int i = 0;     store(root, a.data(), i); }  int main() {      vector<int> a{1,6,8,3,10,2,12};     TreeSort(a);      cout << "The sorted array is:\n";     for (size_t i = 0; i < a.size(); ++i) {         cout << a[i] << " ";     }     cout << endl;          return 0; }

Переваги та недоліки алгоритму[ред. | ред. код]

Переваги[ред. | ред. код]

Основною перевагою алгоритму сортування двійковим деревом є те, що ми легко можемо робити зміни, як у зв'язаному списку.
Сортування двійковим деревом відбувається так само швидко, як алгоритм швидкого сортування.

Недоліки[ред. | ред. код]

Найгірший випадок сортування — коли всі елементи масиву вже відсортовані.
У гіршому випадку, час роботи алгоритму дорівнює $O(n^{2})$ .

Див. також[ред. | ред. код]

Джерела[ред. | ред. код]

Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (2nd ed.) The MIT Press. ISBN 0-07-013151-1
Tree sort algorithm
Big-O Algorithm Complexity