Având în vedere a BST , sarcina este să inserați un nou nod în acesta BST .

Exemplu:

Inserarea în arborele binar de căutare

Cum să inserați o valoare într-un arbore binar de căutare:

O cheie nouă este întotdeauna inserată la frunză prin menținerea proprietății arborelui binar de căutare. Începem să căutăm o cheie de la rădăcină până când lovim un nod frunză. Odată ce este găsit un nod frunză, noul nod este adăugat ca un copil al nodului frunză. Pașii de mai jos sunt urmați în timp ce încercăm să inserăm un nod într-un arbore de căutare binar:

• Verificați valoarea de inserat (să zicem X ) cu valoarea nodului curent (să zicem val ) noi suntem in:
  • Dacă X e mai puțin decât val mutați în subarborele din stânga.
  • În caz contrar, treceți la subarborele din dreapta.
• Odată ce nodul frunzei este atins, introduceți X la dreapta sau la stânga ei în funcție de relația dintre X și valoarea nodului frunză.

Urmați ilustrația de mai jos pentru o mai bună înțelegere:

Ilustrare:

Inserarea în BST

Inserarea în BST

Inserarea în BST

Inserarea în BST

Inserarea în BST

Inserarea în arborele de căutare binar folosind recursiunea:

Mai jos este implementarea operației de inserare folosind recursiunea.

C++14

imagine de reducere

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // 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->cheie = element;> >temp->stânga = temp->dreapta = NULL;> >return> temp;> }> // A utility function to do inorder traversal of BST> void> inorder(>struct> node* root)> {> >if> (root != NULL) {> >inorder(root->stânga);> >printf>(>'%d '>, root->cheie);> >inorder(root->dreapta);> >}> }> // 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->stânga = insert(nod->stânga, cheie);> >else> if> (key>nod->cheie)> >node->dreapta = insert(nod->dreapta, cheie);> >// 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);  // Returnează indicatorul de nod (neschimbat) returnează rădăcina;  } // Această metodă apelează în principal InorderRec() void inorder() { inorderRec(root); } // O funcție utilitar pentru // face traversarea în ordine a BST void inorderRec(Rădăcină nod) { if (rădăcină != null) { inorderRec(rădăcină.stânga);  System.out.print(root.key + ' ');  inorderRec(root.right);  } } // Cod driver public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree();  /* Să creăm următorul BST 50 /  30 70 /  /  20 40 60 80 */ tree.insert(50);  arbore.inserare(30);  tree.insert(20);  arbore.inserare(40);  arbore.inserare(70);  arbore.inserare(60);  tree.insert(80);  // Imprimă parcurgerea în ordine a arborelui BST.inorder();  } } // Acest cod este contribuit de Ankur Narain Verma>
 
 
 
 
python generează uuid
    
 
>
 
    
 
>
 
 
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);  // Returnează indicatorul de nod (neschimbat) returnează rădăcina;  } // Această metodă apelează în principal InorderRec() void inorder() { inorderRec(root); } // O funcție utilitar pentru // face traversarea în ordine a BST void inorderRec(Rădăcină nod) { if (rădăcină != null) { inorderRec(rădăcină.stânga);  Console.Write(root.key + ' ');  inorderRec(root.right);  } } // Cod driver public static void Main(String[] args) { BinarySearchTree tree = new BinarySearchTree();  /* Să creăm următorul BST 50 /  30 70 /  /  20 40 60 80 */ tree.insert(50);  arbore.inserare(30);  tree.insert(20);  arbore.inserare(40);  arbore.inserare(70);  arbore.inserare(60);  tree.insert(80);  // Imprimă parcurgerea în ordine a arborelui BST.inorder();  } } // Acest cod este contribuit de aashish1995>>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 > // 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);  // Returnează indicatorul de nod (neschimbat) returnează rădăcina;  } // Această metodă apelează în principal funcția InorderRec() inorder() { inorderRec(root);  } // O funcție de utilitate pentru // face traversarea în ordine a funcției BST inorderRec(rădăcină) { if (rădăcină != null) { inorderRec(rădăcină.stânga);  document.write(root.key+' ');  inorderRec(root.right);  } } // Cod driver /* Să creăm următorul BST 50 /  30 70 /  /  20 40 60 80 */ insert(50);  insert (30);  insert (20);  insert (40);  insert (70);  insert (60);  insert (80);  // Print inorder traversarea BST inorder(); // Acest cod este contribuit de Rajput-Ji>>>
 
 
 
 
    
 
> 
    
 20 30 40 50 60 70 80>
 
    Complexitatea timpului:    
 
 
Cel mai rău caz de complexitate de timp a operațiunilor de inserare este    Oh)    Unde    h    este înălțimea arborelui de căutare binar.
 
