In questo articolo discuteremo dell'albero di ricerca binario. Questo articolo sarà molto utile e informativo per gli studenti con un background tecnico poiché è un argomento importante del loro corso.
Prima di passare direttamente all'albero binario di ricerca, vediamo innanzitutto una breve descrizione dell'albero.
Cos'è un albero?
Un albero è un tipo di struttura dati utilizzata per rappresentare i dati in forma gerarchica. Può essere definito come una raccolta di oggetti o entità chiamati nodi collegati insieme per simulare una gerarchia. L'albero è una struttura dati non lineare poiché i dati in un albero non vengono archiviati in modo lineare o sequenziale.
Ora iniziamo l'argomento, l'albero della ricerca binaria.
intero per raddoppiare Java
Cos'è un albero di ricerca binaria?
Un albero di ricerca binario segue un certo ordine per disporre gli elementi. In un albero di ricerca binario, il valore del nodo sinistro deve essere inferiore al nodo principale e il valore del nodo destro deve essere maggiore del nodo principale. Questa regola viene applicata ricorsivamente ai sottoalberi sinistro e destro della radice.
Comprendiamo il concetto di albero di ricerca binario con un esempio.
Nella figura sopra, possiamo osservare che il nodo radice è 40 e tutti i nodi del sottoalbero sinistro sono più piccoli del nodo radice e tutti i nodi del sottoalbero destro sono maggiori del nodo radice.
Allo stesso modo, possiamo vedere che il figlio sinistro del nodo radice è maggiore del figlio sinistro e più piccolo del figlio destro. Quindi, soddisfa anche la proprietà dell'albero di ricerca binario. Pertanto, possiamo dire che l'albero nell'immagine sopra è un albero di ricerca binario.
Supponiamo di modificare il valore del nodo da 35 a 55 nell'albero sopra, verificare se l'albero sarà un albero di ricerca binario o meno.
Nell'albero sopra, il valore del nodo radice è 40, che è maggiore del suo figlio sinistro 30 ma più piccolo del figlio destro di 30, cioè 55. Pertanto, l'albero sopra non soddisfa la proprietà dell'albero di ricerca binario. Pertanto, l'albero sopra non è un albero di ricerca binario.
Vantaggi dell'albero di ricerca binario
- La ricerca di un elemento nell'albero di ricerca binario è semplice poiché abbiamo sempre un suggerimento su quale sottoalbero ha l'elemento desiderato.
- Rispetto agli array e agli elenchi concatenati, le operazioni di inserimento e cancellazione sono più veloci in BST.
Esempio di creazione di un albero di ricerca binario
Ora vediamo la creazione dell'albero di ricerca binario utilizzando un esempio.
casella di riepilogo html
Supponiamo che gli elementi dei dati lo siano -45, 15, 79, 90, 10, 55, 12, 20, 50
- Per prima cosa dobbiamo inserire Quattro cinque nell'albero come la radice dell'albero.
- Quindi, leggi l'elemento successivo; se è più piccolo del nodo radice, inserirlo come radice del sottoalbero sinistro e passare all'elemento successivo.
- Altrimenti, se l'elemento è più grande del nodo radice, inserirlo come radice del sottoalbero destro.
Ora vediamo il processo di creazione dell'albero di ricerca binario utilizzando l'elemento dati specificato. Il processo di creazione del BST è mostrato di seguito:
Passaggio 1: inserire 45.
Passaggio 2: inserire 15.
Poiché 15 è inferiore a 45, inserirlo come nodo radice del sottoalbero sinistro.
Passaggio 3: inserire 79.
Poiché 79 è maggiore di 45, inserirlo come nodo radice del sottoalbero destro.
Passaggio 4: inserire 90.
90 è maggiore di 45 e 79, quindi verrà inserito come sottoalbero destro di 79.
Passaggio 5: inserire 10.
10 è inferiore a 45 e 15, quindi verrà inserito come sottoalbero sinistro di 15.
numeri in alfabeto
Passaggio 6: inserire 55.
55 è maggiore di 45 e minore di 79, quindi verrà inserito come sottoalbero sinistro di 79.
Passaggio 7: inserire 12.
12 è minore di 45 e 15 ma maggiore di 10, quindi verrà inserito come sottoalbero destro di 10.
Passaggio 8: inserire 20.
20 è minore di 45 ma maggiore di 15, quindi verrà inserito come sottoalbero destro di 15.
Passaggio 9: inserire 50.
50 è maggiore di 45 ma minore di 79 e 55. Pertanto verrà inserito come sottoalbero sinistro di 55.
Ora la creazione dell'albero di ricerca binario è completata. Successivamente passiamo alle operazioni che possono essere eseguite sull'albero di ricerca binario.
Possiamo eseguire operazioni di inserimento, eliminazione e ricerca sull'albero di ricerca binario.
Capiamo come viene eseguita una ricerca su un albero di ricerca binario.
Ricerca nell'albero di ricerca binario
Cercare significa trovare o localizzare un elemento o nodo specifico in una struttura dati. Nell'albero di ricerca binario, la ricerca di un nodo è semplice perché gli elementi in BST sono memorizzati in un ordine specifico. I passaggi per la ricerca di un nodo nell'albero di ricerca binaria sono elencati come segue:
- Innanzitutto, confronta l'elemento da cercare con l'elemento radice dell'albero.
- Se root corrisponde all'elemento di destinazione, restituisce la posizione del nodo.
- Se non corrisponde, controlla se l'elemento è inferiore all'elemento radice, se è più piccolo dell'elemento radice, spostati al sottoalbero sinistro.
- Se è più grande dell'elemento radice, spostati al sottoalbero destro.
- Ripetere la procedura precedente in modo ricorsivo finché non viene trovata la corrispondenza.
- Se l'elemento non viene trovato o non è presente nell'albero, restituisce NULL.
Ora comprendiamo la ricerca nell'albero binario utilizzando un esempio. Stiamo prendendo l'albero di ricerca binario formato sopra. Supponiamo di dover trovare il nodo 20 dall'albero sottostante.
Passo 1:
Passo 2:
Passaggio 3:
Vediamo ora l'algoritmo per cercare un elemento nell'albero di ricerca binario.
Algoritmo per cercare un elemento nell'albero di ricerca binario
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> Produzione
riavviare mysql ubuntu
Dopo l'esecuzione del codice sopra, l'output sarà:
Quindi, questo è tutto sull'articolo. Spero che l'articolo ti sia utile e informativo.