Albero di ricerca binario (BST) con esempio

Sommario:

Anonim

Che cos'è un albero di ricerca binario?

L'albero di ricerca binario è un algoritmo avanzato utilizzato per analizzare il nodo, i suoi rami sinistro e destro, che sono modellati in una struttura ad albero e restituiscono il valore. Il BST è concepito sull'architettura di un algoritmo di ricerca binaria di base; quindi consente ricerche, inserimenti e rimozioni più veloci dei nodi. Questo rende il programma davvero veloce e preciso.

In questo tutorial sulla struttura dei dati imparerai:

  • Che cos'è un albero di ricerca binario?
  • Attributi dell'albero di ricerca binario
  • Perché abbiamo bisogno di un albero di ricerca binario?
  • Tipi di alberi binari
  • Come funziona l'albero di ricerca binario?
  • Termini importanti

Attributi dell'albero di ricerca binario

Un BST è composto da più nodi ed è costituito dai seguenti attributi:

  • I nodi dell'albero sono rappresentati in una relazione padre-figlio
  • Ogni nodo padre può avere zero nodi figlio o un massimo di due sottonodi o sottostrutture sui lati sinistro e destro.
  • Ogni sottoalbero, noto anche come albero di ricerca binario, ha rami secondari a destra ea sinistra di se stessi.
  • Tutti i nodi sono collegati con coppie chiave-valore.
  • Le chiavi dei nodi presenti sulla sottostruttura sinistra sono più piccole delle chiavi del loro nodo genitore
  • Allo stesso modo, le chiavi dei nodi della sottostruttura sinistra hanno valori inferiori rispetto alle chiavi del loro nodo padre.

  1. C'è il nodo principale o livello genitore 11. Sotto di esso, ci sono nodi / rami sinistro e destro con i propri valori chiave
  2. Il sottoalbero destro ha valori chiave maggiori del nodo padre
  3. Il sottoalbero sinistro ha valori rispetto al nodo padre

Perché abbiamo bisogno di un albero di ricerca binario?

  • I due fattori principali che rendono l'albero di ricerca binario una soluzione ottimale a qualsiasi problema del mondo reale sono la velocità e l'accuratezza.
  • A causa del fatto che la ricerca binaria è in un formato simile a un ramo con relazioni genitore-figlio, l'algoritmo sa in quale posizione dell'albero devono essere cercati gli elementi. Ciò riduce il numero di confronti di valori-chiave che il programma deve effettuare per individuare l'elemento desiderato.
  • Inoltre, nel caso in cui l'elemento da cercare sia maggiore o minore del nodo padre, il nodo sa quale lato dell'albero cercare. Il motivo è che il sottoalbero sinistro è sempre minore del nodo padre e il sottoalbero destro ha valori sempre uguali o maggiori del nodo padre.
  • BST è comunemente utilizzato per implementare ricerche complesse, logiche di gioco robuste, attività di completamento automatico e grafica.
  • L'algoritmo supporta in modo efficiente operazioni come ricerca, inserimento ed eliminazione.

Tipi di alberi binari

Tre tipi di alberi binari sono:

  • Albero binario completo: tutti i livelli negli alberi sono pieni delle possibili eccezioni dell'ultimo livello. Allo stesso modo, tutti i nodi sono pieni, dirigendo l'estrema sinistra.
  • Albero binario completo: tutti i nodi hanno 2 nodi figli tranne la foglia.
  • Albero binario bilanciato o perfetto: nell'albero, tutti i nodi hanno due figli. Inoltre, c'è lo stesso livello di ogni sottonodo.

Come funziona l'albero di ricerca binario?

L'albero ha sempre un nodo radice e ulteriori nodi figlio, a sinistra oa destra. L'algoritmo esegue tutte le operazioni confrontando i valori con la radice e i suoi ulteriori nodi figlio nel sottoalbero sinistro o destro di conseguenza.

Dipende dall'elemento da inserire, cercare o eliminare, dopo il confronto, l'algoritmo può facilmente rilasciare la sottostruttura sinistra o destra del nodo radice.

BST offre principalmente i seguenti tre tipi di operazioni per il tuo utilizzo:

  • Cerca: cerca l'elemento dall'albero binario
  • Inserisci: aggiunge un elemento all'albero binario
  • Elimina: elimina l'elemento da un albero binario

Ogni operazione ha una propria struttura e metodo di esecuzione / analisi, ma la più complessa di tutte è l'operazione Elimina.

Operazione di ricerca

Iniziare sempre l'analisi dell'albero nel nodo radice e quindi spostarsi ulteriormente nella sottostruttura destra o sinistra del nodo radice a seconda che l'elemento da individuare sia minore o maggiore della radice.

  1. L'elemento da cercare è 10
  2. Confronta l'elemento con il nodo radice 12, 10 <12, quindi ti sposti nella sottostruttura sinistra. Non c'è bisogno di analizzare la sottostruttura di destra
  3. Ora confronta 10 con il nodo 7, 10> 7, quindi spostati nella sottostruttura di destra
  4. Quindi confronta 10 con il nodo successivo, che è 9, 10> 9, guarda nel sottoalbero figlio destro
  5. 10 corrispondenze con il valore nel nodo, 10 = 10, restituiscono il valore all'utente.

