TRI PAR ARBRE

Tri des arbres est un algorithme de tri basé sur Arbre de recherche binaire structure des données. Il crée d'abord un arbre de recherche binaire à partir des éléments de la liste ou du tableau d'entrée, puis effectue un parcours dans l'ordre sur l'arbre de recherche binaire créé pour obtenir les éléments dans l'ordre trié.

Algorithme:

Étape 1 : Prenez les éléments entrés dans un tableau. Étape 2 : arbre de recherche binaire . Étape 3 :

Applications du tri par arbre :

Si vous utilisez un arbre splay comme arbre de recherche binaire, l'algorithme résultant (appelé splaysort) a une propriété supplémentaire selon laquelle il s'agit d'un tri adaptatif, ce qui signifie que son temps de travail est plus rapide que O (n log n) pour les entrées virtuelles.

C++

    // C++ program to implement Tree Sort   #include       using     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  ;   }

Java

    // 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 M

Python3

    # 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 shinjanpatra

    // 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

JavaScript

     <  script  >   // Javascript program to    // implement Tree Sort   // Class containing left and   // right child of current    // node and key value   class     Node     {      constructor  (  item  )     {      this  .  key     =     item  ;      this  .  left     =     this  .  right     =     null  ;      }   }   // Root of BST   let     root     =     new     Node  ();   root     =     null  ;   // This method mainly   // calls insertRec()   function     insert  (  key  )     {      root     =     insertRec  (  root       key  );   }   /* A recursive function to    insert a new key in BST */   function     insertRec  (  root       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   function     inorderRec  (  root  )     {      if     (  root     !=     null  )     {      inorderRec  (  root  .  left  );      document  .  write  (  root  .  key     +     ' '  );      inorderRec  (  root  .  right  );      }   }   function     treeins  (  arr  )     {      for     (  let     i     =     0  ;     i      <     arr  .  length  ;     i  ++  )     {      insert  (  arr  [  i  ]);      }   }   // Driver Code   let     arr     =     [  5       4       7       2       11  ];   treeins  (  arr  );   inorderRec  (  root  );   // This code is contributed   // by Saurabh Jaiswal    <  /script>

Sortir

2 4 5 7 11

Analyse de complexité :

Complexité de la durée moyenne des dossiers : O(n log n) L'ajout d'un élément à un arbre de recherche binaire prend en moyenne un temps O(log n). Par conséquent, l’ajout de n éléments prendra un temps O(n log n)

Dans le pire des cas, complexité temporelle : Sur ²). The worst case time complexity of Tree Sort can be improved by using a self-balancing binary search tree like Red Black Tree AVL Tree. Using self-balancing binary tree Tree Sort will take O(n log n) time to sort the array in worst case.

Espace auxiliaire : Sur)