Рубрики

Сортировка деревьев

Tree sort — это алгоритм сортировки, основанный на структуре данных Binary Search Tree . Сначала он создает двоичное дерево поиска из элементов входного списка или массива, а затем выполняет упорядоченный обход созданного двоичного дерева поиска, чтобы получить элементы в отсортированном порядке.

Алгоритм:

Step 1: Take the elements input in an array.
Step 2: Create a Binary search tree by inserting data items from the array into the
        binary search tree.
Step 3: Perform in-order traversal on the tree to get the elements in sorted order.

C ++

// C ++ программа для реализации сортировки по дереву
#include<bits/stdc++.h>

  

using namespace std;

  

struct Node

{

    int key;

    struct Node *left, *right;

};

  
// Вспомогательная функция для создания нового узла BST

struct Node *newNode(int item)

{

    struct Node *temp = new Node;

    temp->key = item;

    temp->left = temp->right = NULL;

    return temp;

}

  
// Сохраняем обход InSoder BST
// в обр []

void storeSorted(Node *root, int arr[], int &i)

{

    if (root != NULL)

    {

        storeSorted(root->left, arr, i);

        arr[i++] = root->key;

        storeSorted(root->right, arr, i);

    }

}

  
/ * Утилита для вставки нового

   Узел с данным ключом в BST * /

Node* insert(Node* node, int key)

{

    / * Если дерево пустое, вернуть новый узел * /

    if (node == NULL) return newNode(key);

  

    / * В противном случае вернемся вниз по дереву * /

    if (key < node->key)

        node->left  = insert(node->left, key);

    else if (key > node->key)

        node->right = insert(node->right, key);

  

    / * вернуть (неизмененный) указатель узла * /

    return node;

}

  
// Эта функция сортирует arr [0..n-1], используя сортировку деревьев

void treeSort(int arr[], int n)

{

    struct Node *root = NULL;

  

    // Построить BST

    root = insert(root, arr[0]);

    for (int i=1; i<n; i++)

        insert(root, arr[i]);

  

    // Сохраняем обход InSoder BST

    // в обр []

    int i = 0;

    storeSorted(root, arr, i);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    // создать входной массив

    int arr[] = {5, 4, 7, 2, 11};

    int n = sizeof(arr)/sizeof(arr[0]);

  

    treeSort(arr, n);

  

        for (int i=0; i<n; i++)

       cout << arr[i] << " ";

  

    return 0;

}

Джава

// Java программа для
// реализовать сортировку деревьев

class GFG 

{

  

    // Класс, содержащий left и

    // правый потомок текущего

    // узел и значение ключа

    class Node 

    {

        int key;

        Node left, right;

  

        public Node(int item) 

        {

            key = item;

            left = right = null;

        }

    }

  

    // Корень BST

    Node root;

  

    // Конструктор

    GFG() 

    

        root = null

    }

  

    // Этот метод в основном

    // вызывает insertRec ()

    void insert(int key)

    {

        root = insertRec(root, key);

    }

      

    / * Рекурсивная функция для

    вставить новый ключ в BST * /

    Node insertRec(Node root, int key) 

    {

  

        / * Если дерево пусто,

        вернуть новый узел * /

        if (root == null

        {

            root = new Node(key);

            return root;

        }

  

        / * В противном случае повторить

        вниз по дереву * /

        if (key < root.key)

            root.left = insertRec(root.left, key);

        else if (key > root.key)

            root.right = insertRec(root.right, key);

  

        / * вернуть рут * /

        return root;

    }

      

    // Функция для выполнения

    // обход порядка BST

    void inorderRec(Node root) 

    {

        if (root != null

        {

            inorderRec(root.left);

            System.out.print(root.key + " ");

            inorderRec(root.right);

        }

    }

    void treeins(int arr[])

    {

        for(int i = 0; i < arr.length; i++)

        {

            insert(arr[i]);

        }

          

    }

  

    // Код драйвера

    public static void main(String[] args) 

    {

        GFG tree = new GFG();

        int arr[] = {5, 4, 7, 2, 11};

        tree.treeins(arr);

        tree.inorderRec(tree.root);

    }

}

  
// Этот код добавлен
// Вибин М


Выход:

2 4 5 7 11

Сложность среднего регистра времени: O (n log n) Добавление одного элемента в дерево бинарного поиска в среднем занимает O (log n) времени. Следовательно, добавление n элементов займет O (n log n) времени.

В худшем случае сложность времени: O (n 2 ). Наихудшая временная сложность сортировки деревьев может быть улучшена с помощью самобалансирующегося бинарного дерева поиска, такого как Red Black Tree, AVL Tree. Использование самобалансирующегося двоичного дерева для сортировки массива в худшем случае займет O (n log n) времени.

Вспомогательное пространство: O (n)

Ссылки:
https://en.wikipedia.org/wiki/Tree_sort

Эта статья предоставлена Суровым Агарвалом . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Сортировка деревьев

0.00 (0%) 0 votes