Binärer Suchbaum löschen

  2. Tutorial
  3. Datenstruktur
  4. Binärer Suchbaum löschen
Harshit Jindal 12 Oktober 2023
Data Structure Binary Tree Binary Search Tree
  1. Löschvorgang im binären Suchbaum
  2. Binäre Suchbaum-Löschdarstellung
  3. BST-Löschalgorithmus
  4. Binäre Suchbaum-Löschimplementierung
  5. Binärer Suchbaum-Löschalgorithmus Komplexität
Binärer Suchbaum löschen

Im Artikel Binärer Suchbaum: Suchen und Einfügen haben wir besprochen, wie man ein Element in einen BST einfügt und wie man nach einem Wert in einem BST sucht. In diesem Artikel wird besprochen, wie man einen Knoten aus dem binären Suchbaum löscht.

Löschvorgang im binären Suchbaum

Das Einfügen eines Knotens in einen BST ist relativ einfach. Aber beim Löschen eines Knotens müssen wir auf mehrere Möglichkeiten achten. Folgende 3 Fälle können auftreten:

  • Der zu löschende Knoten hat kein Kind - er ist ein Blatt.

Dies ist der einfachste Fall; da ein Blattknoten kein Kind hat, brauchen wir uns um nichts zu kümmern. Wir können den Blattknoten durch NULL ersetzen und den diesem Knoten zugewiesenen Platz freigeben.

  • Der zu löschende Knoten hat nur ein Kind (linkes oder rechtes Kind).

In diesem Fall speichern wir das Kind des Knotens und entfernen den Knoten von seiner ursprünglichen Position. Der untergeordnete Knoten wird dann an der ursprünglichen Position des gelöschten Knotens eingefügt.

  • Der zu löschende Knoten hat beide Kinder, linkes und rechtes Kind.

Dies ist der kniffligste Fall, denn hier können wir den Knoten nicht einfach löschen oder durch sein Kind ersetzen. In diesem Fall suchen wir den kleinsten Knoten im rechten Teilbaum des Knotens minnode. Ersetzen Sie den Wert des zu löschenden Knotens durch den Wert von minnode und rufen Sie auf diesem Knoten rekursiv delete auf.

Binäre Suchbaum-Löschdarstellung

  • Der zu löschende Knoten hat kein Kind - er ist ein Blatt.

    Binäre Suchbaum-Löschoperation
    Der Knoten 7 hat kein Kind; löschen Sie ihn einfach aus dem Baum, es wird keine BST-Eigenschaft verletzt.

  • Der zu löschende Knoten hat nur ein Kind

    Binäre Suchbaum-Löschoperation
    Der Knoten 15 hat ein Kind 7; wir müssen uns vor dem Löschen von 15 um dieses Kind kümmern. Also kopieren wir ihn zuerst und ersetzen ihn dann durch 15.

  • Der zu löschende Knoten hat beide Kinder.

    Löschvorgang im binären Suchbaum
    Der Knoten 21 hat zwei Kinder - 15 und 27. Wir finden das kleinste Element im rechten Teilbaum 23 und ersetzen es durch 21, und dann rufen wir eine Rekursion auf, um 23 aus dem rechten Teilbaum zu löschen.

BST-Löschalgorithmus

  • Wenn root == NULL , dann wird NULL zurückgegeben.
  • Wenn root->key < X, dann verwerfen Sie den linken Teilbaum und finden das zu löschende Element im rechten Teilbaum

    root-> right = deleteNode(root->right,X)

  • Else if root->key > X, then discard the right subtree and find the element to be deleted in left subtree

    root->left = deleteNode(root->left, X)

  • Wenn root->key ==X, dann entsprechend den 3 Fällen vorgehen:
    • Wenn (root->left == NULL && root->right == NULL) dann root löschen und NULL zurückgeben.
    • Andernfalls, wenn (root->right == NULL), kopieren Sie den linken Teilbaum und ersetzen Sie ihn durch den zu löschenden Knoten.
    • Andernfalls, wenn (root->left == NULL) dann kopiere den rechten Teilbaum und ersetze ihn durch den zu löschenden Knoten.
    • Andernfalls, wenn (root->left && root->right) dann suche den minimalen Knoten im rechten Teilbaum minnode und ersetze ihn durch den zu löschenden Knoten. Rekursiv minnode aus dem rechten Teilbaum löschen.
  • Geben Sie den Zeiger auf die ursprüngliche root zurück.

Binäre Suchbaum-Löschimplementierung

#include <iostream>
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) {
  if (root != NULL) {
    inorder(root->left);
    cout << root->key << " ";
    inorder(root->right);
  }
}

void insert(Node*& root, int key) {
  Node* toinsert = newNode(key);
  Node* curr = root;
  Node* prev = NULL;

  while (curr != NULL) {
    prev = curr;
    if (key < curr->key)
      curr = curr->left;
    else
      curr = curr->right;
  }
  if (prev == NULL) {
    prev = toinsert;
    root = prev;
  }

  else if (key < prev->key) {
    prev->left = toinsert;
  }

  else {
    prev->right = toinsert;
  }
}

Node* getmin(Node* root) {
  Node* curr = root;

  while (curr && curr->left) {
    curr = curr->left;
  }

  return curr;
}

Node* deleteNode(Node* root, int key) {
  if (root == NULL) return root;

  if (key < root->key)
    root->left = deleteNode(root->left, key);

  else if (key > root->key)
    root->right = deleteNode(root->right, key);
  else {
    if (root->left == NULL) {
      Node* temp = root->right;
      delete (root);
      return temp;
    } else if (root->right == NULL) {
      Node* temp = root->left;
      delete (root);
      return temp;
    }

    Node* temp = getmin(root->right);

    root->key = temp->key;
    root->right = deleteNode(root->right, temp->key);
  }
  return root;
}

int main() {
  Node* root = NULL;
  insert(root, 5);
  insert(root, 3);
  insert(root, 8);
  insert(root, 6);
  insert(root, 4);
  insert(root, 2);
  insert(root, 1);
  insert(root, 7);
  inorder(root);
  cout << "\n";
  deleteNode(root, 5);
  inorder(root);
}

Binärer Suchbaum-Löschalgorithmus Komplexität

Zeit Komplexität

  • Durchschnittlicher Fall

Im durchschnittlichen Fall ist die Zeitkomplexität des Löschens eines Knotens aus einem 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 Löschens ist in der Größenordnung von O(logn). Sie ist identisch mit der Zeitkomplexität im durchschnittlichen 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 des Algorithmus ist O(n) aufgrund des zusätzlichen Platzbedarfs durch Rekursionsaufrufe.

Autor: Harshit Jindal
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 - Data Structure

Verwandter Artikel - Binary Tree

Verwandter Artikel - Binary Search Tree