ВСТАВКА В БІНАРНЕ ДЕРЕВО ПОШУКУ (BST)

Враховуючи а BST , завдання полягає в тому, щоб вставити в це новий вузол BST .

приклад:

Вставка в бінарне дерево пошуку

Як вставити значення в бінарне дерево пошуку:

Новий ключ завжди вставляється на аркуші шляхом збереження властивості бінарного дерева пошуку. Ми починаємо пошук ключа з кореня, поки не натрапимо на листовий вузол. Після того, як кінцевий вузол знайдено, новий вузол додається як дочірній елемент листового вузла. Наведені нижче кроки виконуються під час спроби вставити вузол у бінарне дерево пошуку:

Перевірте значення, яке потрібно вставити (скажімо X ) зі значенням поточного вузла (скажімо вал ) ми всередині:
- Якщо X менше ніж вал перейти до лівого піддерева.
- В іншому випадку перейдіть до правого піддерева.
Досягнувши листового вузла, вставте X праворуч або ліворуч залежно від співвідношення між X і значення листового вузла.

Для кращого розуміння дотримуйтесь ілюстрації нижче:

Ілюстрація:

Вставка в BST

Вставка в BST

Вставка в BST

Вставка в BST

Вставка в BST

Вставка в бінарне дерево пошуку за допомогою рекурсії:

Нижче наведено реалізацію операції вставки за допомогою рекурсії.

C++14

// 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->right = Insert(root->right, value);> > }> > else> if> (value data) {> > // Insert left node data, if the 'value'> > // to be inserted is smaller than 'root' node data.> > // Process left nodes.> > root->left = 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->ліворуч);> >

cout ' ';  Inorder(root->праворуч); } // Код драйвера int main() { BST b, *root = NULL;  корінь = b.Insert(корінь, 50);  b.Insert(корінь, 30);  b.Insert(корінь, 20);  b.Insert(корінь, 40);  b.Insert(корінь, 70);  b.Insert(корінь, 60);  b.Insert(корінь, 80);  b.Inorder(корінь);  повернути 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->ключ = елемент;> > temp->лівий = temp->right = NULL;> > return> temp;> }> // A utility function to do inorder traversal of BST> void> inorder(> struct> node* root)> {> > if> (root != NULL) {> > inorder(root->ліворуч);> > printf> (> '%d '> , root->ключ);>> > inorder(root->правильно);> > }> }> // 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->ліворуч = вставити (вузол->ліворуч, клавіша);> > else> if> (key>вузол->ключ)> > node->праворуч = вставити (вузол->праворуч, ключ);> > // 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, ключ);  // Повертає (незмінений) покажчик вузла return root;  } // Цей метод переважно викликає InorderRec() void inorder() { inorderRec(root); } // Допоміжна функція для // обходу BST у порядку void inorderRec(Node root) { if (root != null) { inorderRec(root.left);  System.out.print(root.key + ' ');  inorderRec(root.right);  } } // Код драйвера public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree();  /* Створимо наступний 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);  // Друк обходу в порядку BST tree.inorder();  } } // Цей код створено Анкуром Нараїном Вермою>

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, ключ);  // Повертає (незмінений) покажчик вузла return root;  } // Цей метод переважно викликає InorderRec() void inorder() { inorderRec(root); } // Допоміжна функція для // обходу BST у порядку void inorderRec(Node root) { if (root != null) { inorderRec(root.left);  Console.Write(root.key + ' ');  inorderRec(root.right);  } } // Код драйвера public static void Main(String[] args) { BinarySearchTree tree = new BinarySearchTree();  /* Створимо наступний 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);  // Друк обходу в порядку BST tree.inorder();  } } // Цей код створено 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, ключ);  // Повертає (незмінений) покажчик вузла return root;  } // Цей метод переважно викликає функцію InorderRec() inorder() { inorderRec(root);  } // Допоміжна функція для // обходу BST у порядку inorderRec(root) { if (root != null) { inorderRec(root.left);  document.write(root.key+' ');  inorderRec(root.right);  } } // Код драйвера /* Створимо наступний BST 50 /  30 70 /  /  20 40 60 80 */ insert(50);  вставка(30);  вставити (20);  вставка (40);  вставка(70);  вставка (60);  вставка (80);  // Друк обходу BST inorder(); // Цей код надано Rajput-Ji>>>

