W tym artykule omówimy drzewo wyszukiwania binarnego. Ten artykuł będzie bardzo pomocny i pouczający dla studentów z wykształceniem technicznym, ponieważ jest to ważny temat ich kursu.
Zanim przejdziemy bezpośrednio do drzewa wyszukiwania binarnego, przyjrzyjmy się najpierw krótkiemu opisowi drzewa.
Co to jest drzewo?
Drzewo to rodzaj struktury danych używanej do reprezentowania danych w formie hierarchicznej. Można go zdefiniować jako zbiór obiektów lub jednostek zwanych węzłami, które są ze sobą połączone w celu symulacji hierarchii. Drzewo jest nieliniową strukturą danych, ponieważ dane w drzewie nie są przechowywane liniowo ani sekwencyjnie.
Teraz zacznijmy temat, drzewo wyszukiwania binarnego.
Co to jest drzewo wyszukiwania binarnego?
Drzewo wyszukiwania binarnego charakteryzuje się pewnym porządkiem rozmieszczenia elementów. W drzewie wyszukiwania binarnego wartość lewego węzła musi być mniejsza niż węzeł nadrzędny, a wartość prawego węzła musi być większa niż węzeł nadrzędny. Reguła ta jest stosowana rekurencyjnie do lewego i prawego poddrzewa korzenia.
Przyjrzyjmy się koncepcji drzewa wyszukiwania binarnego na przykładzie.
Na powyższym rysunku możemy zaobserwować, że węzeł główny ma 40, a wszystkie węzły lewego poddrzewa są mniejsze niż węzeł główny, a wszystkie węzły prawego poddrzewa są większe niż węzeł główny.
Podobnie widzimy, że lewe dziecko węzła głównego jest większe niż jego lewe dziecko i mniejsze niż prawe dziecko. Spełnia więc również właściwość drzewa wyszukiwania binarnego. Można zatem powiedzieć, że drzewo na powyższym obrazku jest drzewem wyszukiwania binarnego.
Załóżmy, że jeśli zmienimy wartość węzła 35 na 55 w powyższym drzewie, sprawdzimy, czy drzewo będzie drzewem wyszukiwania binarnego, czy nie.
W powyższym drzewie wartość węzła głównego wynosi 40, czyli jest większa niż jego lewe dziecko 30, ale mniejsza niż prawe dziecko 30, tj. 55. Zatem powyższe drzewo nie spełnia właściwości drzewa wyszukiwania binarnego. Dlatego powyższe drzewo nie jest drzewem wyszukiwania binarnego.
Zalety drzewa wyszukiwania binarnego
- Wyszukiwanie elementu w drzewie wyszukiwania binarnego jest łatwe, ponieważ zawsze mamy wskazówkę, w którym poddrzewie znajduje się żądany element.
- W porównaniu do tablic i list połączonych, operacje wstawiania i usuwania są szybsze w BST.
Przykład tworzenia drzewa wyszukiwania binarnego
Przyjrzyjmy się teraz tworzeniu drzewa wyszukiwania binarnego na przykładzie.
Załóżmy, że elementy danych są - 45, 15, 79, 90, 10, 55, 12, 20, 50
Neena Gupta
- Najpierw musimy wstawić Cztery pięć w drzewo jako korzeń drzewa.
- Następnie przeczytaj kolejny element; jeśli jest mniejszy niż węzeł główny, wstaw go jako korzeń lewego poddrzewa i przejdź do następnego elementu.
- W przeciwnym razie, jeśli element jest większy niż węzeł główny, wstaw go jako korzeń prawego poddrzewa.
Przyjrzyjmy się teraz procesowi tworzenia drzewa wyszukiwania binarnego przy użyciu podanego elementu danych. Proces tworzenia BST pokazano poniżej -
Krok 1 - Włóż 45.
Krok 2 – Wstaw 15.
Ponieważ 15 jest mniejsze niż 45, wstaw je jako węzeł główny lewego poddrzewa.
Krok 3 – Wstaw 79.
Ponieważ 79 jest większe niż 45, wstaw je jako węzeł główny prawego poddrzewa.
Krok 4 - Włóż 90.
rodzaje testów
Liczba 90 jest większa niż 45 i 79, więc zostanie wstawiona jako prawe poddrzewo liczby 79.
Krok 5 – Wstaw 10.
Liczba 10 jest mniejsza niż 45 i 15, więc zostanie wstawiona jako lewe poddrzewo liczby 15.
Krok 6 - Włóż 55.
Liczba 55 jest większa niż 45 i mniejsza niż 79, więc zostanie wstawiona jako lewe poddrzewo liczby 79.
Krok 7 – Wstaw 12.
Liczba 12 jest mniejsza niż 45 i 15, ale większa niż 10, więc zostanie wstawiona jako prawe poddrzewo liczby 10.
Krok 8 – Wstaw 20.
Liczba 20 jest mniejsza niż 45, ale większa niż 15, więc zostanie wstawiona jako prawe poddrzewo liczby 15.
Krok 9 - Włóż 50.
Liczba 50 jest większa niż 45, ale mniejsza niż 79 i 55. Zostanie zatem wstawiona jako lewe poddrzewo liczby 55.
Teraz tworzenie drzewa wyszukiwania binarnego zostało zakończone. Następnie przejdźmy do operacji, które można wykonać na drzewie wyszukiwania binarnego.
Na drzewie wyszukiwania binarnego możemy wykonywać operacje wstawiania, usuwania i wyszukiwania.
Rozumiemy, jak przeprowadzane jest wyszukiwanie w drzewie wyszukiwania binarnego.
Wyszukiwanie w drzewie wyszukiwania binarnego
Wyszukiwanie oznacza znalezienie lub zlokalizowanie określonego elementu lub węzła w strukturze danych. W drzewie wyszukiwania binarnego przeszukiwanie węzła jest łatwe, ponieważ elementy w BST są przechowywane w określonej kolejności. Etapy wyszukiwania węzła w drzewie wyszukiwania binarnego są następujące:
- Najpierw porównaj element, który ma być przeszukany, z elementem głównym drzewa.
- Jeśli element główny jest dopasowany do elementu docelowego, zwróć lokalizację węzła.
- Jeśli nie jest dopasowany, to sprawdź, czy element jest mniejszy od elementu głównego, jeśli jest mniejszy od elementu głównego, to przejdź do lewego poddrzewa.
- Jeśli jest większy niż element główny, przejdź do prawego poddrzewa.
- Powtarzaj powyższą procedurę rekurencyjnie, aż zostanie znalezione dopasowanie.
- Jeżeli element nie zostanie odnaleziony lub nie występuje w drzewie, zwróć NULL.
Teraz zrozummy wyszukiwanie w drzewie binarnym na przykładzie. Bierzemy utworzone powyżej drzewo wyszukiwania binarnego. Załóżmy, że musimy znaleźć węzeł 20 z poniższego drzewa.
Krok 1:
Krok 2:
Krok 3:
Przyjrzyjmy się teraz algorytmowi przeszukiwania elementu w drzewie wyszukiwania binarnego.
Algorytm przeszukiwania elementu w drzewie wyszukiwania binarnego
Search (root, item) Step 1 - if (item = root → data) or (root = NULL) return root else if (item <root 2 → data) return search(root left, item) else right, end if step - < pre> <p>Now let's understand how the deletion is performed on a binary search tree. We will also see an example to delete an element from the given tree.</p> <h3>Deletion in Binary Search tree</h3> <p>In a binary search tree, we must delete a node from the tree by keeping in mind that the property of BST is not violated. To delete a node from BST, there are three possible situations occur -</p> <ul> <li>The node to be deleted is the leaf node, or,</li> <li>The node to be deleted has only one child, and,</li> <li>The node to be deleted has two children</li> </ul> <p>We will understand the situations listed above in detail.</p> <p> <strong>When the node to be deleted is the leaf node</strong> </p> <p>It is the simplest case to delete a node in BST. Here, we have to replace the leaf node with NULL and simply free the allocated space.</p> <p>We can see the process to delete a leaf node from BST in the below image. In below image, suppose we have to delete node 90, as the node to be deleted is a leaf node, so it will be replaced with NULL, and the allocated space will free.</p> <img src="//techcodeview.com/img/ds-tutorial/58/binary-search-tree-15.webp" alt="Binary Search tree"> <p> <strong>When the node to be deleted has only one child</strong> </p> <p>In this case, we have to replace the target node with its child, and then delete the child node. It means that after replacing the target node with its child node, the child node will now contain the value to be deleted. So, we simply have to replace the child node with NULL and free up the allocated space.</p> <p>We can see the process of deleting a node with one child from BST in the below image. In the below image, suppose we have to delete the node 79, as the node to be deleted has only one child, so it will be replaced with its child 55.</p> <p>So, the replaced node 79 will now be a leaf node that can be easily deleted.</p> <img src="//techcodeview.com/img/ds-tutorial/58/binary-search-tree-16.webp" alt="Binary Search tree"> <p> <strong>When the node to be deleted has two children</strong> </p> <p>This case of deleting a node in BST is a bit complex among other two cases. In such a case, the steps to be followed are listed as follows -</p> <ul> <li>First, find the inorder successor of the node to be deleted.</li> <li>After that, replace that node with the inorder successor until the target node is placed at the leaf of tree.</li> <li>And at last, replace the node with NULL and free up the allocated space.</li> </ul> <p>The inorder successor is required when the right child of the node is not empty. We can obtain the inorder successor by finding the minimum element in the right child of the node.</p> <p>We can see the process of deleting a node with two children from BST in the below image. In the below image, suppose we have to delete node 45 that is the root node, as the node to be deleted has two children, so it will be replaced with its inorder successor. Now, node 45 will be at the leaf of the tree so that it can be deleted easily.</p> <img src="//techcodeview.com/img/ds-tutorial/58/binary-search-tree-17.webp" alt="Binary Search tree"> <p>Now let's understand how insertion is performed on a binary search tree.</p> <h3>Insertion in Binary Search tree</h3> <p>A new key in BST is always inserted at the leaf. To insert an element in BST, we have to start searching from the root node; if the node to be inserted is less than the root node, then search for an empty location in the left subtree. Else, search for the empty location in the right subtree and insert the data. Insert in BST is similar to searching, as we always have to maintain the rule that the left subtree is smaller than the root, and right subtree is larger than the root.</p> <p>Now, let's see the process of inserting a node into BST using an example.</p> <img src="//techcodeview.com/img/ds-tutorial/58/binary-search-tree-18.webp" alt="Binary Search tree"> <br> <img src="//techcodeview.com/img/ds-tutorial/58/binary-search-tree-19.webp" alt="Binary Search tree"> <h3>The complexity of the Binary Search tree</h3> <p>Let's see the time and space complexity of the Binary search tree. We will see the time complexity for insertion, deletion, and searching operations in best case, average case, and worst case.</p> <h3>1. Time Complexity</h3> <table class="table"> <tr> <th>Operations</th> <th>Best case time complexity</th> <th>Average case time complexity</th> <th>Worst case time complexity</th> </tr> <tr> <td> <strong>Insertion</strong> </td> <td>O(log n)</td> <td>O(log n)</td> <td>O(n)</td> </tr> <tr> <td> <strong>Deletion</strong> </td> <td>O(log n)</td> <td>O(log n)</td> <td>O(n)</td> </tr> <tr> <td> <strong>Search</strong> </td> <td>O(log n)</td> <td>O(log n)</td> <td>O(n)</td> </tr> </table> <p>Where 'n' is the number of nodes in the given tree.</p> <h3>2. Space Complexity</h3> <table class="table"> <tr> <th>Operations</th> <th>Space complexity</th> </tr> <tr> <td> <strong>Insertion</strong> </td> <td>O(n)</td> </tr> <tr> <td> <strong>Deletion</strong> </td> <td>O(n)</td> </tr> <tr> <td> <strong>Search</strong> </td> <td>O(n)</td> </tr> </table> <ul> <li>The space complexity of all operations of Binary search tree is O(n).</li> </ul> <h2>Implementation of Binary search tree</h2> <p>Now, let's see the program to implement the operations of Binary Search tree.</p> <p> <strong>Program:</strong> Write a program to perform operations of Binary Search tree in C++.</p> <p>In this program, we will see the implementation of the operations of binary search tree. Here, we will see the creation, inorder traversal, insertion, and deletion operations of tree.</p> <p>Here, we will see the inorder traversal of the tree to check whether the nodes of the tree are in their proper location or not. We know that the inorder traversal always gives us the data in ascending order. So, after performing the insertion and deletion operations, we perform the inorder traversal, and after traversing, if we get data in ascending order, then it is clear that the nodes are in their proper location.</p> <pre> #include using namespace std; struct Node { int data; Node *left; Node *right; }; Node* create(int item) { Node* node = new Node; node->data = item; node->left = node->right = NULL; return node; } /*Inorder traversal of the tree formed*/ void inorder(Node *root) { if (root == NULL) return; inorder(root->left); //traverse left subtree cout<data <right); traverse right subtree } node* findminimum(node* cur) *to find the inorder successor* { while(cur->left != NULL) { cur = cur->left; } return cur; } Node* insertion(Node* root, int item) /*Insert a node*/ { if (root == NULL) return create(item); /*return new node if tree is empty*/ if (item data) root->left = insertion(root->left, item); else root->right = insertion(root->right, item); return root; } void search(Node* &cur, int item, Node* &parent) { while (cur != NULL && cur->data != item) { parent = cur; if (item data) cur = cur->left; else cur = cur->right; } } void deletion(Node*& root, int item) /*function to delete a node*/ { Node* parent = NULL; Node* cur = root; search(cur, item, parent); /*find the node to be deleted*/ if (cur == NULL) return; if (cur->left == NULL && cur->right == NULL) /*When node has no children*/ { if (cur != root) { if (parent->left == cur) parent->left = NULL; else parent->right = NULL; } else root = NULL; free(cur); } else if (cur->left && cur->right) { Node* succ = findMinimum(cur->right); int val = succ->data; deletion(root, succ->data); cur->data = val; } else { Node* child = (cur->left)? cur->left: cur->right; if (cur != root) { if (cur == parent->left) parent->left = child; else parent->right = child; } else root = child; free(cur); } } int main() { Node* root = NULL; root = insertion(root, 45); root = insertion(root, 30); root = insertion(root, 50); root = insertion(root, 25); root = insertion(root, 35); root = insertion(root, 45); root = insertion(root, 60); root = insertion(root, 4); printf('The inorder traversal of the given binary tree is -
'); inorder(root); deletion(root, 25); printf('
After deleting node 25, the inorder traversal of the given binary tree is -
'); inorder(root); insertion(root, 2); printf('
After inserting node 2, the inorder traversal of the given binary tree is -
'); inorder(root); return 0; } </data></pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/58/binary-search-tree-20.webp" alt="Binary Search tree"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></root> Wyjście
wyliczenie tostring Java
Po wykonaniu powyższego kodu wyjściem będzie -
To tyle na temat artykułu. Mam nadzieję, że artykuł będzie dla Ciebie pomocny i pouczający.