Gli alberi di ricerca binari supportano tre operazioni principali: inserimento di elementi, eliminazione di elementi e ricerca (controllando se è presente una chiave).

SearchingEdit

La ricerca in un albero di ricerca binario per una chiave specifica può essere programmata in modo ricorsivo o iterativo.

Iniziamo esaminando il nodo radice. Se l’albero è null, la chiave che stiamo cercando non esiste nell’albero. Altrimenti, se la chiave è uguale a quella della radice, la ricerca ha successo e restituiamo il nodo. Se la chiave è inferiore a quella della radice, cerchiamo la sottostruttura sinistra., Allo stesso modo, se la chiave è maggiore di quella della radice, cerchiamo la sottoalbero destra. Questo processo viene ripetuto finché la chiave non viene trovata o il sottoalbero rimanente non è nullo. Se la chiave cercata non viene trovata dopo aver raggiunto un sottoalbero null, la chiave non è presente nell’albero. Questo è facilmente espresso come un algoritmo ricorsivo (implementato in Python):

Lo stesso algoritmo può essere implementato iterativamente:

Questi due esempi non supportano i duplicati, cioè si basano sulla relazione di ordine che è un ordine totale.

Si può notare che l’algoritmo ricorsivo è ricorsivo di coda., In un linguaggio che supporta l’ottimizzazione delle chiamate di coda, gli esempi ricorsivi e iterativi verranno compilati in programmi equivalenti.

Poiché nel peggiore dei casi questo algoritmo deve cercare dalla radice dell’albero alla foglia più lontana dalla radice, l’operazione di ricerca richiede tempo proporzionale all’altezza dell’albero (vedi terminologia dell’albero). In media, gli alberi di ricerca binari con le chiavi dei nodi hanno altezza O (log |Nodes|). Tuttavia, nel peggiore dei casi, gli alberi di ricerca binari possono avere altezza O(|Nodes/), quando l’albero sbilanciato assomiglia a una lista collegata (albero degenerato).,

Ricerca con duplicati allowedEdit

Se la relazione di ordine è solo un preordine totale, una ragionevole estensione della funzionalità è la seguente: anche in caso di uguaglianza cerca fino alle foglie. Permettendo così di specificare (o hard-wire) una direzione, dove inserire un duplicato, a destra oa sinistra di tutti i duplicati nell’albero finora. Se la direzione è cablata, entrambe le scelte, destra e sinistra, supportano una pila con inserisci duplicato come operazione push ed elimina come operazione pop.,: 155

Un tipo di albero binario dotato di tale funzione di ricerca diventa stabile.

InsertionEdit

L’inserimento inizia come inizierebbe una ricerca; se la chiave non è uguale a quella della radice, cerchiamo i sottoalberi sinistro o destro come prima. Alla fine, raggiungeremo un nodo esterno e aggiungeremo la nuova coppia chiave-valore (qui codificata come record ‘newNode’) come figlio destro o sinistro, a seconda della chiave del nodo., In altre parole, esaminiamo la radice e inseriamo ricorsivamente il nuovo nodo nella sottostruttura sinistra se la sua chiave è inferiore a quella della radice, o la sottostruttura destra se la sua chiave è maggiore o uguale alla radice.

Ecco come un tipico inserimento di albero di ricerca binario potrebbe essere eseguito in un albero binario in C++:

In alternativa, una versione non ricorsiva potrebbe essere implementata in questo modo., L’uso di un puntatore a puntatore per tenere traccia di dove proveniamo consente al codice di evitare il controllo esplicito e la gestione del caso in cui è necessario inserire un nodo alla radice dell’albero:

La precedente variante procedurale distruttiva modifica l’albero in posizione. Utilizza solo lo spazio heap costante (e la versione iterativa utilizza anche lo spazio stack costante), ma la versione precedente dell’albero è persa., In alternativa, come nel seguente esempio Python, possiamo ricostruire tutti gli antenati del nodo inserito; qualsiasi riferimento alla radice dell’albero originale rimane valido, rendendo l’albero una struttura dati persistente:

