Überprüfung des Binären Suchbaum

  2. Tutorial
  3. Datenstruktur
  4. Überprüfung des Binären Suchbaum
Harshit Jindal 12 Oktober 2023
Data Structure Binary Tree Binary Search Tree
  1. Der Algorithmus zum Prüfen, ob ein binärer Baum ein binärer Suchbaum ist
  2. Implementierung des Algorithmus zur Überprüfung, ob ein binärer Baum ein binärer Suchbaum ist
  3. Komplexitätsanalyse
Überprüfung des Binären Suchbaum

Ein Binärbaum ist eine nichtlineare Datenstruktur. Er wird als Binärbaum bezeichnet, weil jeder Knoten maximal zwei Kinder hat. Diese Kinder werden als linke Kinder und rechte Kinder bezeichnet. Damit ein Binärbaum zu einem BST wird, muss er die folgenden Eigenschaften erfüllen:

  • 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 Algorithmus zum Prüfen, ob ein binärer Baum ein binärer Suchbaum ist

Algorithmus 1

Bei diesem Ansatz wird geprüft, ob der linke Teilbaum ein Element enthält, das größer als der Wert der Wurzel ist, und ob der rechte Teilbaum ein Element enthält, das kleiner als der Wert der Wurzel ist, indem jeder Knoten als Wurzel seines Teilbaums betrachtet wird. Um das Max- und Min-Element zu finden, müssen wir zwei separate Funktionen verwenden, getMin() und getMax().

getMin()

  • Initialisieren Sie temp als root.
  • Während temp ein left hat, machen Sie folgendes:
    • Setzen Sie temp als temp->left, d.h. gehen Sie nach links, um das kleinste Element zu finden.
  • Geben Sie temp->val als den minimalen Wert innerhalb dieses Teilbaums zurück.

getMax()

  • Initialisieren Sie temp als root.
  • Solange temp ein right hat, tun Sie Folgendes:
    • Setzen Sie temp als temp->rechts, d.h. gehen Sie nach rechts, um das größte Element zu finden.
  • Geben Sie temp->val als den maximalen Wert innerhalb dieses Teilbaums zurück.

istBST(Wurzel)

  • Wenn die root NULL ist, wird true zurückgegeben.
  • Finde maximales Element maxm im linken Teilbaum durch Aufruf von getMax(root->left);
  • Finde minimales Element minm im rechten Teilbaum durch Aufruf von getMin(root->right);
  • Wenn das Wurzelelement kleiner als maxm oder größer als minm ist, wird false zurückgegeben.
  • Prüfen Sie rekursiv alle Knoten, indem Sie isBST(root->left) und isBST(root->right) aufrufen. Wenn beide rekursiven Aufrufe true zurückgeben, dann ist der Baum BST, andernfalls wird false zurückgegeben.

Der obige Algorithmus sagt uns, ob ein Baum BST ist oder nicht, ist aber extrem langsam. Die Funktionen getMin() und getMax() haben im schlimmsten Fall eine Zeitkomplexität von O(n) und werden für n Knoten aufgerufen, so dass die gesamte Zeitkomplexität O(n2) ist.

Algorithmus 2:

Dieser Algorithmus verbessert den vorherigen Algorithmus, indem er keine wiederholten Berechnungen durchführt. Der vorherige Ansatz rief getMin() und getMax() für jeden Knoten auf. Dieser Ansatz verbessert den obigen Ansatz, indem er die minimal und maximal zulässigen Werte beim Durchlaufen der Knoten im Auge behält.

istBST(root)

  • Initialisieren Sie zwei Variablen min als INT_MIN und max als INT_MAX.
  • Rufen Sie isBST(root,min,max) auf.

isBST(Wurzel, min, max)

  • Wenn root NULL ist, wird true zurückgegeben.
  • Wenn min > root->data, dann ist die BST-Eigenschaft verletzt, gib false zurück.
  • Wenn max < root->data, dann ist die BST-Eigenschaft verletzt, gib false zurück.
  • Prüfen Sie rekursiv den linken Teilbaum durch den Aufruf von isBST(root->left, min, root->data-1) (die Übergabe von min und root->data - 1 als Argumente ändert den gültigen Bereich für BST im linken Teilbaum) und den rechten Teilbaum durch den Aufruf von isBST(root->right, root->data+1, max) (die Übergabe von root->data + 1 und max als Argumente ändert den gültigen Bereich für BST im rechten Teilbaum).
  • Wenn beide rekursiven Aufrufe true zurückgeben, dann ist der Baum BST, geben Sie true zurück.

Die Zeitkomplexität dieses Algorithmus beträgt O(n), was eine deutliche Verbesserung gegenüber der vorherigen Methode darstellt.

Algorithmus 3:

Dieser Algorithmus vermeidet die Verwendung von INT_MIN und INT_MAX im obigen Algorithmus, indem er sie durch zwei Zeiger, l und r, ersetzt.

istBST(Wurzel)

  • Initialisieren Sie zwei Knoten l und r als NULL.
  • Rufen Sie isBST(root, l, r) auf. (Überladener Funktionsaufruf)

isBST(root, l, r)

  • Wenn root NULL ist, wird true zurückgegeben.
  • Wenn l nicht NULL ist und l->data >= root->data, dann ist die BST-Eigenschaft verletzt, gib false zurück.
  • Wenn r nicht NULL ist und r->data <= root->data, dann ist die BST-Eigenschaft verletzt, gib false zurück.
  • Überprüfen Sie rekursiv den linken Teilbaum durch den Aufruf von isBST(root->left, left, root) (die Übergabe von root als 3. Argument ändert die minimale Wertgrenze für den Teilbaum) und den rechten Teilbaum durch den Aufruf von isBST(root->right, root, right) (die Übergabe von root als 2. Argument ändert die maximale Wertgrenze für den Teilbaum).
  • Wenn beide rekursiven Aufrufe true zurückgeben, dann ist der Baum BST, return true.

