[Powered by Google Translate] [Ricerca binaria] [Patrick Schmid - Harvard University] [Questo è CS50. - CS50.TV] 

Se ti ho dato una lista dei nomi dei personaggi Disney in ordine alfabetico e ti ha chiesto di trovare Mickey Mouse, come è possibile fare per fare questo? Un modo ovvio sarebbe quello di scorrere la lista dall'inizio e controllare ogni nome per vedere se è Mickey. Ma come si legge Aladdin, Alice, Ariel, e così via, si prende subito conto che a partire dalla parte anteriore della lista non era una buona idea. Ok, forse si dovrebbe iniziare a lavorare a ritroso dalla fine della lista. Ora si legge Tarzan, Stitch, Biancaneve, e così via. Eppure, questo non mi sembra il modo migliore per andare su di esso. 

Beh, un altro modo che si potrebbe fare per fare questo è quello di cercare di limitare l'elenco dei nomi che si deve guardare. Dal momento che si sa che sono in ordine alfabetico, si può solo guardare i nomi al centro della lista e verificare se Mickey Mouse è prima o dopo questo nome. Guardando il cognome nella seconda colonna ti renderesti conto che M per Mickey viene dopo J per Jasmine, in modo da dovreste semplicemente ignorare la prima metà della lista. Poi si sarebbe probabilmente guardare la parte superiore della colonna e vedere che inizia con Rapunzel. Mickey viene prima di Raperonzolo, sembra che siamo in grado di ignorare l'ultima colonna pure. Proseguendo la strategia di ricerca, si prende subito vedere che Mickey è nella prima metà della lista dei nomi rimanente e, infine, trovare Mickey nascosto tra Merlino e Minnie. 

Quello che hai appena fatto è stato fondamentalmente di ricerca binaria. Come il nome suggerisce, svolge la sua strategia di ricerca in pochi binario. Che cosa significa? Beh, data una lista di elementi ordinati, l'algoritmo di ricerca binaria prende una decisione binaria - sinistro o destro, superiore o inferiore, in ordine alfabetico prima o dopo - in ogni punto. Ora che abbiamo un nome che va di pari passo con questo algoritmo di ricerca, Vediamo un altro esempio, ma questa volta con un elenco di numeri ordinati. Dire che stiamo cercando il numero 144 in questo elenco di numeri ordinati. Proprio come prima, troviamo il numero che sta in mezzo - che in questo caso è di 13 - 144 e vedere se è superiore o inferiore a 13. Dal momento che è chiaramente superiore a 13, si può ignorare tutto ciò che è 13 o meno e concentratevi solo sulla metà rimanente. Dal momento che ora abbiamo un numero pari di elementi a sinistra, semplicemente scegliere un numero che si trova vicino al centro. In questo caso abbiamo scelto 55. Avremmo potuto altrettanto facilmente scelto 89. Va bene. Anche in questo caso, 144 è maggiore di 55, così andiamo a destra. Fortunatamente per noi, il numero medio successivo è 144, quello che stiamo cercando. Quindi, al fine di trovare 144 con una ricerca binaria, siamo in grado di trovare in soli 3 passi. Se avessimo utilizzato la ricerca lineare qui, ci avrebbe preso 12 passi. È un dato di fatto, dal momento che questo metodo di ricerca dimezza il numero di articoli deve guardare ad ogni passo, si troverà la voce si è alla ricerca di in circa il logaritmo del numero di elementi nella lista. Ora che abbiamo visto due esempi, diamo uno sguardo al un po 'di pseudocodice per una funzione ricorsiva che implementa la ricerca binaria. Partendo dall'alto, vediamo che dobbiamo trovare una funzione che accetta 4 argomenti: chiave, array, min e max. La chiave è il numero che stiamo cercando, per cui 144 nel precedente esempio. Array è l'elenco dei numeri che stiamo cercando. Min e max sono gli indici delle posizioni di minima e massima che stiamo guardando. Così, quando si avvia, sarà zero min e max sarà massimo indice della matrice. Come limitare la ricerca verso il basso, provvederemo ad aggiornare min e max essere proprio il campo che stiamo ancora cercando trovi 

