Albero di ricerca binario (BST) con esempio

Cos'è un albero di ricerca binario?

L'albero di ricerca binario (BST) è un algoritmo avanzato utilizzato per analizzare un nodo, i suoi rami sinistro e destro, modellati in una struttura ad albero, e restituirne il valore. Il BST è concepito sull'architettura di un algoritmo di ricerca binaria di base; pertanto, consente ricerche, inserimenti e rimozioni di nodi più rapidi. Questo rende il programma estremamente veloce e preciso.

Attributi dell'albero di ricerca binario

Un BST è composto da più nodi e comprende i seguenti attributi:

• I nodi dell'albero sono rappresentati in una relazione genitore-figlio.
• Ogni nodo genitore può avere zero nodi figli o un massimo di due sottonodi o sottoalberi sui lati sinistro e destro.
• Ogni sottoalbero, noto anche come albero di ricerca binario, ha sottorami a destra e a sinistra.
• Tutti i nodi sono collegati con coppie chiave-valore.
• Le chiavi dei nodi presenti nel sottoalbero sinistro sono più piccole delle chiavi del loro nodo genitore.
• Analogamente, le chiavi dei nodi presenti nel sottoalbero destro sono maggiori delle chiavi del loro nodo genitore.

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

Perché abbiamo bisogno di un albero di ricerca binario?

• I due fattori principali che rendono un albero di ricerca binario una soluzione ottimale per qualsiasi problema del mondo reale sono la velocità e la precisione.
• Dato che la ricerca binaria avviene 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ò diminuisce 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 in quale lato dell'albero effettuare la ricerca. Il motivo è che il sottoalbero sinistro è sempre minore del nodo padre, mentre 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 dell'albero sono pieni, con una possibile eccezione all'ultimo livello. Analogamente, tutti i nodi sono pieni, procedendo verso sinistra.
• Albero binario completo: Tutti i nodi, tranne la foglia, hanno 2 nodi figli.
• Albero binario bilanciato o perfetto: Nell'albero, tutti i nodi hanno due figli. Inoltre, ogni sotto-nodo ha lo stesso livello.

Scopri di più Albero binario nella struttura dei dati se siete interessati.

Come funziona l'albero di ricerca binaria?

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

A seconda dell'elemento da inserire, cercare o eliminare, dopo il confronto, l'algoritmo può facilmente eliminare il sottoalbero sinistro o destro del nodo radice.

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

• Ricerca: cerca l'elemento nell'albero binario.
• Inserisci: aggiunge un elemento all'albero binario.
• Elimina: elimina l'elemento da un albero binario.

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

Cerca Operaproduzione

È sempre consigliabile iniziare l'analisi dell'albero dal nodo radice e poi procedere verso il sottoalbero destro o sinistro 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 al sottoalbero sinistro. Non è necessario analizzare il sottoalbero destro.
3. Ora confronta 10 con il nodo 7, 10 > 7, quindi spostati al sottoalbero destro.
4. Quindi confronta 10 con il nodo successivo, che è 9, 10 > 9, guarda nel figlio del sottoalbero destro.
5. 10 corrispondenze con il valore nel nodo, 10 = 10, restituiscono il valore all'utente.

Soprannome Code per la ricerca in BST

search(element, root)
    if !root
        return -1
    if root.value == element
        return 1
    if root.value < element
        search(element, root.right)
    else
        search(element, root.left)

inserire Operaproduzione

Si tratta di un'operazione molto semplice. Innanzitutto, viene inserito il nodo radice, quindi il valore successivo viene confrontato con il nodo radice. Se il valore è maggiore della radice, viene aggiunto al sottoalbero destro, altrimenti, se è minore della radice, viene aggiunto al sottoalbero sinistro.

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 rispettivamente nel sottoalbero destro e sinistro.
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. Ora confronta 10, 10 è < 12 e 10 è > 7 e 10 è > 9, posiziona 10 come sottoalbero destro di 9.

