Albero di ricerca binario: un database strutturato contenente nodi, due collegamenti ad altri nodi, destro e sinistro. I nodi sono un oggetto della classe che ha dati e NULL è il segno che segna la fine dell'albero.
È spesso indicato come BST, che ha una proprietà speciale: i nodi più grandi della radice si trovano a destra e quelli più piccoli a sinistra.
Teoria generale e terminologia
In un albero di ricerca binario, ogni nodo, esclusa la radice, è connesso da un bordo diretto da un nodo all' altro, chiamato genitore. Ciascuno di essi può essere connesso a un numero arbitrario di nodi, chiamati figli. I nodi senza "figli" sono chiamati foglie (nodi esterni). Gli elementi che non sono foglie sono chiamati interni. I nodi con lo stesso genitore sono fratelli. Il nodo più in alto è chiamato radice. In BST, assegna un elemento a ciascun nodo e assicurati che disponga di una proprietà speciale impostata per loro.
Terminologia dell'albero:
- La profondità di un nodo è il numero di spigoli definiti dalla radice ad esso.
- L' altezza di un nodo è il numero di bordi definiti da esso alla foglia più profonda.
- L' altezza dell'albero è determinata dall' altezza della radice.
- L'albero di ricerca binario è un design speciale, fornisce il miglior rapporto tra altezza e numero di nodi.
- Altezza h con N nodi al massimo O (log N).
Puoi facilmente dimostrarlo contando i nodi ad ogni livello, partendo dalla radice, supponendo che ne contenga il maggior numero: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Risolvendo questo per h si ottiene h=O (log n).
Vantaggi del legno:
- Riflette le relazioni strutturali dei dati.
- Utilizzato per rappresentare le gerarchie.
- Garantire installazione e ricerca efficienti.
- Gli alberi sono dati molto flessibili, che ti consentono di spostare i sottoalberi con il minimo sforzo.
Metodo di ricerca
In generale, per determinare se un valore è nel BST, avvia un albero di ricerca binario alla sua radice e determina se soddisfa i requisiti:
- essere alla radice;
- essere nel sottoalbero sinistro della radice;
- nel sottoalbero destro della radice.
Se nessun registro di base è soddisfatto, viene eseguita una ricerca ricorsiva nel sottoalbero corrispondente. In re altà ci sono due opzioni di base:
- L'albero è vuoto - restituisce false.
- Il valore è nel nodo radice - restituisce true.
Va notato che un albero di ricerca binario con uno schema sviluppato inizia sempre la ricerca lungo il percorso dalla radice alla foglia. Nel peggiore dei casi, arriva fino alla foglia. Pertanto, il momento peggiore è proporzionale alla lunghezza del percorso più lungo dalla radice alla foglia, che è l' altezza dell'albero. In generale, questo è il momento in cui è necessario sapere quanto tempo ci vuole per cercare in funzione del numero di valori memorizzati nell'albero.
In altre parole, esiste una relazione tra il numero di nodi in un BST e l' altezza di un albero, a seconda della sua "forma". Nel peggiore dei casi, i nodi hanno un solo figlio e un albero di ricerca binario bilanciato è essenzialmente un elenco collegato. Ad esempio:
50
/
10
15
30
/
20
Questo albero ha 5 nodi e altezza=5. Trovare valori nell'intervallo 16-19 e 21-29 richiederà il seguente percorso dalla radice alla foglia (il nodo contenente il valore 20), ad es., ci vorrà del tempo proporzionale al numero di nodi. Nella migliore delle ipotesi, hanno tutti 2 figli e le foglie si trovano alla stessa profondità.
Questo albero di ricerca binario ha 7 nodi e altezza=3. In generale, un albero come questo (albero completo) avrà un' altezza di circa log 2 (N), dove N è il numero di nodi nell'albero. Il valore del log 2 (N) è il numero di volte (2) che N può essere diviso prima che venga raggiunto lo zero.
Riassumendo: il momento peggiore necessario per la ricerca in BST è O (altezza dell'albero). L'albero "lineare" del caso peggiore è O(N), dove N è il numero di nodi nell'albero. Nella migliore delle ipotesi, un albero "completo" è O(log N).
Inserimento binario BST
Mi chiedo dove dovrebbe essereil nuovo nodo si trova nel BST, è necessario comprendere la logica, deve essere posizionato dove l'utente lo trova. Inoltre, devi ricordare le regole:
- Non sono consentiti duplicati, il tentativo di inserire un valore duplicato genererà un'eccezione.
- Il metodo di inserimento pubblico utilizza un metodo ricorsivo "helper" di supporto per inserire effettivamente.
- Un nodo contenente un nuovo valore viene sempre inserito come foglia in BST.
- Il metodo public insert restituisce void, ma il metodo helper restituisce un BSTnode. Lo fa per gestire il caso in cui il nodo passato ad esso è null.
In generale, il metodo helper indica che se l'albero di ricerca binario originale è vuoto, il risultato è un albero con un nodo. In caso contrario, il risultato sarà un puntatore allo stesso nodo passato come argomento.
Cancellazione nell'algoritmo binario
Come ci si potrebbe aspettare, l'eliminazione di un elemento implica la ricerca di un nodo che contenga il valore da rimuovere. Ci sono diverse cose in questo codice:
- BST usa un metodo di eliminazione di supporto e sovraccarico. Se l'elemento che stai cercando non è nell'albero, il metodo di supporto verrà eventualmente chiamato con n==null. Questo non è considerato un errore, l'albero semplicemente non cambia in questo caso. Il metodo dell'helper di eliminazione restituisce un valore: un puntatore all'albero aggiornato.
- Quando una foglia viene rimossa, la rimozione dall'albero di ricerca binario imposta il corrispondente puntatore figlio del suo genitore su null, o la radice su null se quella rimossa èil nodo è una radice e non ha figli.
- Nota che la chiamata di cancellazione deve essere una delle seguenti: root=delete (root, key), n.setLeft (delete (n.getLeft(), key)), n.setRight (delete(n. getRight(), chiave)). Pertanto, in tutti e tre i casi è corretto che il metodo delete restituisca semplicemente null.
- Quando la ricerca del nodo contenente il valore da cancellare riesce, ci sono tre opzioni: il nodo da cancellare è una foglia (non ha figli), il nodo da cancellare ha un figlio, ne ha due bambini.
- Quando il nodo da rimuovere ha un figlio, puoi semplicemente sostituirlo con un figlio, restituendo un puntatore al figlio.
- Se il nodo da eliminare ha zero o 1 figlio, il metodo delete "seguirà il percorso" dalla radice a quel nodo. Quindi il momento peggiore è proporzionale all' altezza dell'albero, sia per la ricerca che per l'inserimento.
Se il nodo da rimuovere ha due figli, vengono eseguiti i seguenti passaggi:
- Trova il nodo da eliminare, seguendo il percorso dalla radice ad esso.
- Trova il valore più piccolo di v nel sottoalbero di destra, proseguendo lungo il percorso verso la foglia.
- Rimuovi ricorsivamente il valore di v, segui lo stesso percorso del passaggio 2.
- Così, nel peggiore dei casi, il percorso dalla radice alla foglia viene eseguito due volte.
Ordine delle traverse
Traversal è un processo che visita tutti i nodi di un albero. Poiché un albero di ricerca binario C è una struttura di dati non lineare, non esiste un attraversamento univoco. Ad esempio, a volte diversi algoritmi di attraversamentoraggruppati nei seguenti due tipi:
- profondità di attraversamento;
- primo passaggio.
C'è un solo tipo di attraversamento della larghezza: bypassare il livello. Questa traversata visita i nodi di livello in basso ea sinistra, in alto ea destra.
Ci sono tre diversi tipi di attraversamenti di profondità:
- Preordine superato - prima visita il genitore e poi il bambino sinistro e destro.
- Passing InOrder - visitare il figlio sinistro, poi il genitore e il figlio destro.
- Past the PostOrder - visitare il figlio sinistro, poi il figlio destro, poi il genitore.
Esempio per quattro attraversamenti di un albero di ricerca binario:
- Preordine - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
- InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
- PostOrdine - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
- Ordine di livello - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.
La figura mostra l'ordine in cui i nodi vengono visitati. Il numero 1 è il primo nodo in una particolare traversata e 7 è l'ultimo nodo.
Questi attraversamenti generali possono essere rappresentati come un unico algoritmo, supponendo che ogni nodo venga visitato tre volte. Il tour di Eulero è una passeggiata attorno a un albero binario in cui ogni bordo viene trattato come un muro che l'utente non può attraversare. In questa passeggiata, ogni nodo sarà visitato o a sinistra, o in basso, oa destra. Il giro di Eulero, che visita i nodi a sinistra, fa sì che la preposizione venga ignorata. Quando i nodi sottostanti vengono visitati, vengono attraversati in ordine. E quando vengono visitati i nodi a destra, ottienibypass passo dopo passo.
Navigazione e debug
Per facilitare la navigazione nell'albero, crea funzioni che prima controllano se sono il figlio sinistro o destro. Per modificare la posizione di un nodo, deve esserci un facile accesso al puntatore sul nodo padre. Implementare correttamente un albero è molto difficile, quindi è necessario conoscere e applicare i processi di debug. Un albero di ricerca binario con un'implementazione ha spesso puntatori che in re altà non indicano la direzione di marcia.
Per capire tutto questo, viene utilizzata una funzione che controlla se l'albero può essere corretto e aiuta a trovare molti errori. Ad esempio, controlla se il nodo padre è un nodo figlio. Con assert(is_wellformed(root)) molti errori possono essere rilevati prematuramente. Usando un paio di punti di interruzione dati all'interno di questa funzione, puoi anche determinare esattamente quale puntatore è sbagliato.
Funzione Konsolenausgabe
Questa funzione scarica l'intero albero sulla console ed è quindi molto utile. L'ordine in cui viene eseguito l'obiettivo di output dell'albero è:
- Per fare ciò, devi prima determinare quali informazioni verranno emesse attraverso il nodo.
- E devi anche sapere quanto è largo e alto l'albero per tenere conto di quanto spazio lasciare.
- Le seguenti funzioni calcolano queste informazioni per l'albero e ogni sottoalbero. Poiché puoi scrivere sulla console solo riga per riga, dovrai anche stampare l'albero riga per riga.
- Ora abbiamo bisogno di un altro modo per ritirarcil'intero albero, non solo riga per riga.
- Con l'aiuto della funzione dump, puoi leggere l'albero e migliorare significativamente l'algoritmo di output, per quanto riguarda la velocità.
Tuttavia, questa funzione sarà difficile da usare su alberi di grandi dimensioni.
Copia costruttore e distruttore
Poiché un albero non è una struttura dati banale, è meglio implementare un costruttore di copie, un distruttore e un operatore di assegnazione. Il distruttore è facile da implementare in modo ricorsivo. Per alberi molto grandi, può gestire "heap overflow". In questo caso, è formulato in modo iterativo. L'idea è di rimuovere la foglia che rappresenta il valore più piccolo di tutte le foglie, quindi si trova sul lato sinistro dell'albero. Tagliare le prime foglie ne crea di nuove e l'albero si restringe fino a quando non cessa di esistere.
Il costruttore di copia può anche essere implementato in modo ricorsivo, ma fai attenzione se viene generata un'eccezione. Altrimenti, l'albero diventa rapidamente confuso e soggetto a errori. Ecco perché è preferita la versione iterativa. L'idea è di passare attraverso il vecchio albero e il nuovo albero, come si farebbe nel distruttore, clonando tutti i nodi che si trovano nel vecchio albero ma non quelli nuovi.
Con questo metodo, l'implementazione dell'albero di ricerca binario è sempre in uno stato integro e può essere rimossa dal distruttore anche in uno stato incompleto. Se si verifica un'eccezione, tutto ciò che devi fare è indicare al distruttore di eliminare l'albero semilavorato. operatore di assegnazionepuò essere facilmente implementato utilizzando Copy & Swap.
Creazione di un albero di ricerca binario
Gli alberi di ricerca binari ottimali sono incredibilmente efficienti se gestiti correttamente. Alcune regole per gli alberi di ricerca binari:
- Un nodo padre ha al massimo 2 nodi figlio.
- Il nodo figlio sinistro è sempre inferiore al nodo padre.
- Un nodo figlio valido è sempre maggiore o uguale al nodo padre.
L'array che verrà utilizzato per costruire l'albero di ricerca binario:
- Una matrice intera di base di sette valori in ordine non ordinato.
- Il primo valore nell'array è 10, quindi il primo passo per costruire l'albero è creare un nodo radice 10, come mostrato qui.
- Con un insieme di nodi radice, tutti gli altri valori saranno figli di questo nodo. Facendo riferimento alle regole, il primo passo da fare per aggiungere 7 all'albero è confrontarlo con il nodo radice.
- Se il valore 7 è inferiore a 10, diventerà il nodo figlio sinistro.
- Se il valore 7 è maggiore o uguale a 10, si sposterà a destra. Poiché 7 è noto per essere inferiore a 10, è designato come il nodo figlio sinistro.
- Esegui ricorsivamente confronti per ogni elemento.
- Seguendo lo stesso schema, esegui lo stesso confronto con il 14° valore nell'array.
- Confronto del valore 14 con il nodo radice 10, sapendo che 14 è il figlio corretto.
- Camminando attraverso l'array,vieni a 20.
- Inizia confrontando l'array con 10, qualunque sia maggiore. Quindi spostati a destra e confrontalo con 14, lui ha più di 14 anni e non ha figli a destra.
- Ora c'è un valore di 1. Seguendo lo stesso schema degli altri valori, confronta 1 con 10, spostandoti a sinistra e confrontando con 7 e infine con l'1 figlio sinistro del 7° nodo.
- Se il valore è 5, confrontalo con 10. Poiché 5 è inferiore a 10, passa a sinistra e confrontalo con 7.
- Sapendo che 5 è minore di 7, continua lungo l'albero e confronta 5 con 1 valore.
- Se 1 non ha figli e 5 è maggiore di 1, allora 5 è un figlio valido di 1 nodo.
- Infine inserisci il valore 8 nell'albero.
- Quando 8 è inferiore a 10, spostalo a sinistra e confrontalo con 7, 8 è maggiore di 7, quindi spostalo a destra e completa l'albero, facendo di 8 un vero figlio di 7.
Ottenere e valutare la semplice eleganza di ottimi alberi di ricerca binari. Come molti argomenti di programmazione, il potere degli alberi di ricerca binari deriva dalla loro capacità di risolvere i dati in piccoli componenti correlati. D'ora in poi, puoi lavorare con l'intero set di dati in modo organizzato.
Potenziali problemi di ricerca binaria
Gli alberi di ricerca binari sono fantastici, ma ci sono alcuni avvertimenti da tenere a mente. Di solito sono efficaci solo se equilibrati. Un albero equilibrato è un albero in cuila differenza tra le altezze dei sottoalberi di qualsiasi nodo nell'albero è al massimo uno. Diamo un'occhiata a un esempio che potrebbe aiutare a chiarire le regole. Immaginiamo che l'array inizi come ordinabile.
Se provi a eseguire un algoritmo di albero di ricerca binario su questo albero, funzionerà esattamente come se stesse semplicemente iterando attraverso l'array fino a trovare il valore desiderato. Il potere della ricerca binaria risiede nella capacità di filtrare rapidamente i valori indesiderati. Quando un albero non è equilibrato, non fornirà gli stessi benefici di un albero equilibrato.
È molto importante esaminare i dati con cui l'utente sta lavorando durante la creazione di un albero di ricerca binario. Puoi integrare routine come la randomizzazione degli array prima di implementare un albero di ricerca binario per gli interi per bilanciarlo.
Esempi di calcolo della ricerca binaria
Dobbiamo determinare che tipo di albero risulterà se 25 viene inserito nel seguente albero binario di ricerca:
10
/
/
5 15
/ /
/ /
2 12 20
Quando si inserisce x in un albero T che non contiene ancora x, la chiave x viene sempre inserita in una nuova foglia. In connessione con questo, il nuovo albero sarà simile a:
10
/
/
5 15
/ /
/ /
2 12 20
25
Che tipo di albero otterresti se inserissi 7 nel seguente albero binario di ricerca?
10
/
/
5 15
/ /
/ /
2 12 20
Risposta:
10
/
/
/
5 15
/ / /
/ / /
2 7 12 20
Un albero di ricerca binario può essere utilizzato per memorizzare qualsiasi oggetto. Il vantaggio dell'utilizzo di un albero di ricerca binario invece di un elenco collegato è che se l'albero è ragionevolmente bilanciato e più simile a un albero "completo" che a uno "lineare", l'inserimento, la ricerca e tutte le operazioni di eliminazione possono essere implementate per essere eseguite in O(log N) tempo.
