Gegeven een BST , de taak is om hierin een nieuw knooppunt in te voegen BST .
Voorbeeld:
Invoeging in binaire zoekboom
Een waarde invoegen in een binaire zoekboom:
Er wordt altijd een nieuwe sleutel in het blad ingevoegd, waarbij de eigenschap van de binaire zoekboom behouden blijft. We beginnen te zoeken naar een sleutel vanaf de wortel totdat we een bladknooppunt tegenkomen. Zodra een bladknooppunt is gevonden, wordt het nieuwe knooppunt toegevoegd als een onderliggend knooppunt van het bladknooppunt. De onderstaande stappen worden gevolgd terwijl we proberen een knooppunt in een binaire zoekboom in te voegen:
- Controleer de waarde die moet worden ingevoegd (bijv X ) met de waarde van het huidige knooppunt (zeg val ) Wij zijn in:
- Als X is minder dan val ga naar de linker subboom.
- Ga anders naar de juiste subboom.
- Zodra het bladknooppunt is bereikt, plaatst u het in X naar rechts of links, afhankelijk van de relatie tussen X en de waarde van het bladknooppunt.
Volg de onderstaande afbeelding voor een beter begrip:
Illustratie:
Invoeging in BST
Invoeging in BST
Invoeging in BST
Invoeging in BST
Invoeging in BST
Invoeging in binaire zoekboom met behulp van recursie:
Hieronder ziet u de implementatie van de invoegbewerking met behulp van recursie.
C++14
logica van de eerste orde
// 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->gegevens) {> >// Insert right node data, if the 'value'> >// to be inserted is greater than 'root' node data.> >// Process right nodes.> >root->rechts = Invoegen(root->rechts, waarde);> >}> >else> if> (value data) {> >// Insert left node data, if the 'value'> >// to be inserted is smaller than 'root' node data.> >// Process left nodes.> >root->links = Invoegen(root->links, waarde);> >}> >// 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); } // Stuurprogrammacode int main() { BST b, *root = NULL; root = b.Insert(root, 50); b.Invoegen(root, 30); b.Invoegen(root, 20); b.Insert(root, 40); b.Invoegen(root, 70); b.Insert(root, 60); b.Insert(root, 80); b.Inorde(root); retour 0; }> |
>
>
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->sleutel = 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->toets);> >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->links = invoegen(knooppunt->links, sleutel);> >else> if> (key>knooppunt->sleutel)> >node->rechts = invoegen(knooppunt->rechts, sleutel);> >// 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, sleutel); // Retourneer de (ongewijzigde) knooppuntaanwijzer return root; } // Deze methode roept voornamelijk InorderRec() void inorder() { inorderRec(root); } // Een hulpprogrammafunctie om // in volgorde de BST te doorlopen void inorderRec(Node root) { if (root != null) { inorderRec(root.left); Systeem.uit.print(root.key + ' '); inorderRec(root.right); } } // Stuurprogrammacode public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); /* Laten we de volgende BST 50 / 30 70 / / 20 40 60 80 */ tree.insert(50); boom.insert(30); boom.insert(20); boom.insert(40); boom.insert(70); boom.insert(60); boom.insert(80); // Print in volgorde doorloop van de BST tree.inorder(); } } // Deze code is bijgedragen door Ankur Narain Verma> |
website zoals coomeet
>
>
Python3
# 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, sleutel); // Retourneer de (ongewijzigde) knooppuntaanwijzer return root; } // Deze methode roept voornamelijk InorderRec() void inorder() { inorderRec(root); } // Een hulpprogrammafunctie om // in volgorde de BST te doorlopen void inorderRec(Node root) { if (root != null) { inorderRec(root.left); Console.Write(root.key + ''); inorderRec(root.right); } } // Stuurprogrammacode public static void Main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); /* Laten we de volgende BST 50 / 30 70 / / 20 40 60 80 */ tree.insert(50); boom.insert(30); boom.insert(20); boom.insert(40); boom.insert(70); boom.insert(60); boom.insert(80); // Print in volgorde doorloop van de BST tree.inorder(); } } // Deze code is bijgedragen door aashish1995> |
>
>
Javascript
> // 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, sleutel); // Retourneer de (ongewijzigde) knooppuntaanwijzer return root; } // Deze methode roept hoofdzakelijk de functie InorderRec() aan inorder() { inorderRec(root); } // Een hulpprogrammafunctie om // de BST-functie in volgorde te doorlopen inorderRec(root) { if (root != null) { inorderRec(root.left); document.write(root.key+''); inorderRec(root.right); } } // Stuurprogrammacode /* Laten we de volgende BST 50 / 30 70 / / 20 40 60 80 */ insert(50); invoegen(30); invoegen(20); invoegen(40); invoegen(70); invoegen(60); invoegen(80); // Print inorder-doorgang van de BST inorder(); // Deze code is bijgedragen door Rajput-Ji> |
>
>Uitvoer
20 30 40 50 60 70 80>
Tijdcomplexiteit:
- De worst-case tijdscomplexiteit van invoegbewerkingen is dat wel Oh) waar H is de hoogte van de binaire zoekboom.
- In het ergste geval moeten we mogelijk van de wortel naar het diepste bladknooppunt reizen. De hoogte van een scheve boom kan worden N en de tijdcomplexiteit van de invoegoperatie kan toenemen Op).
Hulpruimte: De hulpstof de ruimtecomplexiteit van het invoegen in een binaire zoekboom is O(1)
Invoeging in binaire zoekboom met behulp van een iteratieve aanpak:
In plaats van recursie te gebruiken, kunnen we de invoegbewerking ook iteratief implementeren met behulp van a herhalingslus . Hieronder ziet u de implementatie met behulp van een while-lus.
mooiste glimlach ter wereld
C++
// 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> sleutel) {> >prev = temp;> >temp = temp->links;> >}> >else> if> (temp->val vorige = temperatuur; temperatuur = temperatuur->rechts; } } if (prev->val> sleutel) prev->left = knooppunt; anders vorige->rechts = knooppunt; } // Hulpprogrammafunctie om af te drukken in volgorde traversal void inorder (Node* root) { Node* temp = root; stapel st; while (temp != NULL || !st.empty()) { if (temp != NULL) { st.push(temp); temp = temp->links; } anders { temp = st.top(); st.pop(); cout ''; temperatuur = temperatuur->rechts; } } } // Stuurprogrammacode int main() { Knooppunt* root = NULL; invoegen(wortel, 30); invoegen(wortel, 50); invoegen(wortel, 15); invoegen(wortel, 20); invoegen(wortel, 10); invoegen(wortel, 40); invoegen(wortel, 60); // Functieaanroep om de inorder traversal inorder(root) af te drukken; retour 0; }> |
>
>
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>sleutel) {> >prev = temp;> >temp = temp.left;> >}> >else> if> (temp.val prev = temp; temp = temp.right; } } if (prev.val>sleutel) prev.left = knooppunt; anders prev.right = knooppunt; } // Functie om de inorderwaarde public void inorder() af te drukken { Node temp = root; Stapelstapel = nieuwe stapel(); while (temp != null || !stack.isEmpty()) { if (temp != null) { stack.add(temp); temp = temp.links; } anders { temp = stack.pop(); Systeem.uit.print(temp.val + ' '); temp = temp.rechts; } } } }> |
>
>
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>sleutel):> >prev>=> temp> >temp>=> temp.left> >elif>(temp.val prev = temp temp = temp.right if (prev.val>key): prev.left = knooppunt else: prev.right = knooppunt # Functie om de inorder-traversal van BST def inorder(self) af te drukken: temp = self.root stack = [] while (temp != Geen of niet (len( stack) == 0)): if (temp != Geen): stack.append(temp) temp = temp.left else: temp = stack.pop() print(str(temp.val) + ' ', end='') temp = temp.right if __name__ == '__main__': GFG.main([]) # Deze code is bijgedragen door rastogik346.> |
>
>
C#
np.samenvoegen
// 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>sleutel) {> >prev = temp;> >temp = temp.left;> >}> >else> if> (temp.val prev = temp; temp = temp.right; } } if (prev.val>sleutel) prev.left = knooppunt; anders prev.right = knooppunt; } // Functie om de volgorde van BST public void inorder() af te drukken {Node temp = root; Stapelstapel = nieuwe stapel(); while (temp != null || stack.Count != 0) { if (temp != null) { stack.Push(temp); temp = temp.links; } anders { temp = stapel.Pop(); Console.Write(temp.val + ' '); temp = temp.rechts; } } } } // Deze code is bijgedragen door Rajput-Ji> |
>
>
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>sleutel) {> >prev = temp;> >temp = temp.left;> >}>else> if> (temp.val prev = temp; temp = temp.right; } } if (prev.val>sleutel) prev.left = knooppunt; anders prev.right = knooppunt; } // Functie om de inorderwaarde inorder() af te drukken { let temp = this.root; laat stapel = []; while (temp != null || stack.length> 0) { if (temp != null) { stack.push(temp); temp = temp.links; } anders { temp = stack.pop(); console.log(temp.val + ' '); temp = temp.rechts; } } } } let boom = nieuwe BST(); boom.insert(30); boom.insert(50); boom.insert(15); boom.insert(20); boom.insert(10); boom.insert(40); boom.insert(60); boom.inorder(); // deze code is bijgedragen door devendrasolunke> |
>
>Uitvoer
10 15 20 30 40 50 60>
De tijd complexiteit van ongeordende doortocht is Op) , aangezien elk knooppunt één keer wordt bezocht.
De Hulpruimte is Op) , omdat we een stapel gebruiken om knooppunten op te slaan voor recursie.
Gerelateerde Links:
- Zoekbewerking in binaire zoekboom
- Binaire zoekboomverwijderingsbewerking