În acest articol, vom discuta despre arborele de căutare binar. Acest articol va fi foarte util și informativ pentru studenții cu experiență tehnică, deoarece este un subiect important al cursului lor.
Înainte de a trece direct la arborele de căutare binar, să vedem mai întâi o scurtă descriere a arborelui.
Ce este un copac?
Un arbore este un fel de structură de date care este utilizată pentru a reprezenta datele în formă ierarhică. Poate fi definit ca o colecție de obiecte sau entități numite noduri care sunt legate între ele pentru a simula o ierarhie. Arborele este o structură de date neliniară, deoarece datele dintr-un arbore nu sunt stocate liniar sau secvenţial.
Acum, să începem subiectul, arborele de căutare binară.
Ce este un arbore de căutare binar?
Un arbore de căutare binar urmează o anumită ordine pentru a aranja elementele. Într-un arbore de căutare binar, valoarea nodului din stânga trebuie să fie mai mică decât nodul părinte, iar valoarea nodului din dreapta trebuie să fie mai mare decât nodul părinte. Această regulă se aplică recursiv subarborilor din stânga și din dreapta rădăcinii.
Să înțelegem conceptul de arbore de căutare binar cu un exemplu.
În figura de mai sus, putem observa că nodul rădăcină este 40, iar toate nodurile subarborelui din stânga sunt mai mici decât nodul rădăcină, iar toate nodurile subarborelui drept sunt mai mari decât nodul rădăcină.
În mod similar, putem vedea că copilul stâng al nodului rădăcină este mai mare decât copilul său stâng și mai mic decât copilul său drept. Deci, satisface și proprietatea arborelui de căutare binar. Prin urmare, putem spune că arborele din imaginea de mai sus este un arbore de căutare binar.
Să presupunem că dacă schimbăm valoarea nodului 35 la 55 din arborele de mai sus, verificați dacă arborele va fi arbore de căutare binar sau nu.
În arborele de mai sus, valoarea nodului rădăcină este 40, care este mai mare decât copilul său stâng 30, dar mai mic decât copilul din dreapta de 30, adică 55. Deci, arborele de mai sus nu satisface proprietatea arborelui de căutare binar. Prin urmare, arborele de mai sus nu este un arbore de căutare binar.
Avantajele arborelui de căutare binar
- Căutarea unui element în arborele de căutare binar este ușoară, deoarece avem întotdeauna un indiciu că subarborele are elementul dorit.
- În comparație cu listele matrice și legate, operațiunile de inserare și ștergere sunt mai rapide în BST.
Exemplu de creare a unui arbore de căutare binar
Acum, să vedem crearea unui arbore de căutare binar folosind un exemplu.
Să presupunem că elementele de date sunt - 45, 15, 79, 90, 10, 55, 12, 20, 50
- În primul rând, trebuie să introducem Patru cinci în copac ca rădăcină a copacului.
- Apoi, citiți următorul element; dacă este mai mic decât nodul rădăcină, introduceți-l ca rădăcină a subarborelui din stânga și treceți la următorul element.
- În caz contrar, dacă elementul este mai mare decât nodul rădăcină, atunci introduceți-l ca rădăcină a subarborelui din dreapta.
Acum, să vedem procesul de creare a arborelui de căutare binar folosind elementul de date dat. Procesul de creare a BST este prezentat mai jos -
dacă-altfel java
Pasul 1 - Introduceți 45.
Pasul 2 - Introduceți 15.
Deoarece 15 este mai mic decât 45, inserați-l ca nod rădăcină al subarborelui din stânga.
Pasul 3 - Introduceți 79.
Deoarece 79 este mai mare decât 45, inserați-l ca nod rădăcină al subarborelui din dreapta.
Pasul 4 - Introduceți 90.
90 este mai mare decât 45 și 79, deci va fi inserat ca subarborele din dreapta al lui 79.
Pasul 5 - Introduceți 10.
10 este mai mic decât 45 și 15, deci va fi inserat ca un subarboresc din stânga cu 15.
sortează lista de matrice java
Pasul 6 - Introduceți 55.
55 este mai mare decât 45 și mai mic decât 79, așa că va fi inserat ca subarborele din stânga al lui 79.
Pasul 7 - Introduceți 12.
12 este mai mic decât 45 și 15, dar mai mare decât 10, deci va fi inserat ca subarborele din dreapta al lui 10.
Pasul 8 - Introduceți 20.
20 este mai mic decât 45, dar mai mare decât 15, deci va fi inserat ca subarborele din dreapta al lui 15.
Pasul 9 - Introduceți 50.
.04 sub formă de fracție
50 este mai mare decât 45, dar mai mic decât 79 și 55. Deci, va fi inserat ca un subarboresc din stânga cu 55.
Acum, crearea arborelui de căutare binar este finalizată. După aceea, să trecem la operațiunile care pot fi efectuate pe arborele de căutare binar.
Putem efectua operații de inserare, ștergere și căutare în arborele binar de căutare.
Să înțelegem cum se efectuează o căutare pe un arbore de căutare binar.
Căutarea în arborele de căutare binar
Căutarea înseamnă găsirea sau localizarea unui anumit element sau nod într-o structură de date. În arborele de căutare binar, căutarea unui nod este ușoară, deoarece elementele din BST sunt stocate într-o anumită ordine. Pașii căutării unui nod în arborele de căutare binar sunt enumerați după cum urmează -
- Mai întâi, comparați elementul care trebuie căutat cu elementul rădăcină al arborelui.
- Dacă rădăcina este potrivită cu elementul țintă, atunci returnați locația nodului.
- Dacă nu se potrivește, atunci verificați dacă elementul este mai mic decât elementul rădăcină, dacă este mai mic decât elementul rădăcină, apoi treceți la subarborele din stânga.
- Dacă este mai mare decât elementul rădăcină, atunci treceți la subarborele din dreapta.
- Repetați procedura de mai sus în mod recursiv până când este găsită potrivirea.
- Dacă elementul nu este găsit sau nu este prezent în arbore, atunci returnați NULL.
Acum, să înțelegem căutarea în arbore binar folosind un exemplu. Luăm arborele de căutare binar format mai sus. Să presupunem că trebuie să găsim nodul 20 din arborele de mai jos.
Pasul 1:
Pasul 2:
Pasul 3:
Acum, să vedem algoritmul de căutare a unui element în arborele de căutare binar.
Algoritm pentru căutarea unui element în arborele de căutare binar
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> Ieșire
După executarea codului de mai sus, rezultatul va fi -
Deci, asta e totul despre articol. Sper că articolul vă va fi util și informativ.