Givet en BST , er opgaven at indsætte en ny node i denne BST .
Eksempel:
Indsættelse i binært søgetræ
Sådan indsætter du en værdi i et binært søgetræ:
En ny nøgle indsættes altid ved bladet ved at bibeholde egenskaben for det binære søgetræ. Vi begynder at søge efter en nøgle fra roden, indtil vi rammer en bladknude. Når en bladknude er fundet, tilføjes den nye knude som et underordnet bladknudepunkt. Nedenstående trin følges, mens vi forsøger at indsætte en node i et binært søgetræ:
- Kontroller den værdi, der skal indsættes (f.eks x ) med værdien af den aktuelle node (f.eks val ) vi er inde:
- Hvis x er mindre end val flytte til venstre undertræ.
- Ellers skal du flytte til højre undertræ.
- Når bladknuden er nået, indsæt x til højre eller venstre baseret på forholdet mellem x og bladknudepunktets værdi.
Følg nedenstående illustration for en bedre forståelse:
Illustration:
Indsættelse i BST
Indsættelse i BST
Indsættelse i BST
Indsættelse i BST
Indsættelse i BST
Indsættelse i binært søgetræ ved hjælp af rekursion:
Nedenfor er implementeringen af indsættelsesoperationen ved hjælp af rekursion.
C++14
c streng i array
// 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->højre = Indsæt(rod->højre, værdi);> >}> >else> if> (value data) {> >// Insert left node data, if the 'value'> >// to be inserted is smaller than 'root' node data.> >// Process left nodes.> >root->venstre = Indsæt(rod->venstre, værdi);> >}> >// 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->venstre);> >cout ' '; Inorder(root->højre); } // Driverkode int main() { BST b, *root = NULL; root = b.Indsæt(rod, 50); b.Indsæt(rod, 30); b.Indsæt(rod, 20); b.Indsæt(rod, 40); b.Indsæt(rod, 70); b.Indsæt(rod, 60); b.Indsæt(rod, 80); b.Inorder(rod); retur 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->nøgle = element;> >temp->venstre = temp->højre = NULL;> >return> temp;> }> // A utility function to do inorder traversal of BST> void> inorder(>struct> node* root)> {> >if> (root != NULL) {> >inorder(root->venstre);> >printf>(>'%d '>, root->nøgle);> >inorder(root->højre);> >}> }> // 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->venstre = indsæt(node->venstre, tast);> >else> if> (key>node->tast)> >node->højre = indsæt(node->højre, nøgle);> >// 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); // Returner (uændret) node pointer return root; } // Denne metode kalder hovedsageligt InorderRec() void inorder() { inorderRec(root); } // En hjælpefunktion til // at udføre inorder-gennemgang af BST void inorderRec(Node root) { if (root != null) { inorderRec(root.left); System.out.print(root.key + ' '); inorderRec(root.right); } } // Driver Code public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); /* Lad os oprette følgende BST 50 / 30 70 / / 20 40 60 80 */ tree.insert(50); træ.indsæt(30); træ.indsæt(20); træ.indsæt(40); træ.indsæt(70); træ.indsæt(60); træ.indsæt(80); // Udskriv inorder-gennemgang af BST-træet.inorder(); } } // Denne kode er bidraget af Ankur Narain Verma> |
fjederstøvle
>
>
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); // Returner (uændret) node pointer return root; } // Denne metode kalder hovedsageligt InorderRec() void inorder() { inorderRec(root); } // En hjælpefunktion til // at udføre inorder-gennemgang af BST void inorderRec(Node root) { if (root != null) { inorderRec(root.left); Console.Write(root.key + ' '); inorderRec(root.right); } } // Driver Code public static void Main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); /* Lad os oprette følgende BST 50 / 30 70 / / 20 40 60 80 */ tree.insert(50); træ.indsæt(30); træ.indsæt(20); træ.indsæt(40); træ.indsæt(70); træ.indsæt(60); træ.indsæt(80); // Udskriv inorder-gennemgang af BST-træet.inorder(); } } // Denne kode er bidraget af 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); // Returner (uændret) node pointer return root; } // Denne metode kalder hovedsageligt InorderRec()-funktionen inorder() { inorderRec(root); } // En hjælpefunktion til // at udføre inorder-gennemgang af BST-funktionen inorderRec(root) { if (root != null) { inorderRec(root.left); document.write(root.key+' '); inorderRec(root.right); } } // Driverkode /* Lad os oprette følgende BST 50 / 30 70 / / 20 40 60 80 */ insert(50); indsæt(30); indsæt(20); indsæt(40); indsæt(70); indsæt(60); indsæt (80); // Udskriv inordergennemgang af BST inorder(); // Denne kode er bidraget af Rajput-Ji> |
>
>Produktion
20 30 40 50 60 70 80>
Tidskompleksitet:
- Den værst tænkelige tidskompleksitet af indsatsoperationer er O(h) hvor h er højden af det binære søgetræ.
- I værste fald kan vi blive nødt til at rejse fra roden til den dybeste bladknude. Højden af et skævt træ kan blive n og tidskompleksiteten af indsættelsesoperationen kan blive På).
Hjælpeplads: Hjælperen plads kompleksiteten af indsættelse i et binært søgetræ er O(1)
Indsættelse i binært søgetræ ved hjælp af iterativ tilgang:
I stedet for at bruge rekursion kan vi også implementere indsættelsesoperationen iterativt ved hjælp af en mens loop . Nedenfor er implementeringen ved hjælp af en while-løkke.
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> nøgle) {> >prev = temp;> >temp = temp->venstre;> >}> >else> if> (temp->val prev = temp; temp = temp->right; } } if (prev->val> key) prev->left = node; else prev->right = node; } // Hjælpefunktion til at udskrive inorder traversal void inorder(Node* root) { Node* temp = root; stak st; while (temp != NULL || !st.empty()) { if (temp != NULL) { st.push(temp); temp = temp->venstre; } andet { temp = st.top(); st.pop(); cout ' '; temp = temp->right; } } } // Driverkode int main() { Node* root = NULL; indsæt(rod, 30); indsæt(rod, 50); indsæt(rod, 15); indsæt(rod, 20); indsæt(rod, 10); indsæt(rod, 40); indsætte(rod, 60); // Funktionskald for at udskrive inorder traversal inorder(root); retur 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>nøgle) {> >prev = temp;> >temp = temp.left;> >}> >else> if> (temp.val prev = temp; temp = temp.right; } } if (prev.val>key) prev.left = node; else prev.right = node; } // Funktion til at udskrive inorder-værdien public void inorder() { Node temp = root; Stak stak = ny stak(); while (temp != null || !stack.isEmpty()) { if (temp != null) { stack.add(temp); temp = temp.venstre; } andet { 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>nøgle):> >prev>=> temp> >temp>=> temp.left> >elif>(temp.val prev = temp temp = temp.right if (prev.val>key): prev.left = node else: prev.right = node # Funktion til at udskrive inorder-gennemgangen af BST def inorder(self): temp = self.root stack = [] while (temp != Ingen eller ej (len( stack) == 0)): if (temp != Ingen): stack.append(temp) temp = temp.left else: temp = stack.pop() print(str(temp.val) + ' ', end='') temp = temp.right if __name__ == '__main__': GFG.main([]) # Denne kode er bidraget af rastogik346.> |
>
>
C#
10 ml er hvor meget
// 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>nøgle) {> >prev = temp;> >temp = temp.left;> >}> >else> if> (temp.val prev = temp; temp = temp.right; } } if (prev.val>key) prev.left = node; else prev.right = node; } // Funktion til at udskrive inorder-gennemgangen af BST public void inorder() { Node temp = root; Stak stak = ny stak(); while (temp != null || stack.Count != 0) { if (temp != null) { stack.Push(temp); temp = temp.venstre; } andet { temp = stack.Pop(); Console.Write(temp.val + ' '); temp = temp.right; } } } } // Denne kode er bidraget af 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>nøgle) {> >prev = temp;> >temp = temp.left;> >}>else> if> (temp.val prev = temp; temp = temp.right; } } if (prev.val>key) prev.left = node; else prev.right = node; } // Funktion til at udskrive inorder-værdien inorder() { let temp = this.root; lad stable = []; while (temp != null || stack.length> 0) { if (temp != null) { stack.push(temp); temp = temp.venstre; } andet { temp = stack.pop(); console.log(temp.val + ' '); temp = temp.right; } } } } lad træ = ny BST(); træ.indsæt(30); træ.indsæt(50); træ.indsæt(15); træ.indsæt(20); træ.indsæt(10); træ.indsæt(40); træ.indsæt(60); træ.inorder(); // denne kode er bidraget af devendrasolunke> |
>
>Produktion
10 15 20 30 40 50 60>
Det tidskompleksitet af gennemkørsel af uorden er På) , da hver node besøges én gang.
Det Hjælpeplads er På) , da vi bruger en stak til at gemme noder til rekursion.
Relaterede links:
- Binær søgetræssøgningsoperation
- Binær søgetræ Slet operation