Binärer Suchbaum Iteratives Einfügen

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.

  • Erstellen Sie den einzufügenden Knoten - toinsert.
  • Initialisieren Sie zwei Zeiger, curr, der auf root zeigt, und prev, der auf null zeigt. (curr durchläuft den Baum und prev behält seine Spur bei).
  • Gehen Sie wie folgt vor, während curr! = NULL:
    • Aktualisieren Sie prev zu curr, um seinen Pfad zu erhalten.
    • Wenn curr->data > key, setze curr auf curr->left, verwerfe den rechten Teilbaum.
    • Wenn curr->data < key, setzen Sie curr auf curr->right, verwerfen Sie den linken Teilbaum.
  • Wenn prev == NULL ist, bedeutet das, dass der Baum leer ist. Erzeugen Sie den root-Knoten.
  • Andernfalls, wenn prev->data < key, dann füge toinsert rechts von prev ein, prev->right = toinsert.

BST Iteratives Einfügen Abbildung

BST Iteratives Einfügen Illustration

  • Zuerst initialisieren wir BST, indem wir einen root-Knoten erstellen und 5 darin einfügen.
  • 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.

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.

Verwandter Artikel - Data Structure

  • Binärbaum in Binärsuchbaum konvertieren
  • Binärbaum-Traversal
  • Binärer Suchbaum
  • Binärer Suchbaum Inorder Succesor
  • Binärer Suchbaum löschen
  • Verwandter Artikel - Binary Tree

  • Binärbaum in Binärsuchbaum konvertieren
  • Binärbaum-Traversal
  • Binärer Suchbaum
  • Binärer Suchbaum Inorder Succesor
  • Binärer Suchbaum löschen
  • Verwandter Artikel - Binary Search Tree

  • Binärbaum in Binärsuchbaum konvertieren
  • Binärer Suchbaum
  • Binärer Suchbaum Inorder Succesor
  • Binärer Suchbaum löschen
  • Überprüfung des Binären Suchbaum