Givet a BST , uppgiften är att infoga en ny nod i denna BST .
Exempel:
Infogning i binärt sökträd
Så här infogar du ett värde i ett binärt sökträd:
En ny nyckel infogas alltid vid bladet genom att bibehålla egenskapen för det binära sökträdet. Vi börjar söka efter en nyckel från roten tills vi träffar en lövnod. När en lövnod har hittats läggs den nya noden till som en underordnad lövnod. Nedanstående steg följs medan vi försöker infoga en nod i ett binärt sökträd:
- Kontrollera värdet som ska infogas (säg X ) med värdet för den aktuella noden (säg val ) vi är inne:
- Om X är mindre än val flytta till vänster underträd.
- Annars flyttar du till höger underträd.
- När lövnoden nås, sätt in X till höger eller vänster baserat på förhållandet mellan X och lövnodens värde.
Följ illustrationen nedan för en bättre förståelse:
Illustration:
Insättning i BST
Insättning i BST
Insättning i BST
Insättning i BST
Insättning i BST
Infogning i binärt sökträd med hjälp av rekursion:
Nedan är implementeringen av insättningsoperationen med hjälp av rekursion.
C++14
personalvalskommissionens betydelse
// 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->höger = Infoga(root->höger, värde);> >}> >else> if> (value data) {> >// Insert left node data, if the 'value'> >// to be inserted is smaller than 'root' node data.> >// Process left nodes.> >root->vänster = Infoga(root->vänster, värde);> >}> >// 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->vänster);> >cout ' '; Inorder(root->höger); } // Drivrutinskod int main() { BST b, *root = NULL; root = b.Insert(root, 50); b.Infoga(root, 30); b.Infoga(root, 20); b.Infoga(root, 40); b.Infoga(root, 70); b.Infoga(root, 60); b.Insert(root, 80); b.Inorder(root); returnera 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->nyckel = objekt;> >temp->vänster = temp->höger = NULL;> >return> temp;> }> // A utility function to do inorder traversal of BST> void> inorder(>struct> node* root)> {> >if> (root != NULL) {> >inorder(root->vänster);> >printf>(>'%d '>, root->nyckel);> >inorder(root->höger);> >}> }> // 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->vänster = infoga(nod->vänster, nyckel);> >else> if> (key>nod->nyckel)> >node->höger = infoga(nod->höger, nyckel);> >// 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, nyckel); // Returnera (oförändrad) nodpekarens returrot; } // Denna metod anropar huvudsakligen InorderRec() void inorder() { inorderRec(root); } // En verktygsfunktion för att // göra inorderövergång av BST void inorderRec(Nodrot) { if (root != null) { inorderRec(root.left); System.out.print(root.key + ' '); inorderRec(root.right); } } // Driver Code public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); /* Låt oss skapa följande BST 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); // Skriv ut inorder-traversal av BST-trädet.inorder(); } } // Denna kod är bidragit av Ankur Narain Verma> |
aryan khan
>
>
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, nyckel); // Returnera (oförändrad) nodpekarens returrot; } // Denna metod anropar huvudsakligen InorderRec() void inorder() { inorderRec(root); } // En verktygsfunktion för att // göra inorderövergång av BST void inorderRec(Nodrot) { if (root != null) { inorderRec(root.left); Console.Write(root.key + ' '); inorderRec(root.right); } } // Driver Code public static void Main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); /* Låt oss skapa följande BST 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); // Skriv ut inorder-traversal av BST-trädet.inorder(); } } // Denna kod är bidragit av 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, nyckel); // Returnera (oförändrad) nodpekarens returrot; } // Denna metod anropar huvudsakligen InorderRec()-funktionen inorder() { inorderRec(root); } // En verktygsfunktion för att // göra inorderövergång av BST-funktionen inorderRec(root) { if (root != null) { inorderRec(root.left); document.write(root.key+' '); inorderRec(root.right); } } // Driver Code /* Låt oss skapa följande BST 50 / 30 70 / / 20 40 60 80 */ insert(50); infoga (30); infoga (20); infoga (40); infoga (70); infoga (60); infoga (80); // Skriv ut inorderövergång av BST inorder(); // Denna kod är bidragit av Rajput-Ji> |
>
>Produktion
20 30 40 50 60 70 80>
Tidskomplexitet:
- Det värsta tänkbara tidskomplexiteten för skäroperationer är Åh) var h är höjden på det binära sökträdet.
- I värsta fall kan vi behöva resa från roten till den djupaste bladnoden. Höjden på ett skevt träd kan bli n och tidskomplexiteten för insättningsoperationen kan bli På).
Hjälputrymme: Hjälparen rymdkomplexiteten för infogning i ett binärt sökträd är O(1)
Infogning i binärt sökträd med iterativ metod:
Istället för att använda rekursion kan vi också implementera insättningsoperationen iterativt med hjälp av a medan loop . Nedan är implementeringen med en while-loop.
hur man konverterar sträng till int java
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> nyckel) {> >prev = temp;> >temp = temp->vänster;> >}> >else> if> (temp->val prev = temp; temp = temp->höger; } } if (prev->val> key) prev->left = nod; else prev->right = nod; } // Verktygsfunktion för att skriva ut inorder-traversal void inorder(Node* root) { Node* temp = root; stack st; while (temp != NULL || !st.empty()) { if (temp != NULL) { st.push(temp); temp = temp->vänster; } annat { temp = st.top(); st.pop(); cout ' '; temp = temp->höger; } } } // Drivrutinskod int main() { Node* root = NULL; insert(root, 30); insert(root, 50); insert(root, 15); insert(root, 20); insert(root, 10); insert(root, 40); insert(root, 60); // Funktionsanrop för att skriva ut inorder-traversal inorder(root); returnera 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>nyckel) {> >prev = temp;> >temp = temp.left;> >}> >else> if> (temp.val prev = temp; temp = temp.right; } } if (prev.val>nyckel) prev.left = nod; else prev.right = nod; } // Funktion för att skriva ut inordervärdet public void inorder() { Node temp = root; Stack stack = ny stack(); while (temp != null || !stack.isEmpty()) { if (temp != null) { stack.add(temp); temp = temp.vänster; } annat { temp = stack.pop(); System.out.print(temp.val + ' '); temp = temp.höger; } } } }> |
>
>
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>nyckel):> >prev>=> temp> >temp>=> temp.left> >elif>(temp.val prev = temp temp = temp.right if (prev.val>key): prev.left = nod else: prev.right = nod # Funktion för att skriva ut inordergenomgången av BST def inorder(self): temp = self.root stack = [] while (temp != Ingen eller inte (len( stack) == 0)): if (temp != Ingen): stack.append(temp) temp = temp.left annars: temp = stack.pop() print(str(temp.val) + ' ', end='') temp = temp.right om __name__ == '__main__': GFG.main([]) # Denna kod är bidragit av rastogik346.> |
>
>
C#
preity zinta
// 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>nyckel) {> >prev = temp;> >temp = temp.left;> >}> >else> if> (temp.val prev = temp; temp = temp.right; } } if (prev.val>nyckel) prev.left = nod; else prev.right = nod; } // Funktion för att skriva ut inordergenomgången av BST public void inorder() { Node temp = root; Stack stack = ny stack(); while (temp != null || stack.Count != 0) { if (temp != null) { stack.Push(temp); temp = temp.vänster; } annat { temp = stack.Pop(); Console.Write(temp.val + ' '); temp = temp.höger; } } } } // Denna kod är bidragit från 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>nyckel) {> >prev = temp;> >temp = temp.left;> >}>else> if> (temp.val prev = temp; temp = temp.right; } } if (prev.val>nyckel) prev.left = nod; else prev.right = nod; } // Funktion för att skriva ut inorder-värdet inorder() { let temp = this.root; låt stack = []; while (temp != null || stack.length> 0) { if (temp != null) { stack.push(temp); temp = temp.vänster; } annat { temp = stack.pop(); console.log(temp.val + ' '); temp = temp.höger; } } } } låt träd = ny BST(); tree.insert(30); tree.insert(50); tree.insert(15); tree.insert(20); tree.insert(10); tree.insert(40); tree.insert(60); tree.inorder(); // denna kod är bidragit från devendrasolunke> |
>
>Produktion
10 15 20 30 40 50 60>
De tidskomplexitet av inorderpassering är På) , eftersom varje nod besöks en gång.
De Hjälputrymme är På) , eftersom vi använder en stack för att lagra noder för rekursion.
Relaterade länkar:
- Binary Search Tree Search Operation
- Ta bort operation för binärt sökträd