Glede na a BST , je naloga v to vstaviti novo vozlišče BST .
primer:
Vstavljanje v binarno iskalno drevo
Kako vstaviti vrednost v binarno iskalno drevo:
Nov ključ se vedno vstavi na list z ohranjanjem lastnosti binarnega iskalnega drevesa. Ključ začnemo iskati od korena, dokler ne zadenemo listnega vozlišča. Ko je listno vozlišče najdeno, se novo vozlišče doda kot podrejeno listnemu vozlišču. Med poskusom vstavljanja vozlišča v binarno iskalno drevo sledimo spodnjim korakom:
- Preverite vrednost, ki jo želite vnesti (recimo X ) z vrednostjo trenutnega vozlišča (recimo val ) smo v:
- če X je manj kot val premakniti na levo poddrevo.
- V nasprotnem primeru se premaknite na desno poddrevo.
- Ko dosežete listno vozlišče, vstavite X na svojo desno ali levo glede na razmerje med X in vrednost listnega vozlišča.
Sledite spodnji sliki za boljše razumevanje:
Ilustracija:
Vstavljanje v BST
Vstavljanje v BST
Vstavljanje v BST
Vstavljanje v BST
Vstavljanje v BST
Vstavljanje v binarno iskalno drevo z uporabo rekurzije:
Spodaj je implementacija operacije vstavljanja z uporabo rekurzije.
C++14
razlika datumov v excelu
// 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>koren->podatki) {> >// Insert right node data, if the 'value'> >// to be inserted is greater than 'root' node data.> >// Process right nodes.> >root->desno = Vstavi(koren->desno, vrednost);> >}> >else> if> (value data) {> >// Insert left node data, if the 'value'> >// to be inserted is smaller than 'root' node data.> >// Process left nodes.> >root->levo = Vstavi(koren->levo, vrednost);> >}> >// 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->levo);> >cout ' '; Inorder(root->prav); } // Koda gonilnika int main() { BST b, *root = NULL; root = b.Insert(root, 50); b.Vstavi (koren, 30); b.Vstavi (koren, 20); b.Vstavi (koren, 40); b.Vstavi(koren, 70); b.Vstavi (koren, 60); b.Vstavi(koren, 80); b.Inorder(root); vrni 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->ključ = predmet;> >temp->levo = temp->desno = NULL;> >return> temp;> }> // A utility function to do inorder traversal of BST> void> inorder(>struct> node* root)> {> >if> (root != NULL) {> >inorder(root->levo);> >printf>(>'%d '>, root->ključ);> >inorder(root->desno);> >}> }> // 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->levo = vstavi (vozlišče->levo, tipka);> >else> if> (key>vozlišče->ključ)> >node->desno = vstavi (vozlišče->desno, ključ);> >// 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); // Vrni (nespremenjen) kazalec vozlišča return root; } // Ta metoda večinoma kliče InorderRec() void inorder() { inorderRec(root); } // Pomožna funkcija za // prečkanje po vrstnem redu BST void inorderRec(Node root) { if (root != null) { inorderRec(root.left); System.out.print(root.key + ' '); inorderRec(root.right); } } // Koda gonilnika public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); /* Ustvarimo naslednji BST 50 / 30 70 / / 20 40 60 80 */ tree.insert(50); drevo.insert(30); drevo.insert(20); drevo.insert(40); drevo.insert(70); drevo.insert(60); drevo.insert(80); // Natisni prehod po vrstnem redu drevesa BST.inorder(); } } // To kodo je prispeval Ankur Narain Verma> |
git add --all
>
>
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, key); // Vrni (nespremenjen) kazalec vozlišča return root; } // Ta metoda večinoma kliče InorderRec() void inorder() { inorderRec(root); } // Pomožna funkcija za // prečkanje po vrstnem redu BST void inorderRec(Node root) { if (root != null) { inorderRec(root.left); Console.Write(root.key + ' '); inorderRec(root.right); } } // Koda gonilnika public static void Main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); /* Ustvarimo naslednji BST 50 / 30 70 / / 20 40 60 80 */ tree.insert(50); drevo.insert(30); drevo.insert(20); drevo.insert(40); drevo.insert(70); drevo.insert(60); drevo.insert(80); // Natisni prehod po vrstnem redu drevesa BST.inorder(); } } // To kodo je prispeval 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, key); // Vrni (nespremenjen) kazalec vozlišča return root; } // Ta metoda večinoma kliče funkcijo InorderRec() inorder() { inorderRec(root); } // Pomožna funkcija za // prečkanje po vrstnem redu funkcije BST inorderRec(root) { if (root != null) { inorderRec(root.left); document.write(root.key+' '); inorderRec(root.right); } } // Koda gonilnika /* Ustvarimo naslednji BST 50 / 30 70 / / 20 40 60 80 */ insert(50); vstavi(30); vstavi(20); vstavi(40); vstavi(70); vložek (60); vstavi(80); // Natisni prehod po vrstnem redu BST inorder(); // To kodo je prispeval Rajput-Ji> |
>
>Izhod
20 30 40 50 60 70 80>
Časovna zapletenost:
- Najslabša časovna zapletenost operacij vstavljanja je O(h) kje h je višina binarnega iskalnega drevesa.
- V najslabšem primeru bomo morda morali potovati od korena do najglobljega listnega vozla. Višina poševnega drevesa lahko postane n in časovna zapletenost operacije vstavljanja lahko postane O(n).
Pomožni prostor: Pomožni prostorska kompleksnost vstavljanja v binarno iskalno drevo je O(1)
Vstavljanje v binarno iskalno drevo z uporabo iterativnega pristopa:
Namesto uporabe rekurzije lahko operacijo vstavljanja izvajamo tudi iterativno z uporabo a medtem ko zanka . Spodaj je implementacija z uporabo zanke while.
omejitve e-bančništva
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> ključ) {> >prev = temp;> >temp = temp->levo;> >}> >else> if> (temp->val prev = temp; temp = temp->desno; } } if (prev->val> tipka) prev->left = vozlišče; else prev->desno = vozlišče; } // Pomožna funkcija za tiskanje prečkanja po vrstnem redu void inorder(Node* root) { Node* temp = root; kup st; medtem ko (temp != NULL || !st.empty()) { if (temp != NULL) { st.push(temp); temp = temp->levo; } else { temp = st.top(); st.pop(); cout ' '; temp = temp->desno; } } } // Koda gonilnika int main() { Node* root = NULL; vstavi (koren, 30); vstavi (koren, 50); vstavi (koren, 15); vstavi (koren, 20); vstavi (koren, 10); vstavi (koren, 40); vstavi (koren, 60); // Klic funkcije za tiskanje prečkanja vrstnega reda inorder(root); vrni 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>ključ) {> >prev = temp;> >temp = temp.left;> >}> >else> if> (temp.val prev = temp; temp = temp.right; } } if (prev.val>ključ) prev.left = vozlišče; else prev.right = vozlišče; } // Funkcija za tiskanje vrednosti inorder public void inorder() { Node temp = root; Stack stack = new Stack(); medtem ko (temp != null || !stack.isEmpty()) { if (temp != null) { stack.add(temp); temp = temp.levo; } else { temp = stack.pop(); System.out.print(temp.val + ' '); temp = temp.desno; } } } }> |
>
>
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>ključ):> >prev>=> temp> >temp>=> temp.left> >elif>(temp.val prev = temp temp = temp.right if (prev.val>ključ): prev.left = vozlišče else: prev.right = vozlišče # Funkcija za tiskanje prečkanja po vrstnem redu BST def inorder(self): temp = self.root stack = [] while (temp != Brez ali ne (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([]) # To kodo je prispeval rastogik346.> |
>
>
C#
es5 proti es6
// 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>ključ) {> >prev = temp;> >temp = temp.left;> >}> >else> if> (temp.val prev = temp; temp = temp.right; } } if (prev.val>ključ) prev.left = vozlišče; else prev.right = vozlišče; } // Funkcija za tiskanje prečkanja po vrstnem redu BST public void inorder() { Node temp = root; Stack stack = new Stack(); medtem ko (temp != null || stack.Count != 0) { if (temp != null) { stack.Push(temp); temp = temp.levo; } else { temp = stack.Pop(); Console.Write(temp.val + ' '); temp = temp.desno; } } } } // To kodo je prispeval 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>ključ) {> >prev = temp;> >temp = temp.left;> >}>else> if> (temp.val prev = temp; temp = temp.right; } } if (prev.val>ključ) prev.left = vozlišče; else prev.right = vozlišče; } // Funkcija za tiskanje vrednosti inorder() { let temp = this.root; pusti sklad = []; medtem ko (temp != null || stack.length> 0) { if (temp != null) { stack.push(temp); temp = temp.levo; } else { temp = stack.pop(); console.log(temp.val + ' '); temp = temp.desno; } } } } let tree = new BST(); drevo.insert(30); drevo.insert(50); drevo.insert(15); drevo.insert(20); drevo.insert(10); drevo.insert(40); drevo.insert(60); drevo.inorder(); // to kodo prispeva devendrasolunke> |
>
>Izhod
10 15 20 30 40 50 60>
The časovna kompleksnost od nevrsten prehod je O(n) , saj je vsako vozlišče obiskano enkrat.
The Pomožni prostor je O(n) , saj uporabljamo sklad za shranjevanje vozlišč za rekurzijo.
Sorodne povezave:
- Operacija iskanja po binarnem iskalnem drevesu
- Operacija brisanja binarnega iskalnega drevesa