În cel mai rău caz, poate fi necesar să călătorim de la rădăcină la cel mai adânc nod al frunzei. Înălțimea unui copac înclinat poate deveni    n    iar complexitatea timpului operaţiei de inserare poate deveni    Pe).    
 
 
    Spațiu auxiliar:    Asistentul         complexitatea spațială a inserării într-un arbore de căutare binar este    O(1)    
 
    Inserarea în Arborele de căutare binar folosind abordarea iterativă:     
 
În loc să folosim recursiunea, putem implementa și operația de inserare în mod iterativ folosind a    buclă while    . Mai jos este implementarea folosind o buclă while.
derivat parțial latex
 
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> cheie) {> >prev = temp;> >temp = temp->stânga;> >}> >else> if> (temp->val prev = temp;  temp = temp->dreapta;  } } if (prev->val> key) prev->left = nod;  else prev->right = nod; } // Funcție utilitar pentru a imprima în ordine traversal void inorder(Node* rădăcină) { Nod* temp = rădăcină;  stivă st;  while (temp != NULL || !st.empty()) { if (temp != NULL) { st.push(temp);  temp = temp->stânga;  } else { temp = st.top();  st.pop();  cout ' ';  temp = temp->dreapta;  } } } // Cod driver int main() { Nod* root = NULL;  insert (rădăcină, 30);  insert (rădăcină, 50);  insert (rădăcină, 15);  insert (rădăcină, 20);  insert (rădăcină, 10);  insert (rădăcină, 40);  insert (rădăcină, 60);  // Apel de funcție pentru a imprima traversarea inorder inorder(root);  întoarce 0; }>>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // 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>cheie) {> >prev = temp;> >temp = temp.left;> >}> >else> if> (temp.val   prev = temp;  temp = temp.right;  }  }  if (prev.val>cheie) prev.left = nod;  else prev.right = nod;  } // Funcție de tipărire a valorii inorder public void inorder() { Node temp = root;  Stack stack = new Stack();  while (temp != null || !stack.isEmpty()) { if (temp != null) { stack.add(temp);  temp = temp.stânga;  } else { temp = stack.pop();  System.out.print(temp.val + ' ');  temp = temp.dreapta;  } } } }>>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # 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>cheie):> >prev>=> temp> >temp>=> temp.left> >elif>(temp.val   prev = temp  temp = temp.right  if (prev.val>cheie): prev.left = nod else: prev.right = nod # Funcție pentru a imprima traversarea în ordine a BST def inorder(self): temp = self.root stack = [] while (temp != Niciunul sau nu (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([]) # Acest cod este contribuit de rastogik346.>>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
vikas divyakirti
 
     
     
    
 
 
 
 
 
 // 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>cheie) {> >prev = temp;> >temp = temp.left;> >}> >else> if> (temp.val   prev = temp;  temp = temp.right;  }  }  if (prev.val>cheie) prev.left = nod;  else prev.right = nod;  } // Funcție pentru a imprima traversarea în ordine a BST public void inorder() { Node temp = root;  Stack stack = new Stack();  while (temp != null || stack.Count != 0) { if (temp != null) { stack.Push(temp);  temp = temp.stânga;  } else { temp = stack.Pop();  Consola.Scrie(temp.val + ' ');  temp = temp.dreapta;  } } } } // Acest cod este contribuit de Rajput-Ji>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // 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>cheie) {> >prev = temp;> >temp = temp.left;> >}>else> if> (temp.val   prev = temp;  temp = temp.right;  }  }  if (prev.val>cheie) prev.left = nod;  else prev.right = nod;  } // Funcție de tipărire a valorii inorder inorder() { let temp = this.root;  lasă stiva = [];  while (temp != null || stack.length> 0) { if (temp != null) { stack.push(temp);  temp = temp.stânga;  } else { temp = stack.pop();  console.log(temp.val + ' ');  temp = temp.dreapta;  } } } } let tree = new BST(); arbore.inserare(30); arbore.inserare(50); arbore.inserare(15); tree.insert(20); tree.insert(10); arbore.inserare(40); arbore.inserare(60); arbore.inorde(); // acest cod este contribuit de devendrasolunke>
 
 
 
 
    
 
>
 
    
 
>
 
  Ieșire  
 
10 15 20 30 40 50 60>
 
The    complexitatea timpului    de    traversare în ordine    este    Pe)    , deoarece fiecare nod este vizitat o dată.  
The    Spațiu auxiliar    este    Pe)    , deoarece folosim o stivă pentru a stoca noduri pentru recursivitate.
 
    Linkuri conexe:    
 
 
  Operația de căutare binară în arborele de căutare  
 
 Operația de ștergere a arborelui de căutare binar