Сортування двійковим (бінарним) деревом (сортування з допомогою двійкового дерева, англ. tree sort) — алгоритм сортування, що полягає в побудові двійкового дерева пошуку за ключами масиву, а далі, в створенні результуючого масиву впорядокованих елементів виконуючи обхід дерева.
Клас | Алгоритм сортування |
---|---|
Структура даних | Масив |
Найгірша швидкодія | |
Найкраща швидкодія | |
Середня швидкодія | |
Просторова складність у найгіршому випадку |
Алгоритм
- Отримати елементи вхідного масиву.
- Побудувати двійкове дерево вставляючи елементи вхідного масиву в двійкове дерево пошуку.
- Виконати обхід дерева, щоб отримати результуючий масив з впорядкованими елементами.
Аналіз
Швидкодія
Процедура додавання об'єкта в збалансоване дерево має середню алгоритмічну складність . Відповідно, для n об'єктів складність буде дорівнювати .
Однак, складність додавання об'єкта в незбалансоване дерево може досягати , що може збільшити загальну алгоритмічну складність до .
Реалізація
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; }
Переваги та недоліки алгоритму
Переваги
- Основною перевагою алгоритму сортування двійковим деревом є те, що ми легко можемо робити зміни, як у зв'язаному списку.
- Сортування двійковим деревом відбувається так само швидко, як алгоритм швидкого сортування.
Недоліки
- Найгірший випадок сортування — коли всі елементи масиву вже відсортовані.
- У гіршому випадку, час роботи алгоритму дорівнює .
Див. також
Джерела
- Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (2nd ed.) The MIT Press.
- Tree sort algorithm
- Big-O Algorithm Complexity
Посилання
- Tree sort in C++
- GeeksforGeeks: Tree sort
- Алгоритми і Структури
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Sortuvannya dvijkovim binarnim derevom sortuvannya z dopomogoyu dvijkovogo dereva angl tree sort algoritm sortuvannya sho polyagaye v pobudovi dvijkovogo dereva poshuku za klyuchami masivu a dali v stvorenni rezultuyuchogo masivu vporyadokovanih elementiv vikonuyuchi obhid dereva Sortuvannya dvijkovim derevomKlasAlgoritm sortuvannyaStruktura danihMasivNajgirsha shvidkodiyaO n2 displaystyle O n 2 Najkrasha shvidkodiyaW nlog n displaystyle Omega n log n Serednya shvidkodiya8 nlog n displaystyle Theta n log n Prostorova skladnist u najgirshomu vipadkuO n displaystyle O n AlgoritmOtrimati elementi vhidnogo masivu Pobuduvati dvijkove derevo vstavlyayuchi elementi vhidnogo masivu v dvijkove derevo poshuku Vikonati obhid dereva shob otrimati rezultuyuchij masiv z vporyadkovanimi elementami AnalizShvidkodiya Procedura dodavannya ob yekta v zbalansovane derevo maye serednyu algoritmichnu skladnist O log n displaystyle O log n Vidpovidno dlya n ob yektiv skladnist bude dorivnyuvati O nlog n displaystyle O n log n Odnak skladnist dodavannya ob yekta v nezbalansovane derevo mozhe dosyagati O n displaystyle O n sho mozhe zbilshiti zagalnu algoritmichnu skladnist do O n2 displaystyle O n 2 RealizaciyaC include lt iostream gt include lt vector gt using namespace std struct Node int data struct Node left right struct Node newnode int key struct Node temp new Node temp gt data key temp gt left NULL temp gt right NULL return temp Node insert Node node int key if node NULL return newnode key if key lt node gt data node gt left insert node gt left key else node gt right insert node gt right key return node void store Node root int a int amp i if root NULL store root gt left a i a i root gt data store root gt right a i void TreeSort vector lt int gt amp a struct Node root NULL root insert root a 0 for size t i 1 i lt a size i insert root a i int i 0 store root a data i int main vector lt int gt a 1 6 8 3 10 2 12 TreeSort a cout lt lt The sorted array is n for size t i 0 i lt a size i cout lt lt a i lt lt cout lt lt endl return 0 Perevagi ta nedoliki algoritmuPerevagi Osnovnoyu perevagoyu algoritmu sortuvannya dvijkovim derevom ye te sho mi legko mozhemo robiti zmini yak u zv yazanomu spisku Sortuvannya dvijkovim derevom vidbuvayetsya tak samo shvidko yak algoritm shvidkogo sortuvannya Nedoliki Najgirshij vipadok sortuvannya koli vsi elementi masivu vzhe vidsortovani U girshomu vipadku chas roboti algoritmu dorivnyuye O n2 displaystyle O n 2 Div takozhAlgoritm sortuvannya Dvijkove derevo poshuku Zbalansovane derevoDzherelaThomas 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 ComplexityPosilannyaTree sort in C GeeksforGeeks Tree sort Algoritmi i Strukturi