>    
      
      Часова складність:     
     Найгірша часова складність операцій вставки     O(h)     де     ч     це висота бінарного дерева пошуку.  
   У гіршому випадку нам, можливо, доведеться подорожувати від кореня до найглибшого вузла листа. Висота перекошеного дерева може стати     п     і часова складність операції вставки може стати     O(n).     
  
      Допоміжний простір:     Допоміжний           просторова складність вставки в бінарне дерево пошуку становить     О(1)     
      Вставка в бінарне дерево пошуку за допомогою ітераційного підходу:        
   Замість використання рекурсії ми також можемо реалізувати операцію вставки ітеративно за допомогою a     цикл while     . Нижче наведено реалізацію з використанням циклу while.  
  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> ключ) {>   >  prev = temp;>   >  temp = temp->вліво;>   >  }>   >  else>   if>   (temp->val prev = temp;  temp = temp->праворуч;  } } if (prev->val> ключ) prev->left = вузол;  else prev->right = вузол; } // Службова функція для друку обходу в порядку void inorder(Node* root) { Node* temp = root;  стек st;  while (temp != NULL || !st.empty()) { if (temp != NULL) { st.push(temp);  temp = temp->left;  } else { temp = st.top();  st.pop();  cout ' ';  temp = temp->праворуч;  } } } // Код драйвера int main() { Node* root = NULL;  вставити (корінь, 30);  вставити (корінь, 50);  вставити (корінь, 15);  вставити (корінь, 20);  вставити (корінь, 10);  вставити (корінь, 40);  вставити (корінь, 60);  // Виклик функції для друку обходу порядку inorder(root);  повернути 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>ключ) {>   >  prev = temp;>   >  temp = temp.left;>   >  }>   >  else>   if>   (temp.val   prev = temp;  temp = temp.right;  }  }  if (prev.val>ключ) prev.left = вузол;  else prev.right = вузол;  } // Функція друку значення inorder public void inorder() { Node temp = root;  Стек стек = новий стек();  while (temp != null || !stack.isEmpty()) { if (temp != null) { stack.add(temp);  temp = temp.left;  } else { temp = stack.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>ключ):>>   >  prev>  =>   temp>   >  temp>  =>   temp.left>   >  elif>  (temp.val   prev = temp  temp = temp.right  if (prev.val>ключ): prev.left = node else: prev.right = node # Функція для друку обходу BST у порядку inorder(self): temp = self.root stack = [] while (temp != None or not (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([]) # Цей код створено rastogik346.>    
  
  
   
      
    
      
    
  C# 
      
       
   
       
       
     
     
   
          // 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>ключ) {>   >  prev = temp;>   >  temp = temp.left;>   >  }>   >  else>   if>   (temp.val   prev = temp;  temp = temp.right;  }  }  if (prev.val>ключ) prev.left = вузол;  else prev.right = вузол;  } // Функція друку обходу за порядком BST public void inorder() { Node temp = root;  Стек стек = новий стек();  while (temp != null || stack.Count != 0) { if (temp != null) { stack.Push(temp);  temp = temp.left;  } else { temp = stack.Pop();  Console.Write(temp.val + ' ');  temp = temp.right;  } } } } // Цей код створено 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>ключ) {>   >  prev = temp;>   >  temp = temp.left;>   >  }>  else>   if>   (temp.val   prev = temp;  temp = temp.right;  }  }  if (prev.val>ключ) prev.left = вузол;  else prev.right = вузол;  } // Функція друку значення inorder inorder() { let temp = this.root;  нехай стек = [];  while (temp != null || stack.length> 0) { if (temp != null) { stack.push(temp);  temp = temp.left;  } else { temp = stack.pop();  console.log(temp.val + ' ');  temp = temp.right;  } } } } 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); tree.inorder(); // цей код надано devendrasolunke>    
  
  
   
      
    
      
    
  Вихід    
  10 15 20 30 40 50 60 
   The     часова складність     з     непорядковий обхід     є     O(n)     , оскільки кожен вузол відвідується один раз.   
 The     Допоміжне приміщення     є     O(n)     , оскільки ми використовуємо стек для зберігання вузлів для рекурсії.  
      Пов'язані посилання:     
       Операція пошуку в дереві бінарного пошуку    
    Операція видалення бінарного дерева пошуку