ТРЕЕ СОРТ - СОРТИРАЊЕ

Врста дрвета је алгоритам за сортирање који се заснива на Бинарно стабло претраге структура података. Прво креира бинарно стабло претраге од елемената улазне листе или низа, а затим врши обилазак у редоследу креираног стабла бинарне претраге да би добио елементе у сортираном редоследу.

алгоритам:

1. корак:Узмите елементе као унос у низ.2. корак:Креирајте стабло бинарне претраге уметањем ставки података из низа у бинарно стабло претраге .Корак 3:Извршите прелазак по стаблу да бисте добили елементе у сортираном редоследу.

Апликације сортирања дрвета:

Његова најчешћа употреба је за уређивање елемената на мрежи: након сваке инсталације скуп објеката који смо до сада виђени је доступан у структурираном програму.
Ако користите стабло приказа као бинарно стабло претраге, резултујући алгоритам (назван сплаисорт) има додатно својство да је адаптивно сортирање што значи да је његово радно време брже од О (н лог н) за виртуелне улазе.

Испод је имплементација за горњи приступ:

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__(selfitem = 0): self.key = item self.leftself.right = NoneNone # 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>

Излаз

2 4 5 7 11

Анализа сложености:

Просечна сложеност случаја: О(н лог н) Додавање једне ставке у стабло бинарне претраге у просеку траје О(лог н) времена. Стога ће додавање н ставки трајати О(н лог н) времена

Временска сложеност у најгорем случају: О(н²). Временска сложеност Трее Сорт-а у најгорем случају може се побољшати коришћењем самобалансирајућег бинарног стабла претраге као што је Ред Блацк Трее АВЛ Трее. Коришћење самобалансирајућег бинарног стабла Сортирање стабла ће трајати О(н лог н) времена да сортира низ у најгорем случају.

Помоћни простор: О(н)