Vzhľadom na a BST , úlohou je vložiť do toho nový uzol BST .
Príklad:
Vloženie do binárneho vyhľadávacieho stromu
Ako vložiť hodnotu do stromu binárneho vyhľadávania:
Nový kľúč sa vždy vloží do listu zachovaním vlastnosti binárneho vyhľadávacieho stromu. Začneme hľadať kľúč od koreňa, kým nenarazíme na listový uzol. Po nájdení listového uzla sa nový uzol pridá ako potomok listového uzla. Pri pokuse o vloženie uzla do binárneho vyhľadávacieho stromu sa postupujú podľa nasledujúcich krokov:
- Skontrolujte hodnotu, ktorá sa má vložiť (napr X ) s hodnotou aktuálneho uzla (povedzme val ) sme v tom:
- Ak X je menej než val prejdite do ľavého podstromu.
- V opačnom prípade sa presuňte do pravého podstromu.
- Po dosiahnutí uzla listu vložte X vpravo alebo vľavo na základe vzťahu medzi X a hodnotu listového uzla.
Pre lepšie pochopenie postupujte podľa nasledujúceho obrázku:
Ilustrácia:
Vloženie do BST
Vloženie do BST
Vloženie do BST
Vloženie do BST
Vloženie do BST
Vloženie do stromu binárneho vyhľadávania pomocou rekurzie:
Nižšie je uvedená implementácia operácie vkladania pomocou rekurzie.
C++14
0,06 ako zlomok
// 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->vľavo);> >cout ' '; Inorder(root->správny); } // Kód ovládača int main() { BST b, *root = NULL; root = b.Insert(root, 50); b.Vložiť(koreň, 30); b.Vložiť(koreň, 20); b.Vložiť(koreň, 40); b.Vložiť(koreň, 70); b.Vložiť(koreň, 60); b.Vložiť(koreň, 80); b.Inorder(root); návrat 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->kľúč = položka;> >temp->vľavo = teplota->vpravo = NULL;> >return> temp;> }> // A utility function to do inorder traversal of BST> void> inorder(>struct> node* root)> {> >if> (root != NULL) {> >inorder(root->vľavo);> >printf>(>'%d '>, root->kľúč);> >inorder(root->vpravo);> >}> }> // 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->left = insert(node->left, key);> >else> if> (key>uzol->kľúč)> >node->vpravo = vložiť(uzol->vpravo, kľúč);> >// 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); // Vráti (nezmenený) ukazovateľ uzla return root; } // Táto metóda volá hlavne InorderRec() void inorder() { inorderRec(root); } // Pomocná funkcia na // vykonanie prechodu BST podľa poradia void inorderRec(koreň uzla) { if (root != null) { inorderRec(root.left); System.out.print(root.key + ' '); inorderRec(root.right); } } // Kód ovládača public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); /* Vytvorme nasledujúci 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); // Vypíše prechod podľa poradia stromu BST.inorder(); } } // Tento kód pridal Ankur Narain Verma> |
javascriptové výstražné pole
>
>
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); // Vráti (nezmenený) ukazovateľ uzla return root; } // Táto metóda volá hlavne InorderRec() void inorder() { inorderRec(root); } // Pomocná funkcia na // vykonanie prechodu BST podľa poradia void inorderRec(koreň uzla) { if (root != null) { inorderRec(root.left); Console.Write(root.key + ' '); inorderRec(root.right); } } // Kód ovládača public static void Main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); /* Vytvorme nasledujúci 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); // Vypíše prechod podľa poradia stromu BST.inorder(); } } // Tento kód prispel 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); // Vráti (nezmenený) ukazovateľ uzla return root; } // Táto metóda volá hlavne funkciu InorderRec() inorder() { inorderRec(root); } // Pomocná funkcia na // vykonanie prechodu BST funkciou inorderRec(root) { if (root != null) { inorderRec(root.left); document.write(root.key+' '); inorderRec(root.right); } } // Kód ovládača /* Vytvorme nasledujúci BST 50 / 30 70 / / 20 40 60 80 */ insert(50); vložku (30); vložiť(20); vložku (40); vložku (70); vložku (60); vložku (80); // Vytlačí prechod BST inorder(); // Tento kód prispel Rajput-Ji> |
>
>Výkon
20 30 40 50 60 70 80>
Časová zložitosť:
- Najhorší prípad časovej zložitosti operácií vkladania je O(h) kde h je výška binárneho vyhľadávacieho stromu.
- V najhoršom prípade možno budeme musieť cestovať od koreňa až po najhlbší listový uzol. Výška skoseného stromu môže byť n a môže sa stať časová zložitosť operácie vkladania O(n).
Pomocný priestor: Pomocník priestorová zložitosť vkladania do binárneho vyhľadávacieho stromu je O(1)
Vkladanie do stromu binárneho vyhľadávania pomocou iteratívneho prístupu:
Namiesto použitia rekurzie môžeme operáciu vkladania implementovať aj iteračne pomocou a pričom slučka . Nižšie je uvedená implementácia pomocou cyklu while.
vlk verzus líška
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> kľúč) {> >prev = temp;> >temp = temp->vľavo;> >}> >else> if> (temp->val prev = teplota; temp = temp->vpravo; } } if (prev->val> key) prev->left = uzol; else prev->right = uzol; } // Pomôcka funkcia na vytlačenie prechodu poradia void inorder(Node* root) { Node* temp = root; stack st; while (temp != NULL || !st.empty()) { if (temp != NULL) { st.push(temp); temp = temp->left; } else { temp = st.top(); st.pop(); cout ' '; temp = temp->vpravo; } } } // Kód ovládača int main() { Uzol* root = NULL; vložiť(koreň, 30); vložiť(koreň, 50); vložiť(koreň, 15); vložiť(koreň, 20); vložiť(koreň, 10); vložiť(koreň, 40); vložiť(koreň, 60); // Volanie funkcie na vypis inorder traversal inorder(root); návrat 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>kľúč) {> >prev = temp;> >temp = temp.left;> >}> >else> if> (temp.val prev = temp; temp = temp.right; } } if (prev.val>key) prev.left = uzol; else prev.right = uzol; } // Funkcia na vypísanie hodnoty poradia public void inorder() { Node temp = root; Zásobník = nový Zásobník(); 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>kľúč):> >prev>=> temp> >temp>=> temp.left> >elif>(temp.val prev = temp temp = temp.right if (prev.val>kľúč): prev.left = uzol else: prev.right = node # Funkcia na vytlačenie prechodu poradia BST def 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([]) # Tento kód prispel rastogik346.> |
>
>
C#
java je prázdna
// 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>kľúč) {> >prev = temp;> >temp = temp.left;> >}> >else> if> (temp.val prev = temp; temp = temp.right; } } if (prev.val>key) prev.left = uzol; else prev.right = uzol; } // Funkcia na vypísanie prechodu poradia BST public void inorder() { Node temp = root; Zásobník = nový Zásobník(); 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; } } } } // Tento kód prispel 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>kľúč) {> >prev = temp;> >temp = temp.left;> >}>else> if> (temp.val prev = temp; temp = temp.right; } } if (prev.val>key) prev.left = uzol; else prev.right = uzol; } // Funkcia na vypísanie hodnoty poradia inorder() { let temp = this.root; nech stack = []; 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; } } } } nech strom = new BST(); tree.insert(30); tree.insert(50); strom.vložiť(15); tree.insert(20); tree.insert(10); tree.insert(40); tree.insert(60); strom.inorder(); // tento kód prispel devendrasolunke> |
>
>Výkon
10 15 20 30 40 50 60>
The časová zložitosť z neriadený prechod je O(n) , pretože každý uzol je navštívený raz.
The Pomocný priestor je O(n) , keďže na ukladanie uzlov pre rekurziu používame zásobník.
Súvisiace odkazy:
- Operácia vyhľadávania v binárnom vyhľadávacom strome
- Operácia odstránenia binárneho vyhľadávacieho stromu