Donat a BST , la tasca és inserir-hi un nou node BST .

Exemple:

Inserció a l'arbre de cerca binari

Com inserir un valor en un arbre de cerca binari:

Sempre s'insereix una clau nova a la fulla mantenint la propietat de l'arbre de cerca binari. Comencem a buscar una clau des de l'arrel fins que arribem a un node fulla. Un cop es troba un node full, el nou node s'afegeix com a fill del node full. Els passos següents se segueixen mentre intentem inserir un node en un arbre de cerca binari:

• Comproveu el valor a inserir (per exemple X ) amb el valor del node actual (per exemple val ) estem a:
  • Si X és menys que val moveu-vos al subarbre esquerre.
  • En cas contrari, moveu-vos al subarbre dret.
• Un cop arribat al node de la fulla, inseriu-lo X a la seva dreta o esquerra en funció de la relació entre X i el valor del node fulla.

Seguiu la il·lustració següent per a una millor comprensió:

Il·lustració:

Inserció en BST

Inserció en BST

Inserció en BST

Inserció en BST

Inserció en BST

Inserció a l'arbre de cerca binari mitjançant recursivitat:

A continuació es mostra la implementació de l'operació d'inserció mitjançant recursivitat.

C++14

alineació de text css

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // 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->clau = element;> >temp->esquerra = temp->dreta = NULL;> >return> temp;> }> // A utility function to do inorder traversal of BST> void> inorder(>struct> node* root)> {> >if> (root != NULL) {> >inorder(root->esquerra);> >printf>(>'%d '>, root->clau);> >inorder(root->dreta);> >}> }> // 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->esquerra = inserir (node->esquerra, clau);> >else> if> (key>node->clau)> >node->dreta = inserir (node->dreta, clau);> >// 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, clau);  // Retorna l'arrel de retorn del punter del node (no canviat);  } // Aquest mètode crida principalment a InorderRec() void inorder() { inorderRec(arrel); } // Una funció d'utilitat per // fer un recorregut en ordre de BST void inorderRec(arrel del node) { if (arrel != nul) { inorderRec(arrel.esquerra);  System.out.print(clau.arrel + ' ');  inorderRec(arrel.dreta);  } } // Codi del controlador public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree ();  /* Creem el següent 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);  // Imprimeix el recorregut en ordre de l'arbre BST.inorder();  } } // Aquest codi és aportat per Ankur Narain Verma>>>
 
 
 
 
matrius bash
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # 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, clau);  // Retorna l'arrel de retorn del punter del node (no canviat);  } // Aquest mètode crida principalment a InorderRec() void inorder() { inorderRec(arrel); } // Una funció d'utilitat per // fer un recorregut en ordre de BST void inorderRec(arrel del node) { if (arrel != nul) { inorderRec(arrel.esquerra);  Console.Write(root.key + ' ');  inorderRec(arrel.dreta);  } } // Codi del controlador public static void Main(String[] args) { BinarySearchTree tree = new BinarySearchTree ();  /* Creem el següent 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);  // Imprimeix el recorregut en ordre de l'arbre BST.inorder();  } } // Aquest codi és aportat per 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, clau);  // Retorna l'arrel de retorn del punter del node (no canviat);  } // Aquest mètode crida principalment a la funció InorderRec() inorder() { inorderRec(arrel);  } // Una funció d'utilitat per // fer un recorregut en ordre de la funció BST inorderRec(root) { if (root != null) { inorderRec(root.left);  document.write(root.key+' ');  inorderRec(arrel.dreta);  } } // Codi del controlador /* Creem el següent BST 50 /  30 70 /  /  20 40 60 80 */ insert(50);  inserir (30);  inserir (20);  inserir (40);  inserir (70);  inserir (60);  inseriu (80);  // Imprimeix el recorregut inorder del BST inorder(); // Aquest codi és aportat per Rajput-Ji>>>
 
 
 
 
    
 
> 
    
 20 30 40 50 60 70 80>
 
    Complexitat temporal:    
 
 
La complexitat temporal de les operacions d'inserció en el pitjor dels casos és    O(h)    on    h    és l'alçada de l'arbre de cerca binari.
 