Saltiamo alla parte prima e interessante. La prima cosa da fare è trovare il punto medio, l'indice che è a metà strada tra il minimo e il massimo della matrice che stiamo ancora valutando. Poi consideriamo il valore della matrice in quella posizione punto centrale e vedere se il numero che stiamo cercando è inferiore a quella chiave. Se il numero in quella posizione è meno, allora significa che la chiave è più grande di tutti i numeri alla sinistra di tale posizione. Così possiamo chiamare la funzione di ricerca binaria di nuovo, ma questa volta l'aggiornamento del minimo e massimo dei parametri di leggere solo la metà che è maggiore o uguale al valore abbiamo appena visto. D'altra parte, se la chiave è inferiore al numero nel punto centrale corrente dell'array, vogliamo andare a sinistra e ignorare tutti i numeri che sono maggiori. Anche in questo caso, si chiama ricerca binaria, ma questa volta con la gamma di min e max aggiornato per includere solo la parte inferiore. Se il valore nel punto centrale corrente nella matrice non è né maggiore né minore della chiave, allora deve essere uguale alla chiave. Quindi, possiamo semplicemente restituire l'indice corrente punto medio, e abbiamo finito. Infine, questo controllo è qui per il caso che il numero in realtà non è nella matrice di numeri che stiamo cercando. Se l'indice massimo della gamma che stiamo cercando è sempre inferiore al minimo, ciò significa che siamo andati troppo lontano. Dal momento che il numero non era nella matrice di input, ci restituisce -1 per indicare che non è stato trovato. 

Avrete notato che, per questo algoritmo al lavoro, l'elenco dei numeri deve essere ordinato. In altre parole, si possono trovare solo 144 utilizzando la ricerca binaria se tutti i numeri sono ordinati dal più basso al più alto. Se questo non fosse il caso, non sarebbe in grado di escludere la metà dei numeri ad ogni passo. Quindi abbiamo 2 opzioni. O si può prendere un elenco non ordinato e ordinare prima di usare la ricerca binaria, o possiamo fare in modo che l'elenco dei numeri è ordinata come aggiungere numeri ad esso. Così, invece di ordinamento proprio quando dobbiamo cercare, perché non mantenere la lista ordinata in ogni momento? 

Un modo per mantenere un elenco di numeri ordinati consentendo allo stesso tempo uno per aggiungere o spostare i numeri dall'elenco è quello di utilizzare qualcosa che si chiama un albero binario di ricerca. Un albero binario di ricerca è una struttura dati che ha 3 proprietà. In primo luogo, il sottoalbero sinistro di un nodo contiene solo i valori che sono meno o uguale al valore del nodo. Secondo, il sottoalbero destro di un nodo contiene solo valori che sono maggiori di o uguale al valore del nodo. E, infine, entrambi i sottoalberi sinistro e destro di tutti i nodi sono anche alberi binari di ricerca. Vediamo un esempio con gli stessi numeri che abbiamo usato in precedenza. Per quelli di voi che non hanno mai visto un albero di informatica prima, vorrei iniziare dicendo che un albero informatica cresce verso il basso. Sì, a differenza di alberi a cui siete abituati, la radice di una struttura informatica è in alto, e le foglie sono in fondo. Ogni piccola scatola è detto nodo ei nodi sono collegati tra loro da bordi. Quindi, la radice di questo albero è un valore nodo con il valore 13, che ha 2 nodi bambini con i valori 5 e 34. Un sottoalbero è l'albero che si forma solo guardando una sottosezione dell'intero albero. 

