Dawać BST , zadaniem jest wstawienie do tego nowego węzła BST .
Przykład:
Wstawienie do drzewa wyszukiwania binarnego
Jak wstawić wartość do drzewa wyszukiwania binarnego:
Nowy klucz jest zawsze wstawiany do liścia, zachowując właściwość drzewa wyszukiwania binarnego. Zaczynamy szukać klucza od korzenia, aż trafimy na węzeł liścia. Po znalezieniu węzła liścia nowy węzeł jest dodawany jako element podrzędny węzła liścia. Podczas próby wstawienia węzła do drzewa wyszukiwania binarnego wykonywane są poniższe kroki:
- Sprawdź wartość, która ma zostać wstawiona (powiedzmy X ) z wartością bieżącego węzła (powiedzmy wal ) jesteśmy w:
- Jeśli X jest mniej niż wal przejdź do lewego poddrzewa.
- W przeciwnym razie przejdź do prawego poddrzewa.
- Po dotarciu do węzła liścia włóż X w prawo lub w lewo, w zależności od relacji pomiędzy X oraz wartość węzła liścia.
Aby lepiej zrozumieć, postępuj zgodnie z poniższą ilustracją:
Ilustracja:
Wstawienie do BST
Wstawienie do BST
Wstawienie do BST
Wstawienie do BST
Wstawienie do BST
Wstawianie do drzewa wyszukiwania binarnego przy użyciu rekurencji:
Poniżej znajduje się implementacja operacji wstawiania przy użyciu rekurencji.
C++14
operatory JavaScript
// 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->dane) {> >// Insert right node data, if the 'value'> >// to be inserted is greater than 'root' node data.> >// Process right nodes.> >root->prawo = Wstaw(root->prawo, wartość);> >}> >else> if> (value data) {> >// Insert left node data, if the 'value'> >// to be inserted is smaller than 'root' node data.> >// Process left nodes.> >root->lewy = Wstaw(root->lewy, wartość);> >}> >// 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->lewo);> >cout ' '; Inorder(root->Prawidłowy); } // Kod sterownika int main() { BST b, *root = NULL; root = b.Insert(root, 50); b.Insert(root, 30); b.Insert(root, 20); b.Insert(root, 40); b.Insert(root, 70); b.Insert(root, 60); b.Insert(root, 80); b.Inorder(root); zwróć 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->klucz = element;> >temp->lewy = temp->prawy = NULL;> >return> temp;> }> // A utility function to do inorder traversal of BST> void> inorder(>struct> node* root)> {> >if> (root != NULL) {> >inorder(root->lewo);> >printf>(>'%d '>, root->klucz);> >inorder(root->prawda);> >}> }> // 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->lewy = wstaw(węzeł->lewy, klawisz);> >else> if> (key>węzeł->klucz)> >node->prawo = wstaw(węzeł->prawo, klawisz);> >// 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;> }> |
>
>
Jawa
// 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 = wstawRec(root.right, klucz); // Zwraca (niezmieniony) wskaźnik węzła return root; } // Ta metoda wywołuje głównie funkcję InorderRec() void inorder() { inorderRec(root); } // Funkcja narzędziowa // wykonująca przechodzenie w kolejności BST void inorderRec(Node root) { if (root != null) { inorderRec(root.left); System.out.print(root.key + ' '); inorderRec(root.right); } } // Kod sterownika public static void main(String[] args) { Drzewo BinarySearchTree = nowe BinarySearchTree(); /* Utwórzmy następujące BST 50 / 30 70 / / 20 40 60 80 */ Tree.insert(50); drzewo.wstaw(30); drzewo.wstaw(20); drzewo.wstaw(40); drzewo.wstaw(70); drzewo.wstaw(60); drzewo.wstaw(80); // Wydrukuj przejście drzewa BST w kolejności.inorder(); } } // Ten kod został stworzony przez Ankura Naraina Vermę> |
25 ze 100
>
>
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 = wstawRec(root.right, klucz); // Zwraca (niezmieniony) wskaźnik węzła return root; } // Ta metoda wywołuje głównie funkcję InorderRec() void inorder() { inorderRec(root); } // Funkcja narzędziowa // wykonująca przechodzenie w kolejności BST void inorderRec(Node root) { if (root != null) { inorderRec(root.left); Console.Write(root.key + ' '); inorderRec(root.right); } } // Kod sterownika public static void Main(String[] args) { Drzewo BinarySearchTree = nowe BinarySearchTree(); /* Utwórzmy następujące BST 50 / 30 70 / / 20 40 60 80 */ Tree.insert(50); drzewo.wstaw(30); drzewo.wstaw(20); drzewo.wstaw(40); drzewo.wstaw(70); drzewo.wstaw(60); drzewo.wstaw(80); // Wydrukuj przejście drzewa BST w kolejności.inorder(); } } // Ten kod został stworzony przez 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 = wstawRec(root.right, klucz); // Zwraca (niezmieniony) wskaźnik węzła return root; } // Ta metoda wywołuje głównie funkcję InorderRec() inorder() { inorderRec(root); } // Funkcja narzędziowa // wykonująca przechodzenie w kolejności BST funkcja inorderRec(root) { if (root != null) { inorderRec(root.left); dokument.write(root.key+' '); inorderRec(root.right); } } // Kod sterownika /* Stwórzmy następujący BST 50 / 30 70 / / 20 40 60 80 */ wstaw(50); wstaw(30); wstaw(20); wstaw(40); wstaw(70); wstaw(60); wstaw(80); // Wydrukuj przejście w kolejności BST inorder(); // Ten kod został napisany przez Rajput-Ji> |
>
>Wyjście
20 30 40 50 60 70 80>
Złożoność czasowa:
- Najgorszy przypadek złożoności czasowej operacji wstawiania to Oh) Gdzie H jest wysokością drzewa wyszukiwania binarnego.
- W najgorszym przypadku może być konieczne przejście od korzenia do najgłębszego węzła liścia. Wysokość przekrzywionego drzewa może stać się N i może wzrosnąć złożoność czasowa operacji wstawiania NA).
Przestrzeń pomocnicza: Pomocniczy złożoność przestrzenna wstawiania do drzewa wyszukiwania binarnego wynosi O(1)
Wstawianie do drzewa wyszukiwania binarnego przy użyciu podejścia iteracyjnego:
Zamiast używać rekurencji, możemy również zaimplementować operację wstawiania iteracyjnie, używając a pętla while . Poniżej znajduje się implementacja wykorzystująca pętlę while.
q1 q2 q3 q4
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> klucz) {> >prev = temp;> >temp = temp->lewo;> >}> >else> if> (temp->wartość poprzednia = temperatura; temp = temp->prawo; } } if (prev->val> key) prev->left = węzeł; else prev->right = węzeł; } // Funkcja narzędziowa do drukowania przejścia w kolejności void inorder(Node* root) { Node* temp = root; stos st; while (temp != NULL || !st.empty()) { if (temp != NULL) { st.push(temp); temp = temp->lewo; } else { temp = st.top(); st.pop(); cout ' '; temp = temp->prawo; } } } // Kod sterownika int main() { Węzeł* root = NULL; wstaw(korzeń, 30); wstaw(korzeń, 50); wstaw(korzeń, 15); wstaw(korzeń, 20); wstaw(korzeń, 10); wstaw(korzeń, 40); wstaw(korzeń, 60); // Wywołanie funkcji wyświetlającej przejście w kolejności inorder(root); zwróć 0; }> |
>
>
Jawa
// 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>klawisz) {> >prev = temp;> >temp = temp.left;> >}> >else> if> (temp.val prev = temp; temp = temp.right; } } if (prev.val>klucz) prev.left = węzeł; else prev.right = węzeł; } // Funkcja wypisująca wartość zamówienia public void inorder() { Node temp = root; Stos stosu = nowy stos(); while (temp != null || !stack.isEmpty()) { if (temp != null) { stack.add(temp); temp = temp. lewa; } else { temp = stack.pop(); System.out.print(temp.val + ' '); temp = temp.prawa; } } } }> |
>
>
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>klucz):> >prev>=> temp> >temp>=> temp.left> >elif>(temp.val prev = temp temp = temp.right if (prev.val>klucz): prev.left = węzeł else: prev.right = węzeł # Funkcja wyświetlająca przejście w kolejności BST def inorder(self): temp = self.root stos = [] while (temp != Brak lub nie (len( stos) == 0)): if (temp != Brak): stos.append(temp) temp = temp.left else: temp = stack.pop() print(str(temp.val) + ' ', end='') temp = temp.right if __name__ == '__main__': GFG.main([]) # Ten kod został napisany przez rastogik346.> |
>
>
C#
obiad vs czas kolacji
// 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>klawisz) {> >prev = temp;> >temp = temp.left;> >}> >else> if> (temp.val prev = temp; temp = temp.right; } } if (prev.val>klucz) prev.left = węzeł; else prev.right = węzeł; } // Funkcja wyświetlająca przejście w kolejności wewnętrznej BST public void inorder() { Node temp = root; Stos stosu = nowy stos(); while (temp != null || stos.Count != 0) { if (temp != null) { stos.Push(temp); temp = temp. lewa; } else { temp = stos.Pop(); Console.Write(temp.val + ' '); temp = temp.prawa; } } } } // Ten kod został stworzony przez 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>klawisz) {> >prev = temp;> >temp = temp.left;> >}>else> if> (temp.val prev = temp; temp = temp.right; } } if (prev.val>klucz) prev.left = węzeł; else prev.right = węzeł; } // Funkcja wyświetlająca wartość zamówienia inorder() { let temp = this.root; niech stos = []; while (temp != null || długość.staku> 0) { if (temp != null) { stack.push(temp); temp = temp. lewa; } else { temp = stack.pop(); konsola.log(temp.wartość + ' '); temp = temp.prawa; } } } } niech drzewo = nowy BST(); drzewo.wstaw(30); drzewo.wstaw(50); drzewo.wstaw(15); drzewo.wstaw(20); drzewo.wstaw(10); drzewo.wstaw(40); drzewo.wstaw(60); drzewo.inorder(); // ten kod został stworzony przez devendrasolunke> |
>
>Wyjście
10 15 20 30 40 50 60>
The złożoność czasu z przejście wewnętrzne Jest NA) , ponieważ każdy węzeł jest odwiedzany raz.
The Przestrzeń pomocnicza Jest NA) , ponieważ używamy stosu do przechowywania węzłów na potrzeby rekurencji.
Powiązane linki:
- Operacja wyszukiwania drzewa wyszukiwania binarnego
- Operacja usuwania drzewa wyszukiwania binarnego