Sortowanie drzew
Sortowanie drzew to algorytm sortowania oparty na Drzewo wyszukiwania binarnego struktura danych. Najpierw tworzy drzewo wyszukiwania binarnego z elementów listy wejściowej lub tablicy, a następnie wykonuje przechodzenie w określonej kolejności po utworzonym drzewie wyszukiwania binarnego, aby uzyskać elementy w posortowanej kolejności.
Algorytm:
Krok 1: Weź elementy wejściowe w tablicy.Krok 2: Utwórz drzewo wyszukiwania binarnego, wstawiając elementy danych z tablicy do drzewo wyszukiwania binarnego .Krok 3: Wykonaj przechodzenie po drzewie w określonej kolejności, aby uzyskać elementy w posortowanej kolejności.Zastosowania sortowania drzewnego:
- Jego najczęstszym zastosowaniem jest edycja elementów online: po każdej instalacji zestaw widzianych do tej pory obiektów dostępny jest w ustrukturyzowanym programie.
- Jeśli użyjesz drzewa rozłożenia jako drzewa wyszukiwania binarnego, wynikowy algorytm (zwany sortowaniem splay) ma dodatkową właściwość, że jest sortowaniem adaptacyjnym, co oznacza, że jego czas działania jest szybszy niż O (n log n) dla wejść wirtualnych.
Poniżej implementacja powyższego podejścia:
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
Wyjście2 4 5 7 11Analiza złożoności:
Średnia złożoność czasu sprawy: O(n log n) Dodanie jednego elementu do drzewa wyszukiwania binarnego zajmuje średnio O(log n) czasu. Dlatego dodanie n elementów zajmie O(n log n) czasu
Złożoność czasowa najgorszego przypadku: NA 2 ). W najgorszym przypadku złożoność czasową sortowania drzew można poprawić, używając samobalansującego drzewa wyszukiwania binarnego, takiego jak drzewo AVL Red Black Tree. Korzystanie z samorównoważącego się drzewa binarnego Sortowanie drzewa zajmie O (n log n) czasu, aby posortować tablicę w najgorszym przypadku.
Przestrzeń pomocnicza: NA)
Utwórz quiz
Może Ci Się Spodobać
Najpopularniejsze Artykuły
Kategoria
Ciekawe Artykuły