Per esempio, il sottoalbero sinistro del nodo 3 è l'albero creato dai nodi 0, 1 e 2. Quindi, se torniamo alle proprietà di un albero binario di ricerca, si vede che ogni nodo dell'albero è conforme a tutti i 3 oggetti, vale a dire, il sottoalbero sinistro contiene solo i valori che sono inferiori o pari al valore del nodo; il sottoalbero destro di tutti i nodi contiene solo valori maggiori o uguali al valore del nodo, e sottoalberi sinistro e destro di tutti i nodi sono anche alberi binari di ricerca. Anche se questo albero un aspetto diverso, si tratta di un valido albero binario di ricerca per la stessa serie di numeri. È un dato di fatto, ci sono molti modi possibili che si possono creare una valida ricerca albero binario da questi numeri. Bene, torniamo al primo che abbiamo creato. Che cosa possiamo fare con questi alberi? Beh, possiamo in modo molto semplice trovare i valori minimo e massimo. I valori minimi possono trovare sempre andando a sinistra fino a quando non esistono altri nodi da visitare. Al contrario, per trovare il massimo semplicemente scende a destra ogni volta. 

Trovare qualsiasi altro numero che non è il minimo o il massimo è altrettanto facile. Dire che stiamo cercando il numero 89. Abbiamo semplicemente controllare il valore di ogni nodo e di andare a sinistra oa destra, a seconda che il valore del nodo è inferiore o superiore quello che stiamo cercando. Quindi, partendo dalla radice del 13, vediamo che 89 è maggiore, e così andiamo a destra. Poi vediamo il nodo per il 34, e di nuovo si va a destra. 89 è ancora superiore a 55, quindi continuiamo a andare a destra. Abbiamo quindi messo a punto un nodo con il valore di 144 e andate a sinistra. Ed ecco, 89 è proprio lì. 

Un'altra cosa che possiamo fare è stampare tutti i numeri eseguendo un attraversamento in ordine simmetrico. Un attraversamento in ordine simmetrico significa stampare tutto nel sottoalbero sinistro seguita da una stampa del nodo stesso e poi seguita da una stampa tutto ciò che nel sottoalbero destro. Per esempio, prendiamo il nostro preferito albero binario di ricerca e stampare i numeri in modo ordinato. Partiamo alla radice del 13, ma prima di stampare 13 si ha di stampare tutto nel sottoalbero sinistro. Quindi andiamo a 5. Dobbiamo ancora andare più in profondità nella struttura ad albero fino a trovare la più a sinistra del nodo, che è zero. Dopo la stampa zero, torniamo alla 1 e la stampa che fuori. Poi andiamo al sottoalbero destro, che è 2, e la stampa che fuori. Ora che abbiamo finito con questo sottoalbero, siamo in grado di risalire al 3 e stamparlo. Continuando il backup, stampiamo il 5 e poi il 8. Ora che abbiamo completato l'intero sottoalbero sinistro, siamo in grado di stampare il 13 e iniziare a lavorare sul sottoalbero destro. Saltiamo giù a 34, ma prima di stampare 34 dobbiamo stampare il suo sottoalbero sinistro. Così abbiamo stampare 21; poi si arriva a stampare 34 e visitare il suo sottoalbero destro. Dal momento che 55 non ha sottoalbero sinistro, lo stampare e proseguire per il suo sottoalbero destro. 144 ha un sottoalbero di sinistra, e quindi abbiamo stampare il 89, seguita dalla 144, e infine il più a destra del nodo 233. Il gioco è fatto, tutti i numeri vengono stampati in ordine dal più basso al più alto. 

L'aggiunta di qualcosa per l'albero è relativamente indolore pure. Tutto ciò che dobbiamo fare è fare in modo che seguiamo tre binari proprietà albero di ricerca e quindi inserire il valore in cui ci sia spazio. Diciamo che vogliamo inserire il valore di 7. Dal 7 è inferiore a 13, si va a sinistra. Ma è maggiore di 5, quindi abbiamo attraversate a destra. Dal momento che è meno di 8 e 8 è un nodo foglia, si aggiungono 7 al bambino di sinistra 8. Voila! Abbiamo aggiunto un numero al nostro albero binario di ricerca. 