Pseudocodice per l'inserimento di un nodo in BST

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
        y = x
        if x.value < element.value
            x = x.right
        else
            x = x.left
    if y.value < element
        y.right = element
    else
        y.left = element

Elimina Operazioni

Per eliminare un nodo da un albero di ricerca binario (BST), esistono diversi casi, ad esempio l'eliminazione della radice o l'eliminazione di un nodo foglia. Inoltre, dopo aver eliminato la radice, è necessario considerare il nodo radice stesso.

Diciamo che vogliamo eliminare un nodo foglia, possiamo semplicemente eliminarlo, ma se vogliamo eliminare una radice, dobbiamo sostituire il valore della radice con un altro nodo. Prendiamo il seguente esempio:

• Caso 1 – Nodo senza figli: Questa è la situazione più semplice: basta eliminare il nodo che non ha altri figli a destra o a sinistra.
• Caso 2 – Nodo con un figlio: Una volta eliminato il nodo, è sufficiente collegare il suo nodo figlio al nodo padre del valore eliminato.
• Caso 3 – Nodo con due figli: Questa è la situazione più difficile e si basa sulle seguenti due regole:
  • 3a – Predecessore in ordine: È necessario eliminare il nodo con due figli e sostituirlo con il valore più grande presente nel sottoalbero sinistro del nodo eliminato.
  • 3b – Successore in ordine: È necessario eliminare il nodo con due figli e sostituirlo con il valore più piccolo presente nel sottoalbero destro del nodo eliminato.

1. Questo è il primo caso di cancellazione, in cui si elimina un nodo che non ha figli. Come si può vedere nel diagramma, i nodi 19, 10 e 5 non hanno figli. Ma elimineremo il nodo 19.
2. Elimina il valore 19 e rimuovi il collegamento dal nodo.
3. Visualizza la nuova struttura dell'albero di ricerca binario senza 19.

1. Questo è il secondo caso di eliminazione, in cui si elimina un nodo che ha 1 figlio. Come si può vedere nel diagramma, il nodo 9 ha un figlio.
2. Elimina il nodo 9 e sostituiscilo con il suo figlio 10, quindi aggiungi un collegamento dal nodo 7 al nodo 10.
3. Visualizza la nuova struttura dell'albero di ricerca binario 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 nel sottoalbero sinistro di 12 lo sostituirà.
3. Elimina il nodo 12 e sostituiscilo con 10, poiché è il valore più grande nel sottoalbero sinistro.
4. Visualizza la nuova struttura dell'albero di ricerca binario dopo l'eliminazione di 12.

1. Elimina il nodo 12 che ha due figli.
2. L'eliminazione del nodo avverrà in base alla regola In-Order Successor, il che significa che l'elemento più piccolo del sottoalbero destro di 12 lo sostituirà.
3. Elimina il nodo 12 e sostituiscilo con 19, poiché è il valore più piccolo nel sottoalbero di destra.
4. Visualizza la nuova struttura dell'albero di ricerca binario dopo l'eliminazione di 12.

Soprannome Code per eliminare un nodo

delete (value, root):
    Node x = root
    Node y = NULL
    # searching the node
    while x:
        y = x
        if x.value < value
            x = x.right
        else if x.value > value
            x = x.left
        else if value == x
            break
    # if the node is not null, then replace it with successor
    if y.left or y.right:
        newNode = GetInOrderSuccessor(y)
        root.value = newNode.value
        # after copying the value of successor, delete the successor
        free(newNode)
    else
        free(y)

Termini importanti

• Inserisci: Inserisce un elemento in un albero / crea un albero.
• Ricerca: Ricerca un elemento in una struttura ad albero.
• Preordina Traversale: Attraversa un albero seguendo un ordine predefinito.
• Attraversamento in ordine: Attraversa un albero in modo ordinato.
• Attraversamento in postordine: Attraversa un albero in modo post-ordine.

DOMANDE FREQUENTI