Inserisci operazione

Questa è un'operazione molto semplice. Innanzitutto, viene inserito il nodo radice, quindi il valore successivo viene confrontato con il nodo radice. Se il valore è maggiore di root, viene aggiunto alla sottostruttura destra e, se è minore della radice, viene aggiunto alla sottostruttura sinistra.

  1. C'è un elenco di 6 elementi che devono essere inseriti in un BST in ordine da sinistra a destra
  2. Inserisci 12 come nodo radice e confronta i valori successivi 7 e 9 per inserirli di conseguenza nella sottostruttura destra e sinistra
  3. Confronta i valori rimanenti 19, 5 e 10 con il nodo radice 12 e posizionali di conseguenza. 19> 12 posizionalo come figlio destro di 12, 5 <12 e 5 <7, quindi posizionalo come figlio sinistro di 7.
    1. Ora confronta 10, 10 è <12 e 10 è> 7 e 10 è> 9, posiziona 10 come sottostruttura a destra di 9.

Elimina operazioni

L'eliminazione è la più avanzata e complessa tra tutte le altre operazioni. Esistono più casi gestiti per l'eliminazione nella BST.

  • Caso 1 - Nodo con zero figli: questa è la situazione più semplice, basta eliminare il nodo che non ha più figli a destra oa sinistra.
  • Caso 2 - Nodo con un figlio: una volta eliminato il nodo, connetti semplicemente il suo nodo figlio con il nodo padre del valore eliminato.
  • Caso 3 Nodo con due figli: questa è la situazione più difficile e funziona secondo le due regole seguenti
    • 3a - In Order Predecessor: è necessario eliminare il nodo con due figli e sostituirlo con il valore più grande sulla sottostruttura sinistra del nodo eliminato
    • 3b - In Order Successor: è necessario eliminare il nodo con due figli e sostituirlo con il valore più grande sul sottoalbero destro del nodo eliminato

  1. Questo è il primo caso di eliminazione in cui elimini un nodo che non ha figli. Come puoi vedere nel diagramma che 19, 10 e 5 non hanno figli. Ma elimineremo 19.
  2. Elimina il valore 19 e rimuovi il collegamento dal nodo.
  3. Visualizza la nuova struttura della BST senza 19

  1. Questo è il secondo caso di eliminazione in cui elimini un nodo che ha 1 figlio, come puoi vedere nel diagramma che 9 ha un figlio.
  2. Elimina il nodo 9 e sostituiscilo con il suo figlio 10 e aggiungi un collegamento da 7 a 10
  3. Visualizza la nuova struttura della BST senza 9

  1. Qui eliminerai il nodo 12 che ha due figli
  2. L'eliminazione del nodo avverrà in base alla regola del predecessore in ordine, il che significa che l'elemento più grande sulla sottostruttura sinistra di 12 lo sostituirà.
  3. Elimina il nodo 12 e sostituiscilo con 10 poiché è il valore più grande nella sottostruttura sinistra
  4. Visualizza la nuova struttura della BST dopo l'eliminazione 12

  1. 1 Elimina un nodo 12 che ha due figli
  2. 2 L'eliminazione del nodo avverrà in base alla regola In Order Successor, il che significa che l'elemento più grande sulla sottostruttura destra di 12 lo sostituirà
  3. 3 Eliminare il nodo 12 e sostituirlo con 19 poiché è il valore più grande sulla sottostruttura destra
  4. 4 Visualizza la nuova struttura della BST dopo l'eliminazione 12

Termini importanti

  • Inserisci - Inserisce un elemento in un albero / crea un albero.
  • Cerca: cerca un elemento in un albero.
  • Preorder Traversal: attraversa un albero in modalità pre-order.
  • Inorder Traversal - Attraversa un albero in modo ordinato.
  • Postorder Traversal - Attraversa un albero in modalità post-order.

Sommario

  • BST è un algoritmo di livello avanzato che esegue varie operazioni basate sul confronto dei valori del nodo con il nodo radice.
  • Qualsiasi punto in una gerarchia padre-figlio rappresenta il nodo. Almeno un nodo padre o radice rimane sempre presente.
  • Sono presenti una sottostruttura sinistra e una sottostruttura destra. La sottostruttura sinistra contiene valori inferiori al nodo radice. Tuttavia, la sottostruttura destra contiene un valore maggiore del nodo radice.
  • Ogni nodo può avere zero, uno o due figli.
  • Un albero di ricerca binario facilita le operazioni primarie come la ricerca, l'inserimento e l'eliminazione.
  • Elimina che è il più complesso ha più casi, ad esempio un nodo senza figli, un nodo con un figlio e un nodo con due figli.
  • L'algoritmo viene utilizzato in soluzioni del mondo reale come giochi, dati di completamento automatico e grafica.