Se siamo in grado di aggiungere le cose, è meglio essere in grado di cancellare le cose pure. Purtroppo per noi, l'eliminazione è un po 'più complicata - non molto, ma solo un po '. Ci sono 3 diversi scenari che dobbiamo prendere in considerazione quando si eliminano elementi da alberi binari di ricerca. Primo, il caso più semplice è che l'elemento è un nodo foglia. In questo caso, abbiamo semplicemente cancellare e andare avanti con la nostra attività. Supponiamo di voler cancellare il 7 che abbiamo appena aggiunto. Beh, abbiamo semplicemente trovato, rimuoverlo, e questo è tutto. Il caso successivo è se il nodo ha solo 1 bambino. Qui siamo in grado di eliminare il nodo, ma dobbiamo prima fare in modo per collegare la sottostruttura che viene ora lasciato senza genitori per il genitore del nodo che abbiamo appena cancellato. Supponiamo di voler cancellare 3 dal nostro albero. Prendiamo l'elemento figlio di quel nodo e collegarlo al padre del nodo. In questo caso, stiamo ora collegando il 1 alla 5. Questo funziona senza un problema, perché si sa, in base alla proprietà albero binario di ricerca, che tutto il sottoalbero sinistro di 3 era inferiore a 5. Ora che il 3 di sottostruttura è curato, siamo in grado di eliminarlo. Il terzo caso, infine, è il più complesso. Questo è il caso quando il nodo si desidera eliminare ha 2 bambini. Per fare questo, dobbiamo prima trovare il nodo che ha il valore più prossimo, scambiare i due, e quindi eliminare il nodo in questione. Si noti il ​​nodo che ha il valore più grande non può avere 2 figli stessa poiché il suo figlio sinistro sarebbe un candidato migliore a quello immediatamente superiore. Di conseguenza, l'eliminazione di un nodo con 2 bambini ammonta a scambio di 2 nodi, e quindi l'eliminazione è gestita da 1 delle 2 regole di cui sopra. Ad esempio, supponiamo di voler eliminare il nodo radice, 13. La prima cosa che facciamo è trovare il valore più grande nella struttura ad albero che, in questo caso, è di 21. Abbiamo poi scambiare i 2 nodi, facendo una foglia 13 e 21 il nodo del gruppo centrale. Ora possiamo semplicemente eliminare 13. 

Come accennato in precedenza, ci sono molti modi possibili per fare un valido albero binario di ricerca. Purtroppo per noi, alcuni sono peggio di altri. Ad esempio, cosa succede quando si costruisce un albero binario di ricerca da una lista ordinata di numeri? Tutti i numeri sono appena aggiunto a destra ad ogni passo. Quando vogliamo cercare un numero, non abbiamo altra scelta, ma solo per guardare a destra ad ogni passo. Questo non è migliore di ricerca lineare affatto. Anche se non li coprire qui, ci sono altri, più complessi, strutture di dati che fanno in modo che questo non accada. Tuttavia, una cosa semplice che si può fare per evitare questo è a poco a caso mischiare i valori di input. E 'altamente improbabile che per caso a caso un elenco di numeri mischiato è ordinato. Se questo fosse il caso, i casinò non sarebbe rimasto in attività a lungo. 

Il gioco è fatto. Ora si sa sulla ricerca binaria e alberi binari di ricerca. Sono Patrick Schmid, e questo è CS50. [CS50.TV] Un modo ovvio sarebbe quello di scorrere la lista di ... [bip] ... Il numero di elementi ... yep [Ride] Nodo di inviare ... 234 ... augh. >> Yay! Questo è stato -