Ağaç Sıralaması
Ağaç sıralaması dayalı bir sıralama algoritmasıdır. İkili Arama Ağacı veri yapısı. İlk önce girdi listesi veya dizideki öğelerden bir ikili arama ağacı oluşturur ve ardından öğeleri sıralı düzende elde etmek için oluşturulan ikili arama ağacında sıralı bir geçiş gerçekleştirir.
Algoritma:
1. Adım: Bir dizideki eleman girişini alın.Adım 2: Dizideki veri öğelerini diziye ekleyerek bir İkili arama ağacı oluşturun. ikili arama ağacı .3. Adım: Öğeleri sıralı düzende elde etmek için ağaçta sıralı geçiş yapın.Ağaç sıralama uygulamaları:
- En yaygın kullanımı, öğeleri çevrimiçi olarak düzenlemektir: her kurulumdan sonra, o ana kadar görülen bir dizi nesne, yapılandırılmış bir programda mevcuttur.
- İkili arama ağacı olarak bir yayılma ağacı kullanırsanız, ortaya çıkan algoritmanın (splaysort olarak adlandırılır) ek bir özelliği vardır; uyarlanabilir bir sıralamadır, bu da sanal girişler için çalışma süresinin O (n log n) değerinden daha hızlı olduğu anlamına gelir.
Yukarıdaki yaklaşımın uygulaması aşağıdadır:
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
Çıkış2 4 5 7 11Karmaşıklık Analizi:
Ortalama Vaka Süresi Karmaşıklığı: O(n log n) İkili Arama ağacına bir öğe eklemek ortalama olarak O(log n) zaman alır. Bu nedenle n öğe eklemek O(n log n) zaman alacaktır
En Kötü Durumda Zaman Karmaşıklığı: Açık 2 ). Ağaç Sıralamanın en kötü durum zaman karmaşıklığı, Red Black Tree AVL Ağacı gibi kendi kendini dengeleyen bir ikili arama ağacı kullanılarak iyileştirilebilir. Kendi kendini dengeleyen ikili ağaç Ağaç Sıralaması'nın kullanılması, diziyi en kötü durumda sıralamak için O(n log n) zaman alacaktır.
Yardımcı Alan: Açık)
Test Oluştur
Hoşunuza Gidebilir
En Makaleler
Kategori
Ilginç Haberler