Algorithmus 4:

Die inorder-Traversierung des binären Suchbaums gibt Elemente in sortierter Reihenfolge zurück. Wir können diese Eigenschaft verwenden, um zu prüfen, ob ein binärer Baum BST ist. Wenn alle Elemente bei der inorder-Traversierung nicht in aufsteigender Reihenfolge sind, dann ist der gegebene Baum kein binärer Suchbaum.

isBST(root)

  • Initialisieren Sie die Variable prev als INT_MIN. Mit prev wird geprüft, ob der aktuelle Knoten größer als prev ist und somit der sortierten Reihenfolge folgt.
  • Rufen Sie isBST(root, prev) auf. (Überladener Funktionsaufruf).

isBST(root,prev)

  • Wenn die root NULL ist, wird true zurückgegeben.
  • Rekursive Prüfung des linken Teilbaums durch isBST(root->left, prev). Wenn es false ergibt, dann geben Sie false zurück.
  • Wenn root->data <= prev. aufsteigende Reihenfolge verletzt ist, geben Sie false zurück.
  • Aktualisieren Sie prev->data als root->data.
  • Rekursiv prüfen Sie den rechten Teilbaum mit isBST(root->right, prev). Wenn es false liefert, dann geben Sie false zurück.
  • Andernfalls geben Sie true zurück.

Implementierung des Algorithmus zur Überprüfung, ob ein binärer Baum ein binärer Suchbaum ist

Algorithmus 1

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
int getMin(Node* root) {
  while (root->left) {
    root = root->left;
  }

  return root->data;
}
int getMax(Node* root) {
  while (root->right) {
    root = root->right;
  }

  return root->data;
}
bool isBST(Node* root) {
  if (root == NULL) return true;

  if (root->left != NULL && getMax(root->left) > root->data) return false;

  if (root->right != NULL && getMin(root->right) < root->data) return false;

  if (!isBST(root->left) || !isBST(root->right)) return false;

  return true;
}
int main() {
  Node* root = new Node(6);
  root->left = new Node(3);
  root->right = new Node(9);
  root->left->left = new Node(1);
  root->left->right = new Node(5);
  root->right->left = new Node(7);
  root->right->right = new Node(11);
  if (isBST(root)) {
    cout << "This binary tree is a BST." << endl;
  } else {
    cout << "This binary tree is not a BST." << endl;
  }
  return 0;
}

Algorithmus 2

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
bool isBST(Node* root, int min, int max) {
  if (root == NULL) return 1;
  if (root->data < min || root->data > max) return 0;

  return isBST(root->left, min, root->data - 1) &&
         isBST(root->right, root->data + 1, max);
}

bool isBST(Node* root) { return isBST(root, INT_MIN, INT_MAX); }
int main() {
  Node* root = new Node(6);
  root->left = new Node(3);
  root->right = new Node(9);
  root->left->left = new Node(1);
  root->left->right = new Node(5);
  root->right->left = new Node(7);
  root->right->right = new Node(11);
  if (isBST(root)) {
    cout << "This binary tree is a BST." << endl;
  } else {
    cout << "This binary tree is not a BST." << endl;
  }
  return 0;
}

Algorithmus 3

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
bool isBST(Node* root, Node* l, Node* r) {
  if (root == NULL) return true;

  if (l != NULL and root->data <= l->data) return false;
  if (r != NULL and root->data >= r->data) return false;

  return isBST(root->left, l, root) && isBST(root->right, root, r);
}
bool isBST(Node* root) {
  Node* l = NULL;
  Node* r = NULL;
  return isBST(root, l, r);
}
int main() {
  Node* root = new Node(6);
  root->left = new Node(3);
  root->right = new Node(9);
  root->left->left = new Node(1);
  root->left->right = new Node(5);
  root->right->left = new Node(7);
  root->right->right = new Node(11);
  if (isBST(root)) {
    cout << "This binary tree is a BST." << endl;
  } else {
    cout << "This binary tree is not a BST." << endl;
  }
  return 0;
}

Algorithmus 4

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
bool isBST(Node* root, int& prev) {
  if (!root) return true;

  if (!isBST(root->left, prev)) return false;

  if (root->data <= prev) return false;
  prev = root->data;

  return isBST(root->right, prev);
}

bool isBST(Node* root) {
  int prev = INT_MIN;
  return isBST(root, prev);
}
int main() {
  Node* root = new Node(6);
  root->left = new Node(3);
  root->right = new Node(9);
  root->left->left = new Node(1);
  root->left->right = new Node(5);
  root->right->left = new Node(7);
  root->right->right = new Node(11);
  if (isBST(root)) {
    cout << "This binary tree is a BST." << endl;
  } else {
    cout << "This binary tree is not a BST." << endl;
  }
  return 0;
}

Komplexitätsanalyse

Zeitkomplexität

  • Durchschnittlicher Fall

Um zu prüfen, ob der gegebene Binärbaum BST ist oder nicht, müssen wir alle n Knoten durchlaufen, da ein einziger Knoten, der die Eigenschaften missachtet, dazu führt, dass der Baum nicht BST ist. Daher ist die Zeitkomplexität in der Größenordnung von [Big Theta]: O(n).

  • Bester Fall

Die Zeitkomplexität im besten Fall liegt in der Größenordnung von O(n). Sie ist identisch mit der Zeitkomplexität im mittleren Fall.

  • Schlechtester Fall

Die Worst-Case-Zeitkomplexität ist in der Größenordnung von O(n). Sie ist identisch mit der Zeitkomplexität im besten Fall.

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