[Powered by Google Translate] Come rappresentare tutti i membri della famiglia in un computer?
Si potrebbe semplicemente usare una lista,
ma c'è una chiara gerarchia qui.
>> Diciamo che stiamo cominciando con la bisnonna, Alice.
Ha 2 figli, Bob
e tuo nonno, Charlie.
Charlie ha 3 figli,
tuo zio, Dave, tua zia, Eva, e tuo padre, Fred.
Tu sei unico figlio di Fred.
>> Perché organizzare i vostri familiari in questo modo
essere migliore di rappresentazione semplice elenco?
Una ragione è che questa struttura gerarchica,
chiamato 'albero,' contiene più informazioni rispetto a un semplice elenco.
Sappiamo che i rapporti familiari tra tutti
solo esaminando l'albero.
Inoltre, può accelerare
look-up tempo tremendamente, se i dati vengono ordinati albero.
>> Non si può trarre vantaggio da questa qui, ma staremo a vedere un esempio di questo al più presto.
Ogni persona è rappresentata da un nodo sull'albero.
I nodi possono avere nodi figlio
così come un nodo padre.
Questi sono i termini tecnici,
anche quando si utilizzano alberi a cose oltre le famiglie.
Nodo di Alice ha 2 figli e non dei genitori,
mentre il nodo di Charlie ha 3 figli e 1 genitore.
>> Un nodo foglia è uno che non ha figli
sul bordo esterno della struttura.
Il nodo più alto della struttura, il nodo radice,
non ha padre.
>> Un albero binario è un particolare tipo di albero,
in cui ogni nodo ha al massimo 2 bambini.
Ecco l'struct di un nodo di un albero binario in C.
Ogni nodo ha alcuni dati associati
e 2 puntatori ad altri nodi.
>> Nel nostro albero genealogico,
i dati associati era il nome di ogni persona.
Qui è un int, anche se potrebbe essere qualsiasi cosa.
Come si è visto,
un albero binario non sarebbe una buona rappresentazione per una famiglia,
poiché le persone hanno spesso più di 2 bambini.
>> Un albero binario di ricerca
è uno speciale tipo di albero binario ordinato
che ci permette di guardare rapidamente i valori.
Avrete notato
che ogni nodo sotto la radice di un albero
è la radice di un altro albero, chiamato 'sottoalbero.'
Qui, la radice dell'albero è 6,
e il suo bambino, 2, è la radice di un sottoalbero.
>> In un albero binario di ricerca
tutti i valori di un nodo è sottoalbero destro
è maggiore del valore del nodo. Qui: 6.
Beh, i valori in sottoalbero sinistro di un nodo
sono inferiori al valore del nodo.
Se abbiamo bisogno di gestire i valori duplicati,
possiamo cambiare uno di questi per una disuguaglianza sciolto,
il che significa valori identici può cadere sia a sinistra oa destra,
fintanto che siamo coerenti su di esso tutta.
Questo albero è un albero binario di ricerca
perché segue queste regole.
>> Ecco come sarebbero se ci siamo rivolti tutti i nodi in strutture C.
Si noti che se un bambino non è presente,
il puntatore è nullo.
Come si fa a verificare se 7 è nella struttura?
Partiamo alla radice.
Seven è superiore a 6, quindi se è nella struttura, deve essere a destra.
Poi, è inferiore a 8, quindi deve essere lasciato.
Qui, abbiamo trovato 7.
Ora, controlleremo per 5.
Five è minore di 6, quindi deve essere a sinistra.
Cinque è maggiore di 2,
quindi deve essere giusto,
ed è anche superiore a 4, quindi deve essere di nuovo a destra.
Tuttavia, non c'è bambino qui.
Il puntatore è nullo.
Questo significa che 5 non è in nostro albero.
>> Siamo in grado di cercare l'albero binario con il seguente codice:
Ad ogni nodo, controlliamo per vedere se abbiamo trovato
il valore che stiamo cercando.
Se non lo trovi, si determina se deve essere
sulla sinistra o destra e verificare che sottoalbero.
Questo ciclo continuerà l'albero
finché non vi è il nodo figlio sinistro o destro.
>> Ricordate che 5 non era nella struttura.
Come lo inseriamo?
Il processo è simile alla ricerca.
Abbiamo scorrere verso il basso l'albero a partire da 6,
sinistra a 2,
diritto a 4,
e di nuovo a destra, ma 4 non ha figli da questa parte.
Questa sarà la nuova posizione per 5,
e si inizia senza figli.
>> Qual è la velocità di operazioni su un albero binario di ricerca?
Ricordare che Bigohnotation cerca di fornire un limite superiore.
Nel caso peggiore,
il nostro albero potrebbe essere semplicemente una lista concatenata
il che significa che l'inserimento, cancellazione e ricerca
potrebbe richiedere tempo proporzionale al numero di nodi dell'albero.
Questo è O (n).
>> Ad esempio, la seguente è una valida albero binario di ricerca.
Tuttavia, se cerchiamo di trovare 9,
dobbiamo attraversare ogni nodo.
E non è migliore di una lista concatenata.
Idealmente, vorremmo tutti i nodi
del nostro albero binario di ricerca di avere 2 bambini.
In questo modo, inserimento, cancellazione e ricerca
avrebbe preso, nella peggiore delle ipotesi, O (log n).
L'albero di prima potrebbe essere più equilibrata,
come questo.
Ora, guardando a qualsiasi valore ha, al massimo, 3 gradini.
Questo albero è bilanciato,
significato che è ha una profondità minima
rispetto al numero di nodi.
>> Alla ricerca di un valore in un albero binario di ricerca bilanciato
è simile alla ricerca binaria su un array ordinato.
Infatti, se non abbiamo bisogno di inserire o eliminare elementi,
si comportano allo stesso modo.
Tuttavia, una struttura ad albero è meglio
per gli inserimenti di movimentazione ed eliminazioni
>> Il mio nome è Bannus Van der Kloot.
Questo è CS50.