Albero di ricerca binario (BST) con esempio

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 di sinistra sono più piccole delle chiavi del nodo genitore
• Allo stesso modo, le chiavi dei nodi della sottostruttura sinistra hanno valori inferiori rispetto alle chiavi del nodo principale.

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

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 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 genitore, il nodo sa quale lato dell'albero cercare. Il motivo è che il sottoalbero di sinistra è sempre minore del nodo genitore e il sottoalbero di destra ha valori sempre uguali o maggiori del nodo genitore.
• 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 ciascun sottonodo.

Scopri 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:

• 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 un proprio metodo di esecuzione/analisi, ma la più complessa di tutte è l'operazione Delete.

Cerca Operaproduzione

Iniziare sempre l'analisi dell'albero dal nodo radice e poi spostarsi ulteriormente verso il sottoalbero destro o sinistro del nodo radice a seconda che l'elemento da individuare sia inferiore 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 di sinistra. Non è necessario analizzare il sottoalbero destro
3. Ora confronta 10 con il nodo 7, 10 > 7, quindi spostati nel sottoalbero di destra
4. Quindi confronta 10 con il nodo successivo, che è 9, 10 > 9, guarda nel sottoalbero destro
5. 10 corrispondenze con il valore nel nodo, 10 = 10, restituiscono il valore all'utente.

Pseudo codice 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

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 della radice, viene aggiunto al sottoalbero di destra, mentre se è minore della radice, viene aggiunto al sottoalbero di 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 nel sottoalbero destro e sinistro
3. Confronta i restanti valori 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 BST, ci sono alcuni casi, ad esempio eliminare una radice o eliminare un nodo foglia. Inoltre, dopo aver eliminato una radice, dobbiamo pensare al nodo radice.

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 con zero figli: questa è la situazione più semplice, basta eliminare il nodo che non ha più figli né a destra né a sinistra.
• Caso 2 – Nodo con un figlio: una volta eliminato il nodo, collega semplicemente il suo nodo figlio con il nodo genitore del valore eliminato.
• Caso 3 Nodo con due figli: questa è la situazione più difficile e funziona con le due regole seguenti
• 3a – In Order Predecessor: è necessario eliminare il nodo con due figli e sostituirlo con il valore più grande nel sottoalbero sinistro del nodo eliminato
• 3b – Nell'ordine successore: è necessario eliminare il nodo con due figli e sostituirlo con il valore più grande nel sottoalbero destro del nodo eliminato

1. Questo è il primo caso di eliminazione in cui si elimina un nodo che non ha figli. Come puoi vedere nel diagramma, 19, 10 e 5 non hanno figli. Ma ne 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 dell'ordine, il che significa che l'elemento più grande sul sottoalbero sinistro di 12 lo sostituirà.
3. Elimina il nodo 12 e sostituiscilo con 10 poiché è il valore più grande nel sottoalbero di sinistra
4. Visualizza la nuova struttura del BST dopo aver eliminato 12

1. 1 Eliminare 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 nel sottoalbero destro di 12 lo sostituirà
3. 3 Eliminare il nodo 12 e sostituirlo con 19 poiché è il valore più grande nel sottoalbero destro
4. 4 Visualizza la nuova struttura del BST dopo aver eliminato 12

Pseudo codice 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 to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

Termini importanti

• Inserisci: inserisce un elemento in un albero/crea un albero.
• Cerca: cerca un elemento in un albero.
• Attraversamento in preordine: attraversa un albero in modalità preordine.
• Attraversamento in ordine: attraversa un albero in ordine.
• Attraversamento post-ordine: attraversa un albero in modo post-ordine.

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 genitore-figlio rappresenta il nodo. Almeno un nodo genitore o radice rimane sempre presente.
• Ci sono un sottoalbero sinistro e un sottoalbero destro. Il sottoalbero di sinistra contiene valori inferiori al nodo radice. Tuttavia, il sottoalbero destro 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 ricerca, inserimento ed eliminazione.
• Essendo l'eliminazione la più complessa, ci sono casi multipli, ad esempio un nodo senza elementi figlio, un nodo con un elemento figlio e un nodo con due elementi figlio.
• L'algoritmo viene utilizzato in soluzioni del mondo reale come giochi, dati di completamento automatico e grafica.