binary search tree c
Esercitazione dettagliata sull'albero di ricerca binaria (BST) in C ++, comprese operazioni, implementazione C ++, vantaggi e programmi di esempio:
Un albero di ricerca binario o BST, come viene comunemente chiamato, è un albero binario che soddisfa le seguenti condizioni:
- I nodi che sono inferiori al nodo radice che viene posizionato come figli di sinistra del BST.
- I nodi che sono maggiori del nodo radice posizionato come figli di destra del BST.
- I sottoalberi sinistro e destro sono a loro volta gli alberi di ricerca binari.
Questa disposizione di ordinare le chiavi in una sequenza particolare facilita al programmatore di eseguire operazioni come ricerca, inserimento, cancellazione, ecc. In modo più efficiente. Se i nodi non sono ordinati, potremmo dover confrontare ogni nodo prima di poter ottenere il risultato dell'operazione.
=> Controlla qui la serie completa di formazione C ++.
Cosa imparerai:
- Albero di ricerca binario C ++
- Operazioni di base
- Implementazione dell'albero di ricerca binaria C ++
- Vantaggi della BST
- Applicazioni di BST
- Conclusione
- Lettura consigliata
Albero di ricerca binario C ++
Di seguito è mostrato un esempio di BST.
Gli alberi binari di ricerca vengono anche chiamati 'alberi binari ordinati' a causa di questo specifico ordinamento dei nodi.
Dal BST sopra, possiamo vedere che il sottoalbero di sinistra ha nodi che sono inferiori alla radice, cioè 45 mentre il sottoalbero di destra ha i nodi che sono maggiori di 45.
Parliamo ora di alcune operazioni di base della BST.
Operazioni di base
# 1) Inserisci
L'operazione di inserimento aggiunge un nuovo nodo in un albero di ricerca binario.
Di seguito è riportato l'algoritmo per l'operazione di inserimento dell'albero di ricerca binaria.
html css intervista domande e risposte
Insert(data) Begin If node == null Return createNode(data) If(data >root->data) Node->right = insert(node->left,data) Else If(data data) Node->right = insert(node>right,data) Return node; endCome mostrato nell'algoritmo di cui sopra, dobbiamo assicurarci che il nodo sia posizionato nella posizione appropriata in modo da non violare l'ordinamento BST.
Come vediamo nella sequenza di diagrammi sopra, eseguiamo una serie di operazioni di inserimento. Dopo aver confrontato la chiave da inserire con il nodo radice, viene scelta la sottostruttura sinistra o destra per la chiave da inserire come nodo foglia nella posizione appropriata.
# 2) Elimina
L'operazione di eliminazione elimina un nodo che corrisponde alla chiave specificata da BST. Anche in questa operazione, dobbiamo riposizionare i nodi rimanenti dopo la cancellazione in modo che l'ordine BST non venga violato.
Quindi, a seconda di quale nodo dobbiamo eliminare, abbiamo i seguenti casi di eliminazione in BST:
# 1) Quando il nodo è un nodo foglia
Quando il nodo da eliminare è un nodo foglia, eliminiamo direttamente il nodo.
# 2) Quando il nodo ha un solo figlio
Quando il nodo da eliminare ha un solo figlio, copiamo il figlio nel nodo ed eliminiamo il figlio.
# 3) Quando il nodo ha due figli
Se il nodo da eliminare ha due figli, troviamo il successore inorder per il nodo e quindi copiamo il successore inorder nel nodo. Successivamente, eliminiamo il successore inordine.
Nell'albero sopra per eliminare il nodo 6 con due figli, troviamo prima il successore inordine per quel nodo da eliminare. Troviamo il successore inordine trovando il valore minimo nella sottostruttura destra. Nel caso precedente, il valore minimo è 7 nella sottostruttura destra. Lo copiamo nel nodo da eliminare e quindi eliminiamo il successore inorder.
# 3) Cerca
L'operazione di ricerca della BST ricerca un particolare elemento identificato come 'chiave' nella BST. Il vantaggio di cercare un elemento in BST è che non è necessario cercare l'intero albero. Invece a causa dell'ordinamento in BST, confrontiamo semplicemente la chiave con la radice.
Se la chiave è la stessa di root, restituiamo root. Se la chiave non è root, la confrontiamo con la root per determinare se è necessario cercare nella sottostruttura sinistra o destra. Una volta trovato il sottoalbero, dobbiamo cercare la chiave in e la cerchiamo ricorsivamente in uno dei sottoalberi.
Di seguito è riportato l'algoritmo per un'operazione di ricerca in BST.
Search(key) Begin If(root == null || root->data == key) Return root; If(root->key left,key) Else if (root->key >key ) Search(root->right,key); end 
Se vogliamo cercare una chiave con valore 6 nell'albero sopra, per prima cosa confrontiamo la chiave con il nodo radice, cioè if (6 == 7) => No if (6<7) =Yes; this means that we will omit the right subtree and search for the key in the left subtree.
Successivamente scendiamo all'albero secondario sinistro. Se (6 == 5) => No.
Se (6 No; questo significa 6> 5 e dobbiamo muoverci verso destra.
Se (6 == 6) => Sì; la chiave è trovata.
# 4) Traversate
Abbiamo già discusso gli attraversamenti per l'albero binario. Anche nel caso di BST, possiamo attraversare l'albero per entrare nella sequenza Order, preorder o postOrder. Infatti, quando attraversiamo la BST nella sequenza Inorder01, otteniamo la sequenza ordinata.
Lo abbiamo mostrato nell'illustrazione sottostante.
Gli attraversamenti per l'albero sopra sono i seguenti:
Attraversamento in ordine (lnr): 3 5 6 7 8 9 10
Attraversamento preordine (nlr): 7 5 3 6 9 8 10
PostOrder traversal (lrn): 3 6 5 8 10 9 7
Illustrazione
Costruiamo un albero di ricerca binario dai dati forniti di seguito.
45 30 60 65 70
Prendiamo il primo elemento come nodo radice.
# 1) 45
Nei passaggi successivi, posizioneremo i dati in base alla definizione dell'albero di ricerca binaria, ovvero se i dati sono minori del nodo padre, verranno posizionati a sinistra del figlio e se i dati sono maggiori del nodo padre, allora sarà il bambino giusto.
Questi passaggi sono mostrati di seguito.
# 2) 30
# 3) 60
# 4) 65
# 5) 70
Quando eseguiamo l'attraversamento in ordine sulla BST di cui sopra che abbiamo appena costruito, la sequenza è la seguente.
Possiamo vedere che la sequenza trasversale ha elementi disposti in ordine crescente.
Implementazione dell'albero di ricerca binaria C ++
Dimostriamo BST e le sue operazioni utilizzando l'implementazione C ++.
#include using namespace std; //declaration for new bst node struct bstnode { int data; struct bstnode *left, *right; }; // create a new BST node struct bstnode *newNode(int key) { struct bstnode *temp = new struct bstnode(); temp->data = key; temp->left = temp->right = NULL; return temp; } // perform inorder traversal of BST void inorder(struct bstnode *root) { if (root != NULL) { inorder(root->left); cout<data<<' '; inorder(root->right); } } /* insert a new node in BST with given key */ struct bstnode* insert(struct bstnode* node, int key) { //tree is empty;return a new node if (node == NULL) return newNode(key); //if tree is not empty find the proper place to insert new node if (key data) node->left = insert(node->left, key); else node->right = insert(node->right, key); //return the node pointer return node; } //returns the node with minimum value struct bstnode * minValueNode(struct bstnode* node) { struct bstnode* current = node; //search the leftmost tree while (current && current->left != NULL) current = current->left; return current; } //function to delete the node with given key and rearrange the root struct bstnode* deleteNode(struct bstnode* root, int key) { // empty tree if (root == NULL) return root; // search the tree and if key data) root->left = deleteNode(root->left, key); // if key > root, go for rightmost tree else if (key > root->data) root->right = deleteNode(root->right, key); // key is same as root else { // node with only one child or no child if (root->left == NULL) { struct bstnode *temp = root->right; free(root); return temp; } else if (root->right == NULL) { struct bstnode *temp = root->left; free(root); return temp; } // node with both children; get successor and then delete the node struct bstnode* temp = minValueNode(root->right); // Copy the inorder successor's content to this node root->data = temp->data; // Delete the inorder successor root->right = deleteNode(root->right, temp->data); } return root; } // main program int main() { /* Let us create following BST 40 / 30 60 65 70*/ struct bstnode *root = NULL; root = insert(root, 40); root = insert(root, 30); root = insert(root, 60); root = insert(root, 65); root = insert(root, 70); cout<<'Binary Search Tree created (Inorder traversal):'< Produzione:
Albero di ricerca binario creato (traversata in ordine):
30 40 60 65 70
Elimina nodo 40
Attraversamento in ordine per l'albero di ricerca binario modificato:
30 60 65 70
Nel programma sopra, produciamo il BST per la sequenza di attraversamento in ordine.
Vantaggi della BST
# 1) La ricerca è molto efficiente
esempi di data mining nel mondo reale
Abbiamo tutti i nodi di BST in un ordine specifico, quindi la ricerca di un particolare articolo è molto efficiente e veloce. Questo perché non è necessario cercare nell'intero albero e confrontare tutti i nodi.
Dobbiamo solo confrontare il nodo radice con l'elemento che stiamo cercando e poi decidiamo se dobbiamo cercare nella sottostruttura sinistra o destra.
# 2) Lavoro efficiente rispetto agli array e agli elenchi collegati
Quando cerchiamo un elemento in caso di BST, eliminiamo metà della sottostruttura sinistra o destra ad ogni passaggio, migliorando così le prestazioni dell'operazione di ricerca. Ciò è in contrasto con gli array o gli elenchi collegati in cui è necessario confrontare tutti gli elementi in sequenza per cercare un elemento particolare.
# 3) Inserisci ed elimina sono più veloci
Le operazioni di inserimento ed eliminazione sono inoltre più veloci rispetto ad altre strutture di dati come elenchi e array collegati.
Applicazioni di BST
Alcune delle principali applicazioni della BST sono le seguenti:
- BST viene utilizzato per implementare l'indicizzazione multilivello nelle applicazioni di database.
- BST viene utilizzato anche per implementare costrutti come un dizionario.
- BST può essere utilizzato per implementare vari algoritmi di ricerca efficienti.
- BST viene utilizzato anche nelle applicazioni che richiedono un elenco ordinato come input come i negozi online.
- I BST vengono utilizzati anche per valutare l'espressione utilizzando alberi delle espressioni.
Conclusione
Gli alberi binari di ricerca (BST) sono una variazione dell'albero binario e sono ampiamente utilizzati nel campo del software. Sono anche chiamati alberi binari ordinati poiché ogni nodo in BST viene posizionato secondo un ordine specifico.
L'attraversamento in ordine di BST ci fornisce la sequenza ordinata di elementi in ordine crescente. Quando i BST vengono utilizzati per la ricerca, è molto efficiente e viene eseguito in pochissimo tempo. I BST vengono utilizzati anche per una varietà di applicazioni come la codifica di Huffman, l'indicizzazione multilivello nei database, ecc.
=> Leggi qui la popolare serie di formazione C ++.
Lettura consigliata
- Struttura dei dati dell'albero binario in C ++
- Struttura dei dati ad albero e heap AVL in C ++
- Struttura dati B Tree e B + Tree in C ++
- Operazioni di input / output di base in C ++
- Operazioni di I / O di base in Java (flussi di input / output)
- Alberi in C ++: terminologia di base, tecniche di attraversamento e tipi di alberi C ++
- File Input Output Operazioni in C ++
- Puntatori e operazioni con i puntatori in C ++