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

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

Клас	Алгоритм сортування
Структура даних	Масив
Найгірша швидкодія	$O(n^{2})$
Найкраща швидкодія	$\Omega (n\log n)$
Середня швидкодія	$\Theta (n\log n)$
Просторова складність у найгіршому випадку	$O(n)$

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

Алгоритм

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

Аналіз

Швидкодія

Процедура додавання об'єкта в збалансоване дерево має середню алгоритмічну складність $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

Посилання

• Tree sort in C++
• GeeksforGeeks: Tree sort
• Алгоритми і Структури