La parte che viene ricostruita utilizza lo spazio O(log n) nel caso medio e O(n) nel caso peggiore.

In entrambe le versioni, questa operazione richiede tempo proporzionale all’altezza dell’albero nel peggiore dei casi, che è O(log n) tempo nel caso medio su tutti gli alberi, ma O(n) tempo nel peggiore dei casi.,

Un altro modo per spiegare l’inserimento è che per inserire un nuovo nodo nell’albero, la sua chiave viene prima confrontata con quella della radice. Se la sua chiave è inferiore a quella della radice, viene quindi confrontata con la chiave del figlio sinistro della radice. Se la sua chiave è maggiore, viene confrontata con il figlio destro della radice. Questo processo continua, fino a quando il nuovo nodo viene confrontato con un nodo foglia, quindi viene aggiunto come figlio destro o sinistro di questo nodo, a seconda della sua chiave: se la chiave è inferiore alla chiave della foglia, viene inserita come figlio sinistro della foglia, altrimenti come figlio destro della foglia.,

Esistono altri modi per inserire nodi in un albero binario, ma questo è l’unico modo per inserire nodi alle foglie e allo stesso tempo preservare la struttura BST.

DeletionEdit

Quando si rimuove un nodo da un albero di ricerca binario è obbligatorio mantenere la sequenza in ordine dei nodi. Ci sono molte possibilità per farlo. Tuttavia, il seguente metodo che è stato proposto da T. Hibbard nel 1962 garantisce che le altezze dei sottoalberi soggetti sono cambiati da al massimo uno., Ci sono tre possibili casi da considerare:

• Eliminazione di un nodo senza figli: basta rimuovere il nodo dall’albero.
• Eliminazione di un nodo con un figlio: rimuovere il nodo e sostituirlo con il suo figlio.
• Eliminazione di un nodo D con due figli: scegliere il predecessore in ordine di D o il successore in ordine E (vedi figura). Invece di eliminare D, sovrascrivi la sua chiave e il suo valore con E. Se E non ha un figlio, rimuovi E dal suo genitore precedente G. Se E ha un figlio F, è un figlio giusto, in modo che sostituisca E al genitore di E.,

In tutti i casi, quando D sembra essere la radice, fai di nuovo la radice del nodo sostitutivo.

I nodi con due figli sono più difficili da eliminare., Il successore in ordine di un nodo è il figlio più a sinistra del sottoalbero destro e il predecessore in ordine di un nodo è il figlio più a destra del sottoalbero sinistro. In entrambi i casi, questo nodo avrà solo uno o nessun figlio. Eliminalo secondo uno dei due casi più semplici sopra.

L’uso coerente del successore in ordine o del predecessore in ordine per ogni istanza del caso a due figli può portare a un albero sbilanciato, quindi alcune implementazioni selezionano l’una o l’altra in momenti diversi.,

Runtime analysis: Sebbene questa operazione non attraversi sempre l’albero fino a una foglia, questa è sempre una possibilità; quindi nel peggiore dei casi richiede tempo proporzionale all’altezza dell’albero. Non richiede di più anche quando il nodo ha due figli, poiché segue ancora un singolo percorso e non visita alcun nodo due volte.,

TraversalEdit

Una volta che l’albero di ricerca binario è stato creato, i suoi elementi possono essere recuperati in ordine ricorsivamente attraversando il sottoalbero sinistro del nodo radice, accedendo al nodo stesso, quindi attraversando ricorsivamente il sottoalbero destro del nodo, continuando questo modello con ogni nodo nell’albero come si accede ricorsivamente. Come con tutti gli alberi binari, si può condurre un attraversamento pre-ordine o un attraversamento post-ordine, ma nessuno dei due è probabile che sia utile per gli alberi di ricerca binari., Un attraversamento in ordine di un albero di ricerca binario comporterà sempre un elenco ordinato di elementi del nodo (numeri, stringhe o altri elementi comparabili).

Il codice per l’attraversamento in ordine in Python è riportato di seguito. Chiamerà callback (alcune funzioni che il programmatore desidera richiamare sul valore del nodo, come la stampa sullo schermo) per ogni nodo nell’albero.

