Ņemot vērā a BST , uzdevums ir ievietot jaunu mezglu šajā BST .
Piemērs:
Ievietošana binārajā meklēšanas kokā
Kā ievietot vērtību binārajā meklēšanas kokā:
Lapā vienmēr tiek ievietota jauna atslēga, saglabājot binārā meklēšanas koka rekvizītu. Mēs sākam meklēt atslēgu no saknes, līdz sasniedzam lapas mezglu. Kad lapas mezgls ir atrasts, jaunais mezgls tiek pievienots kā lapas mezgla bērns. Mēģinot ievietot mezglu binārajā meklēšanas kokā, tiek veiktas tālāk norādītās darbības.
- Pārbaudiet ievietojamo vērtību (teiksim X ) ar pašreizējā mezgla vērtību (teiksim val ) mes esam ieksa:
- Ja X ir mazāks par val pāriet uz kreiso apakškoku.
- Pretējā gadījumā pārejiet uz labo apakškoku.
- Kad lapas mezgls ir sasniegts, ievietojiet X pa labi vai pa kreisi, pamatojoties uz attiecību starp X un lapas mezgla vērtību.
Izpildiet tālāk sniegto ilustrāciju, lai labāk izprastu:
Ilustrācija:
Ievietošana BST
Ievietošana BST
Ievietošana BST
Ievietošana BST
Ievietošana BST
Ievietošana binārajā meklēšanas kokā, izmantojot rekursiju:
Tālāk ir parādīta ievietošanas operācijas ieviešana, izmantojot rekursiju.
C++14
css teksta līdzināšana
// 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>sakne->dati) {> >// Insert right node data, if the 'value'> >// to be inserted is greater than 'root' node data.> >// Process right nodes.> >root->tiesības = Ievietot(sakne->pa labi, vērtība);> >}> >else> if> (value data) {> >// Insert left node data, if the 'value'> >// to be inserted is smaller than 'root' node data.> >// Process left nodes.> >root->pa kreisi = 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->pa kreisi);> >cout ' '; Inorder(root->pa labi); } // Draivera kods int main() { BST b, *root = NULL; sakne = b.Ievietot(sakne, 50); b.Ievietot(sakne, 30); b.Ievietot(sakne, 20); b.Ievietot(sakne, 40); b.Ievietot(sakne, 70); b.Ievietot(sakne, 60); b.Ievietot(sakne, 80); b.Inorder(sakne); atgriezties 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->atslēga = prece;> >temp->pa kreisi = temp->right = NULL;> >return> temp;> }> // A utility function to do inorder traversal of BST> void> inorder(>struct> node* root)> {> >if> (root != NULL) {> >inorder(root->pa kreisi);> >printf>(>'%d '>, root->atslēga);> >inorder(root->pa labi);> >}> }> // 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->pa kreisi = ievietot(mezgls->pa kreisi, atslēga);> >else> if> (key>mezgls->atslēga)> >node->pa labi = ievietot(mezgls->labais, atslēga);> >// 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); // Atgriezt (nemainītu) mezgla rādītāja atgriešanas sakni; } // Šī metode galvenokārt izsauc InorderRec() void inorder() { inorderRec(root); } // Lietderības funkcija, lai // veiktu BST inorder šķērsošanu void inorderRec(Node root) { if (root != null) { inorderRec(root.left); System.out.print(root.key + ' '); inorderRec(root.right); } } // Draivera kods public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); /* Izveidosim šādu BST 50 / 30 70 / / 20 40 60 80 */ tree.insert(50); koks.ievietot(30); koks.ievietot(20); koks.ievietot(40); koks.ievietot(70); koks.ievietot(60); koks.ievietot(80); // Drukāt pasūtījuma traversal no BST tree.inorder(); } } // Šo kodu ir sagatavojis Ankur Narain Verma> |
struct masīva c programmēšana
>
>
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); // Atgriezt (nemainītu) mezgla rādītāja atgriešanas sakni; } // Šī metode galvenokārt izsauc InorderRec() void inorder() { inorderRec(root); } // Lietderības funkcija, lai // veiktu BST inorder šķērsošanu void inorderRec(Node root) { if (root != null) { inorderRec(root.left); Console.Write(root.key + ' '); inorderRec(root.right); } } // Draivera kods public static void Main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); /* Izveidosim šādu BST 50 / 30 70 / / 20 40 60 80 */ tree.insert(50); koks.ievietot(30); koks.ievietot(20); koks.ievietot(40); koks.ievietot(70); koks.ievietot(60); koks.ievietot(80); // Drukāt pasūtījuma traversal no BST tree.inorder(); } } // Šo kodu ir izstrādājis 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); // Atgriezt (nemainītu) mezgla rādītāja atgriešanas sakni; } // Šī metode galvenokārt izsauc InorderRec() funkciju inorder() { inorderRec(root); } // Lietderības funkcija, lai // veiktu BST funkcijas inorder traversal inorderRec(root) { if (root != null) { inorderRec(root.left); document.write(root.key+' '); inorderRec(root.right); } } // Draivera kods /* Izveidosim šādu BST 50 / 30 70 / / 20 40 60 80 */ insert(50); ievietot(30); ievietot(20); ievietot(40); ielikt(70); ievietot(60); ievietot(80); // Drukāt inorder traversal of BST inorder(); // Šo kodu sniedz Rajput-Ji> |
>
>Izvade
20 30 40 50 60 70 80>
Laika sarežģītība:
- Sliktākajā gadījumā ievietošanas darbību sarežģītība ir O(h) kur h ir Binārā meklēšanas koka augstums.
- Sliktākajā gadījumā mums var nākties ceļot no saknes līdz dziļākajam lapas mezglam. Slīpa koka augstums var kļūt n un ievietošanas operācijas laika sarežģītība var kļūt O(n).
Palīgtelpa: Palīgpersona telpas sarežģītība ievietošanai binārajā meklēšanas kokā ir O(1)
Ievietošana binārajā meklēšanas kokā, izmantojot iteratīvo pieeju:
Tā vietā, lai izmantotu rekursiju, mēs varam arī ieviest ievietošanas darbību iteratīvi, izmantojot a kamēr cilpa . Tālāk ir parādīta ieviešana, izmantojot kamēr cilpu.
string.valueof
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> taustiņš) {> >prev = temp;> >temp = temp->pa kreisi;> >}> >else> if> (temp->val prev = temp; temp = temp->pa labi; } } if (iepriekšējais->val> taustiņš) prev->left = mezgls; else prev->right = mezgls; } // Lietderības funkcija, lai drukātu inorder traversal void inorder(Node* root) { Node* temp = root; kaudze st; while (temp != NULL || !st.empty()) { if (temp != NULL) { st.push(temp); temp = temp->pa kreisi; } else { temp = st.top(); st.pop(); cout ' '; temp = temp->pa labi; } } } // Draivera kods int main() { Node* root = NULL; ievietot(sakne, 30); ievietot(sakne, 50); ievietot(sakne, 15); ievietot(sakne, 20); ievietot(sakne, 10); ievietot(sakne, 40); ievietot(sakne, 60); // Funkcijas izsaukums, lai izdrukātu inorder traversal inorder(root); atgriezties 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>taustiņš) {> >prev = temp;> >temp = temp.left;> >}> >else> if> (temp.val prev = temp; temp = temp.right; } } if (prev.val>taustiņš) prev.left = mezgls; else prev.right = mezgls; } // Funkcija secības vērtības drukāšanai public void inorder() { Node temp = root; Stack kaudze = new Stack(); while (temp != null || !steck.isEmpty()) { if (temp != null) { steck.add(temp); temp = temp.left; } else { temp = kaudze.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>atslēga):> >prev>=> temp> >temp>=> temp.left> >elif>(temp.val prev = temp temp = temp.right if (prev.val>taustiņš): prev.left = node else: prev.right = node # Funkcija, lai izdrukātu BST def inorder(self) secības šķērsošanu: temp = self.root steck = [] while (temp != None or not (len() kaudze) == 0)): if (temp != Nav): stack.append(temp) temp = temp.left else: temp = kaudze.pop() print(str(temp.val) + ' ', end='') temp = temp.right if __name__ == '__main__': GFG.main([]) # Šo kodu nodrošina rastogik346.>> |
>
kā iegūt spēli balodis operētājsistēmā Android
// 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>taustiņš) {>>prev = temp;>>temp = temp.left;>>}>>else>if>(temp.val prev = temp; temp = temp.right; } } if (prev.val>taustiņš) prev.left = mezgls; else prev.right = mezgls; } // Funkcija, lai izdrukātu BST kārtas traversal public void inorder() { Node temp = root; Stack steck = new Stack(); while (temp != null || kaudze.Count != 0) { if (temp != null) { kaudze.Push(temp); temp = temp.left; } else { temp = kaudze.Pop(); Console.Write(temp.val + ' '); temp = temp.right; } } } } // Šo kodu sniedz 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>taustiņš) {>>prev = temp;>>temp = temp.left;>>}>else>if>(temp.val prev = temp; temp = temp.right; } } if (prev.val>taustiņš) prev.left = mezgls; else prev.right = mezgls; } // Funkcija secības vērtības drukāšanai inorder() { let temp = this.root; let kaudze = []; while (temp != null || kaudze.length> 0) { if (temp != null) { kaudze.push(temp); temp = temp.left; } else { temp = kaudze.pop(); console.log(temp.val + ' '); temp = temp.right; } } } } let tree = new BST(); koks.ievietot(30); koks.ievietot(50); koks.ievietot(15); koks.ievietot(20); koks.ievietot(10); koks.ievietot(40); koks.ievietot(60); koks.inorder(); // šo kodu nodrošina devendrasolunke>>>Izvade10 15 20 30 40 50 60>The laika sarežģītība no pasūtījuma šķērsošana ir O(n) , jo katrs mezgls tiek apmeklēts vienu reizi.
The Palīgtelpa ir O(n) , jo mēs izmantojam steku, lai saglabātu mezglus rekursijai.Saistītās saites:
- Binārās meklēšanas koka meklēšanas operācija
- Binārās meklēšanas koka dzēšanas darbība