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

Umwandlung von Binärbaum in BST Abbildung

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.