Binärbaum in Binärsuchbaum konvertieren

Binärbaum in Binärsuchbaum konvertieren

  1. Algorithmus zum Konvertieren eines Binärbaums in BST
  2. Umwandlung von Binärbaum in BST Abbildung
  3. Binärbaum in BST umwandeln Implementierung
  4. Binärbaum in BST umwandeln Algorithmuskomplexität

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. Er kann auch als ein ungerichteter Graph interpretiert werden, in dem der oberste Knoten als Wurzel bezeichnet wird. Ein Binary Search Tree (BST) ist ein binärer Baum mit speziellen Eigenschaften, der dabei hilft, die Daten in einer sortierten Weise zu organisieren.

In diesem Lernprogramm wird beschrieben, wie ein Binärbaum in einen BST konvertiert wird, wobei die ursprüngliche Struktur des Binärbaums erhalten bleibt.

Algorithmus zum Konvertieren eines Binärbaums in BST

  • Erstellen Sie ein Array mit dem Namen arr, um die geordnete Traversierung der Binärbaumknoten zu speichern.
  • Sortieren Sie arr mit einem beliebigen Sortieralgorithmus (MergeSort O(nlogn), QuickSort O(n^2), Insertion Sort O(n^2), usw.).
  • Führen Sie wiederum die inorder Traversierung des Baums durch und speichern Sie die Elemente im Binärbaum aus dem sortierten Array arr, um den BST zu erhalten.

Umwandlung von Binärbaum in BST Abbildung

Binärbaum in BST umwandeln Abbildung

  • Sortieren Sie das Array arr mit einem beliebigen Sortieralgorithmus, um [1, 2, 3, 4, 5, 6] zu erhalten.
  • Wir rufen erneut das Inorder-Traversal auf, um das sortierte Array arr wieder im Binärbaum zu speichern, um unseren BST zu erhalten.

Binärbaum in BST umwandeln Implementierung

#include <bits/stdc++.h>
using namespace std;

class Node {
    public:
        int data;
        Node *left, *right;
        Node(int x) {
            this->data = x;
            this->left = this->right = NULL;
        }
};
vector<int>v;

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

void storetree(Node*root, int i = 0) {
    if (!root) {
        return;
    }
    storetree(root->left);
    v.push_back(root->data);
    storetree(root->right);
}

void restoretree(Node*root, int& i) {
    if (!root) {
        return;
    }
    restoretree(root->left, i);
    root->data = v[i];
    i++;
    restoretree(root->right, i);
}

void converttoBST(Node*root) {
    if (!root) {
        return;
    }
    storetree(root);
    sort(v.begin(), v.end());
    int i = 0;
    restoretree(root, i);
}

int main() {
    Node* root = new Node(3);
    root->left = new Node(1);
    root->right = new Node(7);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->left->left->right = new Node(2);
    root->right->left = new Node(6);
    root->right->right = new Node(9);
    root->right->right->left = new Node(8);
    cout << "The inorder traversal of the tree is : "; inorder(root); cout << endl;
    converttoBST(root);
    cout << "The inorder traversal of the tree is : "; inorder(root); cout << endl;
}

Binärbaum in BST umwandeln Algorithmuskomplexität

Zeitkomplexität

  • Durchschnittlicher Fall

Die Zeitkomplexität des Inorder-Traversals, bei dem wir das Array in sorted speichern und das sorted Array zurück in den Binärbaum speichern, ist O(n). Aber die Komplexität des Sortierens des Arrays ist O(nlogn) und daher ist die Gesamtkomplexität gegeben als O(nlogn) + 2*O(n). Die Zeitkomplexität liegt in der Größenordnung von O(nlogn).

  • Bester Fall

Die Zeitkomplexität im besten Fall liegt in der Größenordnung von O(n). Wenn der gegebene Binärbaum bereits ein BST ist, führen wir das Inorder-Traversal durch, um ihn zu realisieren, und es sind keine Sortieroperationen erforderlich.

  • Schlimmster Fall

Die Zeitkomplexität im schlimmsten Fall liegt in der Größenordnung von O(nlogn).

Raumkomplexität

Die Platzkomplexität des Algorithmus ist O(n) aufgrund des zusätzlichen Platzbedarfs durch Rekursionsaufrufe.

Verwandter Artikel - Data Structure

  • Binärbaum-Traversal
  • Binärer Suchbaum
  • Binärer Suchbaum Inorder Succesor
  • Binärer Suchbaum Iteratives Einfügen
  • Binärer Suchbaum löschen
  • Verwandter Artikel - Binary Tree

  • Binärbaum-Traversal
  • Binärer Suchbaum
  • Binärer Suchbaum Inorder Succesor
  • Binärer Suchbaum Iteratives Einfügen
  • Binärer Suchbaum löschen
  • Verwandter Artikel - Binary Search Tree

  • Binärer Suchbaum
  • Binärer Suchbaum Inorder Succesor
  • Binärer Suchbaum Iteratives Einfügen
  • Binärer Suchbaum löschen
  • Überprüfung des Binären Suchbaum