Сортування дерева
Сорт дерева це алгоритм сортування, який базується на Двійкове дерево пошуку структура даних. Спочатку створюється двійкове дерево пошуку з елементів вхідного списку або масиву, а потім виконується порядковий обхід створеного бінарного дерева пошуку, щоб отримати елементи в порядку сортування.
Алгоритм:
крок 1: Візьміть елементи, введені в масив.Крок 2: Створіть бінарне дерево пошуку, вставивши елементи даних із масиву в двійкове дерево пошуку .крок 3: Виконайте порядковий обхід дерева, щоб отримати елементи в порядку сортування.Застосування дерева:
- Його найпоширенішим використанням є редагування елементів онлайн: після кожного встановлення набір об’єктів, які ви бачили до цього моменту, доступний у структурованій програмі.
- Якщо ви використовуєте splay-дерево як бінарне дерево пошуку, отриманий алгоритм (званий splaysort) має додаткову властивість, що він є адаптивним сортуванням, що означає, що його робочий час є швидшим, ніж O (n log n) для віртуальних вхідних даних.
Нижче наведено реалізацію вищезазначеного підходу:
C++Java// C++ program to implement Tree Sort #includeusing namespace std ; struct Node { int key ; struct Node * left * right ; }; // A utility function to create a new BST Node struct Node * newNode ( int item ) { struct Node * temp = new Node ; temp -> key = item ; temp -> left = temp -> right = NULL ; return temp ; } // Stores inorder traversal of the BST // in arr[] 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 ); } } /* A utility function to insert a new Node with given key in BST */ Node * insert ( Node * node int key ) { /* If the tree is empty return a new Node */ if ( node == NULL ) return newNode ( key ); /* Otherwise recur down the tree */ if ( key < node -> key ) node -> left = insert ( node -> left key ); else if ( key > node -> key ) node -> right = insert ( node -> right key ); /* return the (unchanged) Node pointer */ return node ; } // This function sorts arr[0..n-1] using Tree Sort void treeSort ( int arr [] int n ) { struct Node * root = NULL ; // Construct the BST root = insert ( root arr [ 0 ]); for ( int i = 1 ; i < n ; i ++ ) root = insert ( root arr [ i ]); // Store inorder traversal of the BST // in arr[] int i = 0 ; storeSorted ( root arr i ); } // Driver Program to test above functions int main () { //create input array 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 ; } Python3// Java program to // implement Tree Sort class GFG { // Class containing left and // right child of current // node and key value class Node { int key ; Node left right ; public Node ( int item ) { key = item ; left = right = null ; } } // Root of BST Node root ; // Constructor GFG () { root = null ; } // This method mainly // calls insertRec() void insert ( int key ) { root = insertRec ( root key ); } /* A recursive function to insert a new key in BST */ Node insertRec ( Node root int key ) { /* If the tree is empty return a new node */ if ( root == null ) { root = new Node ( key ); return root ; } /* Otherwise recur down the tree */ if ( key < root . key ) root . left = insertRec ( root . left key ); else if ( key > root . key ) root . right = insertRec ( root . right key ); /* return the root */ return root ; } // A function to do // inorder traversal of 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 ] ); } } // Driver Code public static void main ( String [] args ) { GFG tree = new GFG (); int arr [] = { 5 4 7 2 11 }; tree . treeins ( arr ); tree . inorderRec ( tree . root ); } } // This code is contributed // by Vibin MC## Python3 program to # implement Tree Sort # Class containing left and # right child of current # node and key value class Node : def __init__ ( self item = 0 ): self . key = item self . left self . right = None None # Root of BST root = Node () root = None # This method mainly # calls insertRec() def insert ( key ): global root root = insertRec ( root key ) # A recursive function to # insert a new key in BST def insertRec ( root key ): # If the tree is empty # return a new node if ( root == None ): root = Node ( key ) return root # Otherwise recur # down the tree if ( key < root . key ): root . left = insertRec ( root . left key ) elif ( key > root . key ): root . right = insertRec ( root . right key ) # return the root return root # A function to do # inorder traversal of BST def inorderRec ( root ): if ( root != None ): inorderRec ( root . left ) print ( root . key end = ' ' ) inorderRec ( root . right ) def treeins ( arr ): for i in range ( len ( arr )): insert ( arr [ i ]) # Driver Code arr = [ 5 4 7 2 11 ] treeins ( arr ) inorderRec ( root ) # This code is contributed by shinjanpatraJavaScript// C# program to // implement Tree Sort using System ; public class GFG { // Class containing left and // right child of current // node and key value public class Node { public int key ; public Node left right ; public Node ( int item ) { key = item ; left = right = null ; } } // Root of BST Node root ; // Constructor GFG () { root = null ; } // This method mainly // calls insertRec() void insert ( int key ) { root = insertRec ( root key ); } /* A recursive function to insert a new key in BST */ Node insertRec ( Node root int key ) { /* If the tree is empty return a new node */ if ( root == null ) { root = new Node ( key ); return root ; } /* Otherwise recur down the tree */ if ( key < root . key ) root . left = insertRec ( root . left key ); else if ( key > root . key ) root . right = insertRec ( root . right key ); /* return the root */ return root ; } // A function to do // inorder traversal of BST void inorderRec ( Node root ) { if ( root != null ) { inorderRec ( root . left ); Console . Write ( root . key + ' ' ); inorderRec ( root . right ); } } void treeins ( int [] arr ) { for ( int i = 0 ; i < arr . Length ; i ++ ) { insert ( arr [ i ]); } } // Driver Code public static void Main ( String [] args ) { GFG tree = new GFG (); int [] arr = { 5 4 7 2 11 }; tree . treeins ( arr ); tree . inorderRec ( tree . root ); } } // This code is contributed by Rajput-Ji
Вихід2 4 5 7 11Аналіз складності:
Середня складність справи: O(n log n) Додавання одного елемента до дерева бінарного пошуку в середньому займає O(log n) часу. Тому додавання n елементів займе O(n log n) часу
Найгірша часова складність: O(n 2 ). У найгіршому випадку часову складність Tree Sort можна покращити за допомогою самобалансуючого бінарного дерева пошуку, такого як Red Black Tree AVL Tree. У найгіршому випадку використання самобалансуючого сортування бінарного дерева займе O(n log n) часу для сортування масиву.
Допоміжний простір: O(n)
Створіть вікторину
Вам Може Сподобатися
Кращі Статті
Категорія
