Va bene non comprendere appieno gli alberi RB? [chiuso]

15

Quindi ho appena imparato alberi neri e rossi a Cormen e wow! Tipicamente mi piace capire tutti gli algoritmi e le strutture dati al punto da poterli ricostruire da zero senza dover barare guardando lo pseudo codice. Mi piacciono molto gli algoritmi quindi mi diverto a imparare come funzionano e di solito passo linea per riga e provo alcuni casi osservando il codice e controllando se ciò che sta accadendo è quello che ho capito dovrebbe accadere.

Solo capire cosa sta succedendo mi ha portato MOLTO tempo per gli alberi RB. Anche con le spiegazioni del libro, trovavo ancora difficile comprendere il codice. Per non parlare del fatto che non potevo capire come / perché le rotazioni funzionano. Non lo trovo affatto intuitivo. Voglio dire, i tre (sei in realtà) diversi casi per l'inserimento e poi i 4 casi per la cancellazione? È possibile capire questa cosa? È impossibile per me ricostruire questo codice senza barare. Fino a quando l'albero binario non potrei implementare la roba fuori dalla mia testa, con qualche ritocco funzionerebbe sempre, ma gli alberi RB non ho intenzione di provare. Voglio dire, anche l'insegnante si è confusa qualche volta, quindi suppongo che non sia così facile, ma allo stesso tempo, non dovremmo capire tutto quello che sta succedendo o almeno perché? Il libro non ha davvero spiegato come qualcuno abbia avuto l'idea delle rotazioni. Come ha fatto qualcuno a notare che con 2 rotazioni è possibile risolvere qualsiasi problema di inserimento? È fantastico!

La mia domanda è: devo davvero capire al 100% gli alberi RB? Mi sento un po 'brutto saltare le cose senza comprenderlo appieno. Grazie in anticipo ragazzi! (PS: non ci sono tag per RB-tree, in realtà nemmeno per albero, solo binary-tree, quindi metto solo algoritmi)

    
posta Bernardo Pires 29.05.2011 - 22:48
fonte

6 risposte

13

Sembri equiparare l'idea di "comprensione" con "essere in grado di scrivere il codice senza guardare il libro". Queste sono due cose diverse. Se riesci a vedere come ruotano i nodi dell'albero riorganizza l'albero per mantenere l'equilibrio, allora lo capisci. Essere in grado di richiamare immediatamente tutti i casi per cui si applicano le rotazioni non è il punto.

Io stesso, probabilmente potrei capire le rotazioni se avessi penna / carta / diverse ore per giocarci. Ma di certo non potevo semplicemente scriverlo senza pensarci. Se dovessi effettivamente scrivere un tale algoritmo, lo farei per assicurarmi di ottenere tutti i dettagli corretti. Ovviamente, in quasi tutte le situazioni utilizzerei codice già scritto.

Quando tutto questo viene utilizzato è quando ti imbatti in una situazione che non si adatta a nessuno degli algoritmi. Non avrai mai bisogno di scrivere la tua implementazione dell'albero. Ma potresti trovarti, ad esempio, bisognoso di appiattire una serie di elenchi doppiamente collegati. In tal caso, avere compreso l'idea alla base della rotazione può essere molto utile.

    
risposta data 29.05.2011 - 23:51
fonte
4

Se hai familiarità con la programmazione funzionale, potresti trovare questo approccio migliore (Okasaki 1999):

link

In caso contrario, prendi in considerazione almeno la frase di apertura:

Everybody learns about balanced binary search trees in their introductory computer science classes, but even the stouthearted tremble at the thought of actually implementing such a beast.

    
risposta data 30.05.2011 - 00:13
fonte
3

Non è necessario comprendere le rotazioni in dettaglio. dovresti capire la relazione tra gli alberi RB e gli alberi 2-3-4 (vedi Sedgewick). Tutte quelle pazze rotazioni hanno molto più senso quando le immagini come 2-3-4 alberi. Se il tuo professore non ha insegnato agli alberi RB come dettaglio di implementazione per 2-3-4 alberi, dovresti probabilmente leggere qualcosa su 2-3-4 alberi. (Il trattamento di Sedgewick è abbastanza buono, Wikipedia non ce l'ha.)

Più in generale, comprendere i dettagli di implementazione del perché un algoritmo funziona è a volte utile. Capire la logica del perché l'algoritmo funziona è quasi sempre utile. Essere in grado di elaborare autonomamente l'algoritmo di solito non è necessario, anche se più algoritmi capisci le migliori possibilità che avrai.

    
risposta data 30.05.2011 - 08:40
fonte
1

Se hai bisogno di "RB Trees By Heart" per il tuo esame la prossima settimana, dovrai mordere il proiettile e impararli. In tal caso, dovresti riconsiderare i tuoi metodi di apprendimento. Forse provare a spiegare RB Trees a un compagno di classe ti aiuterà più di un'altra notte di solitario scrivere il codice.

Se gli RB Trees sono una base per il tuo prossimo corso dopo le vacanze, saltali ora (senza brutti sentimenti) e concentrati sul corso di questo semestre. Ma tieni gli occhi aperti per gli argomenti che potrebbero prepararti per un secondo tentativo a RB Trees.

Se senti onestamente che non avrai mai veramente bisogno di loro (vedi il commento di Anna Lear), baciami addio senza rimpianti - nessuno sa più che una goccia nel mare della conoscenza (peccato che gli insegnanti pensino spesso alla loro caduta è il più importante).

    
risposta data 29.05.2011 - 23:52
fonte
1

La chiave per programmare il successo è non mollare mai :

Oggi i suoi alberi RB domani saranno qualcos'altro. La lezione più grande è non arrendersi .

Per me, questa è una delle essenze principali della programmazione, non arrendersi ...

Ti suggerisco di continuare a provare e quando non riesci FAI NUOVAMENTE .

"Until you get, until it clicks, until it runs."

Perché una volta superate le montagne, il cielo diventa chiaro. La tua mente cambia nella comprensione, tu sei temporaneamente elevato (fino alla prossima montagna) . Questa elevazione temporale vale più di tutti i soldi del mondo ..

    
risposta data 30.05.2011 - 00:10
fonte
0

Il modo migliore per comprenderlo è provarlo :

  • Ci sono 3 o 6 rotazioni. Prendi un pezzo di carta e scrivili uno per uno.
  • Una volta ottenuto, vai e implementa un albero nero rosso. Va bene se devi cercare un paio di cose.

È così che l'abbiamo fatto al college. E per l'esame dobbiamo spiegare come ha funzionato una parte di esso.

    
risposta data 30.05.2011 - 11:26
fonte

Leggi altre domande sui tag