Medžių rūšiavimas
Medžių rūšiavimas yra rūšiavimo algoritmas, pagrįstas Dvejetainis paieškos medis duomenų struktūra. Pirmiausia jis sukuria dvejetainį paieškos medį iš įvesties sąrašo arba masyvo elementų, o tada atlieka sukurto dvejetainio paieškos medžio eilės tvarką, kad elementai būtų surūšiuoti.
Algoritmas:
1 veiksmas: Paimkite įvestus elementus į masyvą.2 veiksmas: Sukurkite dvejetainį paieškos medį, įterpdami duomenų elementus iš masyvo į dvejetainis paieškos medis .3 veiksmas: Atlikite medį eilės tvarka, kad elementai būtų surūšiuoti.Medžių rūšiavimo programos:
- Dažniausiai naudojamas elementų redagavimas internete: po kiekvieno įdiegimo struktūrinėje programoje pasiekiamas iki šiol matytų objektų rinkinys.
- Jei naudojate sklaidos medį kaip dvejetainį paieškos medį, gautas algoritmas (vadinamas splaysort) turi papildomą ypatybę, tai yra adaptyvus rūšiavimas, o tai reiškia, kad jo darbo laikas yra greitesnis nei O (n log n) virtualiems įvestims.
Toliau pateikiamas pirmiau nurodyto metodo įgyvendinimas:
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
Išvestis2 4 5 7 11Sudėtingumo analizė:
Vidutinis bylos trukmės sudėtingumas: O(n log n) Vieno elemento įtraukimas į dvejetainės paieškos medį vidutiniškai užtrunka O(log n) laiko. Todėl n elementų pridėjimas užtruks O (n log n) laiko
Blogiausio atvejo laiko sudėtingumas: O (n 2 ). Blogiausio atvejo „Tree Sort“ sudėtingumą galima pagerinti naudojant savaime balansuojantį dvejetainį paieškos medį, pvz., Red Black Tree AVL Tree. Naudojant savaime balansuojantį dvejetainį medį Medžio rūšiavimas užtruks O (n log n) laiko, kol bus surūšiuotas masyvas blogiausiu atveju.
Pagalbinė erdvė: O(n)
Sukurti viktoriną
Jums Gali Patikti
Top Straipsniai
Kategorija
Įdomios Straipsniai