En el pitjor dels casos, potser haurem de viatjar des de l'arrel fins al node foliar més profund. L'alçada d'un arbre esbiaixat pot arribar a ser    n    i la complexitat temporal de l'operació d'inserció pot arribar a ser    O(n).    
 
 
    Espai auxiliar:    L'auxiliar         La complexitat espacial d'inserció en un arbre de cerca binari és    O(1)    
 
    Inserció a l'arbre de cerca binari mitjançant un enfocament iteratiu:     
 
En lloc d'utilitzar recursivitat, també podem implementar l'operació d'inserció de manera iterativa mitjançant a    bucle while    . A continuació es mostra la implementació mitjançant un bucle while.
guineu vs llop
 
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> clau) {> >prev = temp;> >temp = temp->esquerra;> >}> >else> if> (temp->val prev = temp;  temp = temp->dreta;  } } if (prev->val> clau) prev->left = node;  else prev->right = node; } // Funció d'utilitat per imprimir inorder traversal void inorder (Node* arrel) { Node* temp = arrel;  apilar st;  while (temp != NULL || !st.empty()) { if (temp != NULL) { st.push(temp);  temp = temp->esquerra;  } else { temp = st.top();  st.pop();  cout ' ';  temp = temp->dreta;  } } } // Codi del controlador int main() { Node* arrel = NULL;  inserir (arrel, 30);  inserir (arrel, 50);  inserir (arrel, 15);  inserir (arrel, 20);  inserir (arrel, 10);  inserir (arrel, 40);  inserir (arrel, 60);  // Crida a la funció per imprimir el recorregut inorder inorder(root);  retorn 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>clau) {> >prev = temp;> >temp = temp.left;> >}> >else> if> (temp.val   prev = temp;  temp = temp.right;  }  }  if (prev.val>clau) prev.left = node;  else prev.right = node;  } // Funció per imprimir el valor de l'ordre public void inorder() { Node temp = root;  Stack stack = new Stack();  while (temp != null || !stack.isEmpty()) { if (temp != null) { stack.add(temp);  temp = temp.esquerra;  } else { temp = stack.pop();  System.out.print(temp.val + ' ');  temp = temp.right;  } } } }>>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # 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>clau):> >prev>=> temp> >temp>=> temp.left> >elif>(temp.val   prev = temp  temp = temp.right  if (prev.val>clau): prev.left = node else: prev.right = node # Funció per imprimir el recorregut en ordre de BST def inorder(self): temp = self.root stack = [] while (temp != Cap o no (len( stack) == 0)): if (temp != Cap): stack.append(temp) temp = temp.left else: temp = stack.pop() print(str(temp.val) + ' ', end='') temp = temp.right if __name__ == '__main__': GFG.main([]) # Aquest codi és aportat per rastogik346.>>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
entitat relacional
 
     
     
    
 
 
 
 
 
 // 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>clau) {> >prev = temp;> >temp = temp.left;> >}> >else> if> (temp.val   prev = temp;  temp = temp.right;  }  }  if (prev.val>clau) prev.left = node;  else prev.right = node;  } // Funció per imprimir el recorregut en ordre de 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.esquerra;  } else { temp = stack.Pop();  Console.Write(temp.val + ' ');  temp = temp.right;  } } } } // Aquest codi és aportat per 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>clau) {> >prev = temp;> >temp = temp.left;> >}>else> if> (temp.val   prev = temp;  temp = temp.right;  }  }  if (prev.val>clau) prev.left = node;  else prev.right = node;  } // Funció per imprimir el valor inorder inorder() { let temp = this.root;  deixar apilar = [];  while (temp != null || stack.length> 0) { if (temp != null) { stack.push(temp);  temp = temp.esquerra;  } else { temp = stack.pop();  console.log(temp.val + ' ');  temp = temp.dreta;  } } } } let tree = new BST(); tree.insert(30); tree.insert(50); tree.insert(15); tree.insert(20); tree.insert(10); tree.insert(40); tree.insert(60); arbre.inorde(); // aquest codi és aportat per devendrasolunke>
 
 
 
 
    
 
>
 
    
 
>
 
  Sortida  
 
10 15 20 30 40 50 60>
 
El    complexitat temporal    de    travessa en ordre    és    O(n)    , ja que cada node es visita una vegada.  
El    Espai auxiliar    és    O(n)    , ja que fem servir una pila per emmagatzemar nodes per a la recursivitat.
 
    Enllaços relacionats:    
 
 
  Operació de cerca en arbre de cerca binària  
 
 Operació d'eliminació de l'arbre de cerca binària