Angenommen BST , besteht die Aufgabe darin, einen neuen Knoten einzufügen BST .
Beispiel:
Einfügen in den binären Suchbaum
So fügen Sie einen Wert in einen binären Suchbaum ein:
Am Blatt wird immer ein neuer Schlüssel eingefügt, indem die Eigenschaft des binären Suchbaums beibehalten wird. Wir beginnen mit der Suche nach einem Schlüssel von der Wurzel aus, bis wir auf einen Blattknoten stoßen. Sobald ein Blattknoten gefunden wurde, wird der neue Knoten als untergeordnetes Element des Blattknotens hinzugefügt. Die folgenden Schritte werden ausgeführt, während wir versuchen, einen Knoten in einen binären Suchbaum einzufügen:
- Überprüfen Sie den einzufügenden Wert (z. B X ) mit dem Wert des aktuellen Knotens (z. B val ) wir sind in:
- Wenn X ist weniger als val Wechseln Sie zum linken Teilbaum.
- Andernfalls wechseln Sie zum rechten Teilbaum.
- Sobald der Blattknoten erreicht ist, fügen Sie ihn ein X nach rechts oder links, basierend auf der Beziehung zwischen X und der Wert des Blattknotens.
Befolgen Sie zum besseren Verständnis die folgende Abbildung:
Illustration:
Einfügung in BST
Einfügung in BST
Einfügung in BST
Einfügung in BST
Einfügung in BST
Einfügen in einen binären Suchbaum mithilfe von Rekursion:
Nachfolgend finden Sie die Implementierung der Einfügeoperation mithilfe der Rekursion.
C++14
foreach-Schleifen-Typoskript
// C++ program to demonstrate insertion> // in a BST recursively> #include> using> namespace> std;> class> BST {> >int> data;> >BST *left, *right;> public>:> >// Default constructor.> >BST();> >// Parameterized constructor.> >BST(>int>);> >// Insert function.> >BST* Insert(BST*,>int>);> >// Inorder traversal.> >void> Inorder(BST*);> };> // Default Constructor definition.> BST::BST()> >: data(0)> >, left(NULL)> >, right(NULL)> {> }> // Parameterized Constructor definition.> BST::BST(>int> value)> {> >data = value;> >left = right = NULL;> }> // Insert function definition.> BST* BST::Insert(BST* root,>int> value)> {> >if> (!root) {> >// Insert the first node, if root is NULL.> >return> new> BST(value);> >}> >// Insert data.> >if> (value>root->data) {> >// Insert right node data, if the 'value'> >// to be inserted is greater than 'root' node data.> >// Process right nodes.> >root->right = Insert(root->right, value);> >}> >else> if> (value data) {> >// Insert left node data, if the 'value'> >// to be inserted is smaller than 'root' node data.> >// Process left nodes.> >root->left = Insert(root->left, value);> >}> >// Return 'root' node, after insertion.> >return> root;> }> // Inorder traversal function.> // This gives data in sorted order.> void> BST::Inorder(BST* root)> {> >if> (!root) {> >return>;> >}> >Inorder(root->links);> >cout ' '; Inorder(root->Rechts); } // Treibercode int main() { BST b, *root = NULL; root = b.Insert(root, 50); b.Insert(root, 30); b.Insert(root, 20); b.Insert(root, 40); b.Insert(root, 70); b.Insert(root, 60); b.Insert(root, 80); b.Inorder(root); 0 zurückgeben; }> |
>
>
C
// C program to demonstrate insert> // operation in binary> // search tree.> #include> #include> struct> node {> >int> key;> >struct> node *left, *right;> };> // A utility function to create a new BST node> struct> node* newNode(>int> item)> {> >struct> node* temp> >= (>struct> node*)>malloc>(>sizeof>(>struct> node));> >temp->key = item;> >temp->links = temp->rechts = NULL;> >return> temp;> }> // A utility function to do inorder traversal of BST> void> inorder(>struct> node* root)> {> >if> (root != NULL) {> >inorder(root->links);> >printf>(>'%d '>, root->Schlüssel);> >inorder(root->rechts);> >}> }> // A utility function to insert> // a new node with given key in BST> struct> node* insert(>struct> node* node,>int> key)> {> >// If the tree is empty, return a new node> >if> (node == NULL)> >return> newNode(key);> >// Otherwise, recur down the tree> >if> (key key)> >node->left = insert(node->left, key);> >else> if> (key>Knoten->Schlüssel)> >node->right = insert(node->right, key);> >// Return the (unchanged) node pointer> >return> node;> }> // Driver Code> int> main()> {> >/* Let us create following BST> >50> >/> >30 70> >/ /> >20 40 60 80 */> >struct> node* root = NULL;> >root = insert(root, 50);> >insert(root, 30);> >insert(root, 20);> >insert(root, 40);> >insert(root, 70);> >insert(root, 60);> >insert(root, 80);> >// Print inorder traversal of the BST> >inorder(root);> >return> 0;> }> |
>
>
Java
// Java program to demonstrate> // insert operation in binary> // search tree> import> java.io.*;> public> class> BinarySearchTree {> >// Class containing left> >// and right child of current node> >// and key value> >class> Node {> >int> key;> >Node left, right;> >public> Node(>int> item)> >{> >key = item;> >left = right =>null>;> >}> >}> >// Root of BST> >Node root;> >// Constructor> >BinarySearchTree() { root =>null>; }> >BinarySearchTree(>int> value) { root =>new> Node(value); }> >// This method mainly calls insertRec()> >void> insert(>int> key) { root = insertRec(root, key); }> >// A recursive function to> >// insert a new key in BST> >Node insertRec(Node root,>int> key)> >{> >// If the tree is empty,> >// return a new node> >if> (root ==>null>) {> >root =>new> Node(key);> >return> root;> >}> >// Otherwise, recur down the tree> >else> if> (key root.left = insertRec(root.left, key); else if (key>root.key) root.right = insertRec(root.right, key); // Den (unveränderten) Knotenzeiger zurückgeben return root; } // Diese Methode ruft hauptsächlich InorderRec() auf void inorder() { inorderRec(root); } // Eine Hilfsfunktion zum // Durchlaufen von BST in der richtigen Reihenfolge. void inorderRec(Node root) { if (root != null) { inorderRec(root.left); System.out.print(root.key + ' '); inorderRec(root.right); } } // Treibercode public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); /* Lassen Sie uns folgendes BST erstellen 50 / 30 70 / / 20 40 60 80 */ tree.insert(50); tree.insert(30); tree.insert(20); tree.insert(40); tree.insert(70); tree.insert(60); tree.insert(80); // Inorder-Traversierung des BST-Baums drucken.inorder(); } } // Dieser Code wurde von Ankur Narain Verma>'> beigesteuert |
Was ist Rom?
>
# Python program to demonstrate># insert operation in binary search tree># A utility class that represents># an individual node in a BST>class>Node:>>def>__init__(>self>, key):>>self>.left>=>None>>self>.right>=>None>>self>.val>=>key># A utility function to insert># a new node with the given key>def>insert(root, key):>>if>root>is>None>:>>return>Node(key)>>else>:>>if>root.val>=>=>key:>>return>root>>elif>root.val root.right = insert(root.right, key) else: root.left = insert(root.left, key) return root # A utility function to do inorder tree traversal def inorder(root): if root: inorder(root.left) print(root.val, end=' ') inorder(root.right) # Driver program to test the above functions if __name__ == '__main__': # Let us create the following BST # 50 # / # 30 70 # / / # 20 40 60 80 r = Node(50) r = insert(r, 30) r = insert(r, 20) r = insert(r, 40) r = insert(r, 70) r = insert(r, 60) r = insert(r, 80) # Print inorder traversal of the BST inorder(r)>>>C#
// C# program to demonstrate>// insert operation in binary>// search tree>using>System;>class>BinarySearchTree {>>// Class containing left and>>// right child of current node>>// and key value>>public>class>Node {>>public>int>key;>>public>Node left, right;>>public>Node(>int>item)>>{>>key = item;>>left = right =>null>;>>}>>}>>// Root of BST>>Node root;>>// Constructor>>BinarySearchTree() { root =>null>; }>>BinarySearchTree(>int>value) { root =>new>Node(value); }>>// This method mainly calls insertRec()>>void>insert(>int>key) { root = insertRec(root, key); }>>// A recursive function to insert>>// a new key in BST>>Node insertRec(Node root,>int>key)>>{>>// If the tree is empty,>>// return a new node>>if>(root ==>null>) {>>root =>new>Node(key);>>return>root;>>}>>// Otherwise, recur down the tree>>if>(key root.left = insertRec(root.left, key); else if (key>root.key) root.right = insertRec(root.right, key); // Den (unveränderten) Knotenzeiger zurückgeben return root; } // Diese Methode ruft hauptsächlich InorderRec() auf void inorder() { inorderRec(root); } // Eine Hilfsfunktion zum // Durchlaufen von BST in der richtigen Reihenfolge. void inorderRec(Node root) { if (root != null) { inorderRec(root.left); Console.Write(root.key + ' '); inorderRec(root.right); } } // Treibercode public static void Main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); /* Lassen Sie uns folgendes BST erstellen 50 / 30 70 / / 20 40 60 80 */ tree.insert(50); tree.insert(30); tree.insert(20); tree.insert(40); tree.insert(70); tree.insert(60); tree.insert(80); // Inorder-Traversierung des BST-Baums drucken.inorder(); } } // Dieser Code wurde von aashish1995>'> beigesteuert>
>// javascript program to demonstrate>// insert operation in binary>// search tree>>/*>>* Class containing left and right child of current node and key value>>*/>>class Node {>>constructor(item) {>>this>.key = item;>>this>.left =>this>.right =>null>;>>}>>}>>// Root of BST>>var>root =>null>;>>// This method mainly calls insertRec()>>function>insert(key) {>>root = insertRec(root, key);>>}>>// A recursive function to insert a new key in BST>>function>insertRec(root, key) {>>// If the tree is empty, return a new node>>if>(root ==>null>) {>>root =>new>Node(key);>>return>root;>>}>>// Otherwise, recur down the tree>>if>(key root.left = insertRec(root.left, key); else if (key>root.key) root.right = insertRec(root.right, key); // Den (unveränderten) Knotenzeiger zurückgeben return root; } // Diese Methode ruft hauptsächlich die Funktion InorderRec() auf inorder() { inorderRec(root); } // Eine Hilfsfunktion zum // Durchlaufen der BST-Funktion in der Reihenfolge inorderRec(root) { if (root != null) { inorderRec(root.left); document.write(root.key+' '); inorderRec(root.right); } } // Treibercode /* Lassen Sie uns folgendes BST erstellen: 50 / 30 70 / / 20 40 60 80 */ insert(50); einfügen(30); einfügen(20); einfügen(40); einfügen(70); einfügen(60); einfügen(80); // Inorder-Durchlauf des BST drucken inorder(); // Dieser Code wurde von Rajput-Ji beigesteuert>>>Ausgabe20 30 40 50 60 70 80>Zeitkomplexität:
- Die zeitliche Komplexität von Einfügevorgängen beträgt im schlimmsten Fall Oh) Wo H ist die Höhe des binären Suchbaums.
- Im schlimmsten Fall müssen wir möglicherweise von der Wurzel zum tiefsten Blattknoten reisen. Die Höhe eines schiefen Baumes kann betragen N und die zeitliche Komplexität des Einfügevorgangs kann zunehmen An).
Hilfsraum: Das Hilfsmittel Die räumliche Komplexität des Einfügens in einen binären Suchbaum beträgt O(1)
Einfügen in den binären Suchbaum mithilfe eines iterativen Ansatzes:
Anstatt die Rekursion zu verwenden, können wir die Einfügeoperation auch iterativ mit a implementieren while-Schleife . Nachfolgend finden Sie die Implementierung mithilfe einer While-Schleife.
Fuchs gegen WolfC++
// C++ Code to insert node and to print inorder traversal>// using iteration>#include>using>namespace>std;>// BST Node>class>Node {>public>:>>int>val;>>Node* left;>>Node* right;>>Node(>int>val)>>: val(val)>>, left(NULL)>>, right(NULL)>>{>>}>};>// Utility function to insert node in BST>void>insert(Node*& root,>int>key)>{>>Node* node =>new>Node(key);>>if>(!root) {>>root = node;>>return>;>>}>>Node* prev = NULL;>>Node* temp = root;>>while>(temp) {>>if>(temp->val> key) {>>prev = temp;>>temp = temp->links;>>}>>else>if>(temp->val prev = temp; temp = temp->right; } } if (prev->val> key) prev->left = node; sonst prev->right = node; } // Hilfsfunktion zum Drucken von inorder traversal void inorder(Node* root) { Node* temp = root; Maschen stapeln; while (temp != NULL || !st.empty()) { if (temp != NULL) { st.push(temp); temp = temp->left; } else { temp = st.top(); st.pop(); cout ' '; temp = temp->right; } } } // Treibercode int main() { Node* root = NULL; einfügen(Wurzel, 30); einfügen(Wurzel, 50); einfügen(Wurzel, 15); einfügen(Wurzel, 20); einfügen(Wurzel, 10); einfügen(Wurzel, 40); einfügen(Wurzel, 60); // Funktionsaufruf zum Drucken der Inorder-Traversierung inorder(root); 0 zurückgeben; }>>>Java
// Java code to implement the insertion>// in binary search tree>import>java.io.*;>import>java.util.*;>class>GFG {>>// Driver code>>public>static>void>main(String[] args)>>{>>BST tree =>new>BST();>>tree.insert(>30>);>>tree.insert(>50>);>>tree.insert(>15>);>>tree.insert(>20>);>>tree.insert(>10>);>>tree.insert(>40>);>>tree.insert(>60>);>>tree.inorder();>>}>}>class>Node {>>Node left;>>int>val;>>Node right;>>Node(>int>val) {>this>.val = val; }>}>class>BST {>>Node root;>>// Function to insert a key>>public>void>insert(>int>key)>>{>>Node node =>new>Node(key);>>if>(root ==>null>) {>>root = node;>>return>;>>}>>Node prev =>null>;>>Node temp = root;>>while>(temp !=>null>) {>>if>(temp.val>Schlüssel) {>>prev = temp;>>temp = temp.left;>>}>>else>if>(temp.val prev = temp; temp = temp.right; } } if (prev.val>Schlüssel) prev.left = Knoten; sonst prev.right = Knoten; } // Funktion zum Drucken des Inorder-Werts public void inorder() { Node temp = root; Stapelstapel = neuer Stapel(); while (temp != null || !stack.isEmpty()) { if (temp != null) { stack.add(temp); temp = temp.left; } else { temp = stack.pop(); System.out.print(temp.val + ' '); temp = temp.right; } } } }>>>Python3
# Python 3 code to implement the insertion># operation iteratively>class>GFG:>>@staticmethod>>def>main(args):>>tree>=>BST()>>tree.insert(>30>)>>tree.insert(>50>)>>tree.insert(>15>)>>tree.insert(>20>)>>tree.insert(>10>)>>tree.insert(>40>)>>tree.insert(>60>)>>tree.inorder()>class>Node:>>left>=>None>>val>=>0>>right>=>None>>def>__init__(>self>, val):>>self>.val>=>val>class>BST:>>root>=>None>># Function to insert a key in the BST>>def>insert(>self>, key):>>node>=>Node(key)>>if>(>self>.root>=>=>None>):>>self>.root>=>node>>return>>prev>=>None>>temp>=>self>.root>>while>(temp !>=>None>):>>if>(temp.val>Schlüssel):>>prev>=>temp>>temp>=>temp.left>>elif>(temp.val prev = temp temp = temp.right if (prev.val>key): prev.left = node else: prev.right = node # Funktion zum Drucken der Inorder-Traversierung von BST def inorder(self): temp = self.root stack = [] while (temp != None or not (len( stack) == 0)): if (temp != None): stack.append(temp) temp = temp.left else: temp = stack.pop() print(str(temp.val) + ' ', end='') temp = temp.right if __name__ == '__main__': GFG.main([]) # Dieser Code wurde von rastogik346 beigesteuert.>>>C#
Pfad in Java festgelegt
// Function to implement the insertion>// operation iteratively>using>System;>using>System.Collections.Generic;>public>class>GFG {>>// Driver code>>public>static>void>Main(String[] args)>>{>>BST tree =>new>BST();>>tree.insert(30);>>tree.insert(50);>>tree.insert(15);>>tree.insert(20);>>tree.insert(10);>>tree.insert(40);>>tree.insert(60);>>// Function call to print the inorder traversal>>tree.inorder();>>}>}>public>class>Node {>>public>Node left;>>public>int>val;>>public>Node right;>>public>Node(>int>val) {>this>.val = val; }>}>public>class>BST {>>public>Node root;>>// Function to insert a new key in the BST>>public>void>insert(>int>key)>>{>>Node node =>new>Node(key);>>if>(root ==>null>) {>>root = node;>>return>;>>}>>Node prev =>null>;>>Node temp = root;>>while>(temp !=>null>) {>>if>(temp.val>Schlüssel) {>>prev = temp;>>temp = temp.left;>>}>>else>if>(temp.val prev = temp; temp = temp.right; } } if (prev.val>Schlüssel) prev.left = Knoten; sonst prev.right = Knoten; } // Funktion zum Drucken der Inorder-Traversierung von BST public void inorder() { Node temp = root; Stapelstapel = neuer Stapel(); while (temp != null || stack.Count != 0) { if (temp != null) { stack.Push(temp); temp = temp.left; } else { temp = stack.Pop(); Console.Write(temp.val + ' '); temp = temp.right; } } } } // Dieser Code wurde von Rajput-Ji beigesteuert>>>Javascript
// JavaScript code to implement the insertion>// in binary search tree>class Node {>>constructor(val) {>>this>.left =>null>;>>this>.val = val;>>this>.right =>null>;>>}>}>class BST {>>constructor() {>>this>.root =>null>;>>}>>// Function to insert a key>>insert(key) {>>let node =>new>Node(key);>>if>(>this>.root ==>null>) {>>this>.root = node;>>return>;>>}>>let prev =>null>;>>let temp =>this>.root;>>while>(temp !=>null>) {>>if>(temp.val>Schlüssel) {>>prev = temp;>>temp = temp.left;>>}>else>if>(temp.val prev = temp; temp = temp.right; } } if (prev.val>key) prev.left = node; sonst prev.right = node; } // Funktion zum Drucken des Inorder-Werts inorder() { let temp = this.root; let stack = []; while (temp != null || stack.length> 0) { if (temp != null) { stack.push(temp); temp = temp.left; } else { temp = stack.pop(); console.log(temp.val + ' '); temp = temp.right; } } } } let tree = new BST(); tree.insert(30); tree.insert(50); tree.insert(15); tree.insert(20); tree.insert(10); tree.insert(40); tree.insert(60); tree.inorder(); // Dieser Code wurde von devendrasolunke beigesteuert>>>Ausgabe10 15 20 30 40 50 60>Der Zeitkomplexität von Inorder-Durchquerung Ist An) , da jeder Knoten einmal besucht wird.
Der Hilfsraum Ist An) , da wir einen Stapel verwenden, um Knoten für die Rekursion zu speichern.Verwandte Links:
- Binärer Suchbaum-Suchvorgang
- Löschvorgang für binären Suchbaum