Baumsortierung

Harshit Jindal 12 Oktober 2023
  1. Baumsortieralgorithmus
  2. Beispiel für Baumsortierung
  3. Implementierung des Baumsortieralgorithmus
  4. Baumsortieralgorithmus Komplexität
Baumsortierung

Baumsortierung ist ein Online-Sortieralgorithmus. Er verwendet die Datenstruktur des binären Suchbaums, um die Elemente zu speichern. Die Elemente können in sortierter Reihenfolge abgerufen werden, indem eine in-order Traversierung des binären Suchbaums durchgeführt wird. Da es sich um einen Online-Sortieralgorithmus handelt, werden die eingefügten Elemente immer in sortierter Reihenfolge gehalten.

Baumsortieralgorithmus

Nehmen wir an, dass wir ein unsortiertes Array A[] mit n Elementen haben.

TreeSort()

  • Bauen Sie den Binärsuchbaum auf, indem Sie Elemente aus dem Array in den Binärsuchbaum einfügen.
  • Führen Sie in-order Traversal auf dem Baum durch, um die Elemente wieder in sortierter Reihenfolge zu erhalten.

Insert()

  • Erstellen Sie einen BST-Knoten mit einem Wert, der dem Array-Element A[i] entspricht.
  • Insert(node,key)
    • Wenn root==Null, wird der neu gebildete Knoten zurückgegeben.
    • Wenn root->data < key, root->right = insert(root->right,key).
    • Wenn root->data > key, root->left= insert(root->left,key)
  • gibt den Zeiger auf die ursprüngliche Wurzel zurück.

Inorder()

  • Traversiert den linken Teilbaum.
  • Besuchen Sie die Wurzel.
  • Traversieren Sie den rechten Teilbaum.

Beispiel für Baumsortierung

Angenommen, wir haben das Array: (5, 3, 4, 2, 1, 6). Wir werden es mit dem Einfügungs-Sortieralgorithmus sortieren.

Baumsortieralgorithmus

Zuerst initialisieren wir BST, indem wir den Wurzelknoten 5 erzeugen.

3 ist kleiner als 5, also wird er links von 5 eingefügt.

4 ist kleiner als 5, aber größer als 3, also wird es rechts von 3, aber links von 4 eingefügt.

2 ist das kleinste Element im aktuellen Baum, also wird es an der äußersten linken Position eingefügt.

1 ist das kleinste Element im aktuellen Baum, also wird es an der äußersten linken Position eingefügt.

6 ist das größte Element im aktuellen Baum, also wird es an der äußersten rechten Position eingefügt.

Nachdem der BST aufgebaut wurde, führen wir eine in-order Traversierung des Baums durch, um das endgültige sortierte Array (1, 2, 3 ,4, 5, 6) zu erhalten.

Implementierung des Baumsortieralgorithmus

#include <bits/stdc++.h>

using namespace std;

class Node {
 public:
  int key;
  Node *left, *right;
};

Node *newNode(int item) {
  Node *temp = new Node;
  temp->key = item;
  temp->left = temp->right = NULL;
  return temp;
}

void inorder(Node *root, int arr[], int &i) {
  if (root != NULL) {
    inorder(root->left, arr, i);
    arr[i++] = root->key;
    inorder(root->right, arr, i);
  }
}

Node *insertintoBST(Node *node, int key) {
  if (node == NULL) return newNode(key);
  if (key < node->key)
    node->left = insertintoBST(node->left, key);
  else if (key > node->key)
    node->right = insertintoBST(node->right, key);
  return node;
}

void treeSort(int arr[], int n) {
  Node *root = NULL;
  root = insertintoBST(root, arr[0]);
  for (int i = 1; i < n; i++) root = insertintoBST(root, arr[i]);
  int i = 0;
  inorder(root, arr, i);
}

int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  treeSort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Baumsortieralgorithmus Komplexität

Zeitkomplexität

  • Durchschnittlicher Fall

Im durchschnittlichen Fall liegt die Zeitkomplexität des Einfügens von n Knoten in eine BST in der Größenordnung von O(nlogn). Sie tritt auf, wenn das gebildete BST ein balanciertes BST ist. Daher ist die Zeitkomplexität in der Größenordnung von [Big Theta]: O(nlogn).

  • Schlechtester Fall

Der ungünstigste Fall tritt ein, wenn das Array sortiert ist und ein unbalancierter binärer Suchbaum mit einer maximalen Höhe von O(n) gebildet wird. Er benötigt O(n) Zeit für das Traversieren und O(n2) für das Einfügen, verglichen mit der O(logn) Zeit für das Traversieren im Falle eines regulären BST der Höhe logn. Die Zeitkomplexität im schlimmsten Fall ist [Big O] O(n2).

Sie kann auf O(nlogn) reduziert werden, wenn eine selbstbalancierende Datenstruktur wie AVL-Baum, Red-Black-Tree, etc. verwendet wird.

  • Bester Fall

Der Best-Case tritt ein, wenn der gebildete binäre Suchbaum balanciert ist. Die Best-Case-Zeitkomplexität ist [Big Omega]: O(nlogn). Sie ist identisch mit der Zeitkomplexität im durchschnittlichen Fall.

Raumkomplexität

Die Raumkomplexität für diesen Algorithmus ist O(n), da n Knoten für jedes Element im binären Suchbaum erstellt werden müssen.

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

Verwandter Artikel - Sort Algorithm