Binärer Suchbaum Iteratives Einfügen

1. BST Iterativer Einfügealgorithmus
2. BST Iteratives Einfügen Abbildung
3. Implementierung des iterativen Einfügens von BST
4. BST Iterativer Einfügealgorithmus Komplexität

Im vorherigen Artikel Binärer Suchbaum haben wir den rekursiven Ansatz zum Einfügen eines Knotens in BST besprochen. In diesem Beitrag werden wir den iterativen Ansatz zum Einfügen eines Knotens in BST besprechen. Er ist besser als die rekursive Methode, da der iterative Einfügealgorithmus keinen zusätzlichen Platz benötigt.

BST Iterativer Einfügealgorithmus

Sei root der Wurzelknoten von BST und key das Element, das eingefügt werden soll.

BST Iteratives Einfügen Abbildung

Auf diese Weise fügen wir Elemente in ein BST ein.

Implementierung des iterativen Einfügens von BST

#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;
}

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);
}

BST Iterativer Einfügealgorithmus Komplexität

Zeitkomplexität

• Durchschnittlicher Fall

Im durchschnittlichen Fall ist die Zeitkomplexität des Einfügens eines Knotens in eine 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 ist in der Größenordnung von O(logn). Sie ist identisch mit der Zeitkomplexität im mittleren Fall.

• Schlechtester 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 Worst-Case-Zeitkomplexität sowohl für die Einfüge- als auch für die Suchoperation O(n).

Raumkomplexität

Die Platzkomplexität der iterativen Einfügeoperation ist O(1), da kein zusätzlicher Platz benötigt wird.