Baumsortierung

1. Baumsortieralgorithmus
2. Beispiel für Baumsortierung
3. Implementierung des Baumsortieralgorithmus
4. Baumsortieralgorithmus Komplexität

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()

Insert()

Inorder()

Beispiel für Baumsortierung

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

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(n²) 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(n²).

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.