Binärer Suchbaum

1. Suchoperationen im binären Suchbaum
2. BST-Suchalgorithmus
3. BST-Suche Abbildung
4. Einfügen in BST
5. BST-Einfügealgorithmus
6. BST Insert Abbildung
7. Implementierung von BST Search & Insert
8. BST-Einfüge- und Suchalgorithmus Komplexität

Binary Search Tree (BST) ist eine geordnete knotenbasierte Binärbaum-Datenstruktur. Die Knoten haben einen Wert und zwei Kindknoten (Ein Binärbaum hat maximal zwei Kindknoten), die links und rechts an ihm hängen. Bis auf den Wurzelknoten können alle Knoten nur von ihrem Elternteil referenziert werden. Ein BST hat die folgenden Eigenschaften:

• Alle Knoten im linken Teilbaum sind kleiner als der Wurzelknoten.
• Alle Knoten im rechten Teilbaum sind größer als der Wurzelknoten.
• Der linke und der rechte Teilbaum müssen ebenfalls binäre Suchbäume sein.

Der Baum auf der linken Seite erfüllt alle Eigenschaften des BST. Andererseits scheint der Baum auf der rechten Seite ein BST zu sein, da alle Knoten im linken Teilbaum kleiner und im rechten Teilbaum größer sind. Aber der Knoten 1 im linken Teilbaum erfüllt die BST-Eigenschaften nicht, da er kleiner als der Knoten 4, aber nicht größer als der Wurzelknoten 3 ist. Daher handelt es sich nicht um eine BST.

Da es sich um eine geordnete Datenstruktur handelt, sind die eingegebenen Elemente immer sortiert angeordnet. Wir können In-Order-Traversal verwenden, um die in der BST gespeicherten Daten in sortierter Reihenfolge abzurufen. Sie hat ihren Namen, weil sie, genau wie die binäre Suche, zum Durchsuchen der Daten in O(logn) verwendet werden kann.

Suchoperationen im binären Suchbaum

Wir wissen, dass in einem BST alle Elemente auf der rechten Seite der Wurzel größer sind. Wenn also das gesuchte Zielelement kleiner als die Wurzel ist, kann der gesamte rechte Teilbaum vernachlässigt werden. Analog dazu kann der linke Teilbaum vernachlässigt werden, wenn das Element größer als die Wurzel ist. Wir bewegen uns auf ähnliche Weise, bis wir den Baum erschöpfen oder das Zielelement als Wurzel des Teilbaums finden. Wenn der BST balanciert ist (Ein Baum wird als balanciert bezeichnet, wenn für alle Knoten die Differenz zwischen der Höhe des linken und des rechten Teilbaums kleiner als gleich 1 ist.), dann verläuft die Suche innerhalb des BST ähnlich wie die binäre Suche, da beide Teilbäume etwa die Hälfte der Elemente haben, die bei jeder Iteration vernachlässigt werden.

BST-Suchalgorithmus

Sei root der Wurzelknoten von BST und X das zu suchende Zielelement.

BST-Suche Abbildung

Angenommen, wir haben die obige BST und wollen das Element X = 25 finden.

Einfügen in BST

Der Algorithmus zum Einfügen eines Elements in BST ist dem Suchen eines Elements in BST sehr ähnlich, da wir vor dem Einfügen eines Elements dessen korrekte Position finden müssen. Der einzige Unterschied zwischen der Einfüge- und der Suchfunktion besteht darin, dass wir im Falle der Suche den Knoten zurückgeben, der den Zielwert enthält, während wir im Falle des Einfügens einen neuen Knoten an der entsprechenden Position des Knotens erstellen.

BST-Einfügealgorithmus

Sei root der Wurzelknoten von BST und X das Element, das wir einfügen wollen.

BST Insert Abbildung

Auf diese Weise fügen wir Elemente innerhalb einer BST ein.

Implementierung von BST Search & Insert

#include <iostream>
using namespace std;

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

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

void inorder(Node *root) {
  if (root != NULL) {
    inorder(root->left);
    cout << root->key << " ";
    inorder(root->right);
  }
}

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

  return root;
}

Node *search(Node *root, int key) {
  if (root == NULL || root->key == key) return root;

  if (root->key < key) return search(root->right, key);

  return search(root->left, key);
}
int main() {
  Node *root = NULL;
  root = insert(root, 5);
  root = insert(root, 3);
  root = insert(root, 8);
  root = insert(root, 6);
  root = insert(root, 4);
  root = insert(root, 2);
  root = insert(root, 1);
  root = insert(root, 7);
  cout << search(root, 5)->key << endl;
}

BST-Einfüge- und Suchalgorithmus Komplexität

Zeitkomplexität

• Durchschnittlicher Fall

Im durchschnittlichen Fall ist die Zeitkomplexität des Einfügens eines Knotens oder der Suche nach einem Element in einer BST in der Größenordnung der Höhe des binären Suchbaums. Im Durchschnitt ist die Höhe eines BST O(logn). Sie tritt auf, wenn die gebildete BST eine balancierte BST ist. Daher ist die Zeitkomplexität in der Größenordnung von [Big Theta]: O(logn).

• Bester Fall

Der Best-Case tritt auf, wenn der Baum ein balanciertes BST ist. Die Best-Case-Zeitkomplexität des Einfügens und Suchens ist in der Größenordnung von O(logn). Sie ist identisch mit der Zeitkomplexität im mittleren Fall.

• Schlimmster Fall

Im schlimmsten Fall müssen wir von der Wurzel bis zum tiefsten Blattknoten, d. h. über die gesamte Höhe h des Baums, gehen. Wenn der Baum unbalanciert ist, d. h. schief, kann die Höhe des Baums n werden, und daher ist die Zeitkomplexität im schlimmsten Fall sowohl für die Einfüge- als auch für die Suchoperation O(n).

Raumkomplexität

Die Platzkomplexität sowohl der Einfüge- als auch der Suchoperationen ist O(n) aufgrund des Platzbedarfs der rekursiven Aufrufe.