Traversal richiede tempo O(n), poiché deve visitare ogni nodo. Questo algoritmo è anche O (n), quindi è asintoticamente ottimale.

Traversal può anche essere implementato iterativamente. Per alcune applicazioni, ad esempio, maggiore ricerca uguale, ricerca approssimativa, un’operazione per attraversamento a passo singolo (iterativo) può essere molto utile. Questo è, ovviamente, implementato senza il costrutto di callback e prende O(1) in media e O (log n) nel peggiore dei casi.

VerificationEdit

A volte abbiamo già un albero binario e dobbiamo determinare se si tratta di un BST. Questo problema ha una semplice soluzione ricorsiva.,

La proprietà BST—ogni nodo sul sottoalbero destro deve essere più grande del nodo corrente e ogni nodo sul sottoalbero sinistro deve essere più piccolo del nodo corrente—è la chiave per capire se un albero è un BST o meno. L’algoritmo greedy-semplicemente attraversa l’albero, ad ogni nodo controlla se il nodo contiene un valore più grande del valore sul figlio sinistro e più piccolo del valore sul figlio destro—non funziona per tutti i casi., Considera il seguente albero:

 20 / \ 10 30 / \ 5 40

Nell’albero sopra, ogni nodo soddisfa la condizione che il nodo contenga un valore più grande del suo figlio sinistro e più piccolo del suo figlio destro, eppure non è un BST: il valore 5 si trova nella sottoalbero destro del nodo contenente 20, una violazione della proprietà BST.

Invece di prendere una decisione basata esclusivamente sui valori di un nodo e dei suoi figli, abbiamo anche bisogno di informazioni che scorrono anche dal genitore., Nel caso dell’albero sopra, se potessimo ricordare il nodo contenente il valore 20, vedremmo che il nodo con valore 5 sta violando il contratto di proprietà BST.,

Così, con la condizione che abbiamo bisogno di controllare in ogni nodo è:

• se il nodo è la sinistra figlio di suo padre, allora deve essere inferiore (o uguale) al genitore e deve passare il valore da suo padre alla sua destra sottostruttura per assicurarsi che nessuno dei nodi nel sottoalbero è maggiore del genitore
• se il nodo è il diritto del bambino di suo padre, allora deve essere più grande che il padre e deve passare il valore da suo padre alla sua sinistra sottostruttura per assicurarsi che nessuno dei nodi nel sottoalbero è minore del padre.,

Una soluzione ricorsiva in C++ può spiegare ulteriormente questo:

node->key+1 enode->key-1 sono fatti per consentire solo elementi distinti in BST.

Se vogliamo che anche gli stessi elementi siano presenti, possiamo usare solo node->key in entrambi i punti.

La chiamata iniziale a questa funzione può essere qualcosa del genere:

if (isBST(root, INT_MIN, INT_MAX)) { puts("This is a BST.");} else { puts("This is NOT a BST!");}

Essenzialmente continuiamo a creare un intervallo valido (a partire da ) e continuiamo a ridurlo per ogni nodo mentre scendiamo ricorsivamente.,

Come indicato nella sezione #Traversal, un attraversamento in ordine di un albero di ricerca binario restituisce i nodi ordinati. Quindi abbiamo solo bisogno di mantenere l’ultimo nodo visitato mentre attraversiamo l’albero e verificare se la sua chiave è più piccola (o più piccola/uguale, se i duplicati devono essere consentiti nell’albero) rispetto alla chiave corrente.

Algoritmi parallelimodifica

Esistono anche algoritmi paralleli per alberi di ricerca binari, tra cui l’inserimento/eliminazione di più elementi, la costruzione da array, il filtro con determinati predicatori, l’appiattimento su un array, la fusione/sottrazione / intersezione di due alberi, ecc., Questi algoritmi possono essere implementati utilizzando algoritmi ad albero basati su join, che possono anche mantenere l’albero bilanciato utilizzando diversi schemi di bilanciamento (tra cui albero AVL, albero rosso-nero, albero bilanciato con peso e treap) .