MEDŽIŲ RŪŠIAVIMAS - 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++

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

Išvestis

2 4 5 7 11

Sudė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²). 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)