Sto imparando Haskell e come esercizio sto facendo alberi binari. Avendo fatto un albero binario regolare, voglio adattarlo per il bilanciamento di sé. Quindi:
Ma in modo cruciale, che consiglieresti?
Presumo che questo appartenga qui perché è aperto al dibattito.
Ti consiglio di iniziare con un albero rosso-nero o con un Albero AVL .
L'albero rosso-nero è più veloce per l'inserimento, ma l'albero AVL ha un leggero margine per le ricerche. L'albero AVL è probabilmente un po 'più facile da implementare, ma non tanto in base alla mia esperienza.
L'albero AVL assicura che l'albero sia bilanciato dopo ogni inserimento o eliminazione (nessun albero secondario ha un fattore di equilibrio maggiore di 1 / -1, mentre l'albero rosso-nero assicura che l'albero sia ragionevolmente bilanciato in qualsiasi momento.
Considererei un'alternativa se stai bene con le strutture di dati randomizzate : Skip Lists .
Da un punto di vista di alto livello, è una struttura ad albero, tranne per il fatto che non è implementata come un albero ma come una lista con più livelli di link.
Otterrai inserimenti O (log N) / ricerche / eliminazioni e non dovrai affrontare tutti quei casi di ribilanciamento complessi.
Non ho mai pensato di implementarli in un linguaggio funzionale, e la pagina di wikipedia non ne mostra nessuno, quindi potrebbe non essere facile (in riferimento a immutabilità)
Which is most efficient?
Vago e difficile da rispondere. Le complessità computazionali sono tutte ben definite. Se questo è ciò che intendi per efficienza, non c'è un vero dibattito. In effetti, tutti i buoni algoritmi vengono forniti con prove e fattori di complessità.
Se intendi "tempo di esecuzione" o "uso della memoria", dovrai confrontare le implementazioni effettive. Quindi entrano in gioco la lingua, il tempo di esecuzione, il sistema operativo e altri fattori, rendendo difficile rispondere alla domanda.
Which is easiest to implement?
Vago e difficile da rispondere. Alcuni algoritmi possono sembrare complessi per te, ma per me banali.
Which is most often used?
Vago e difficile da rispondere. Prima c'è il "da chi?" parte di questo? Haskell solo? Che dire di C o C ++? In secondo luogo, c'è il problema del software proprietario in cui non abbiamo accesso alla fonte per fare un sondaggio.
But crucially, which do you recommend?
I assume this belongs here because it's open to debate.
Una corretta. Dato che i tuoi altri criteri non sono molto utili, questo è tutto ciò che otterrai.
È possibile ottenere l'origine di un gran numero di algoritmi ad albero. Se vuoi imparare qualcosa, potresti semplicemente implementare tutti quelli che riesci a trovare. Piuttosto che chiedere una "raccomandazione", basta raccogliere tutti gli algoritmi che riesci a trovare.
Ecco l'elenco:
Ci sono sei quelli popolari definiti. Inizia con quelli.
Se si desidera una struttura relativamente facile con cui iniziare (sia gli alberi AVL che gli alberi rosso-neri sono laboriosi), un'opzione è un treap - denominato come una combinazione di "albero" e "heap".
Ogni nodo riceve un valore di "priorità", spesso assegnato casualmente mentre il nodo viene creato. I nodi sono posizionati nell'albero in modo tale che l'ordine delle chiavi sia rispettato e in modo tale che sia rispettato l'ordine di tipo "heap" dei valori di priorità. Ordinamento tipo heap significa che entrambi i figli di un genitore hanno priorità inferiori rispetto al genitore.
EDIT cancellato "all'interno dei valori chiave" sopra - la priorità e l'ordine delle chiavi si applicano insieme, quindi la priorità è significativa anche per le chiavi univoche.
È una combinazione interessante. Se le chiavi sono univoche e le priorità sono univoche, esiste una struttura ad albero unica per qualsiasi insieme di nodi. Anche così, gli inserimenti e le eliminazioni sono efficienti. A rigor di termini, l'albero può essere sbilanciato fino al punto in cui è effettivamente un elenco collegato, ma questo è estremamente improbabile (come con gli alberi binari standard), inclusi casi normali come le chiavi inserite nell'ordine (a differenza degli alberi binari standard). / p>
Se sei interessato agli alberi di Splay, c'è una versione più semplice di quelli che credo sia stata descritta per la prima volta in un articolo di Allen e Munroe. Non ha le stesse garanzie sulle prestazioni, ma evita complicazioni nel trattare con il riequilibrio "zig-zig" e "zig-zag".
Fondamentalmente, durante la ricerca (comprese le ricerche di un punto di inserimento o di un nodo da eliminare), il nodo che si trova viene ruotato direttamente verso la radice, verso l'alto (ad esempio quando una funzione di ricerca ricorsiva viene chiusa). Ad ogni passo, selezioni una singola rotazione sinistra o destra a seconda che il bambino che vuoi sollevare un altro passo verso la radice fosse il figlio destro o il bambino sinistro (se ricordo le direzioni di rotazione corrette, rispettivamente).
Come gli alberi di Splay, l'idea è che gli oggetti a cui si accede di recente si trovino sempre vicino alla radice dell'albero, così veloci da accedere nuovamente. Essendo più semplici, questi alberi di rotazione-radice di Allen-Munroe (quelli che io chiamo loro - non conoscono il nome ufficiale) possono essere più veloci, ma non hanno la stessa garanzia di prestazioni ammortizzate.
Una cosa - dato che questa struttura dati per definizione si modifica anche per le operazioni di ricerca, probabilmente dovrebbe essere implementata monadicamente. IOW potrebbe non essere adatto per la programmazione funzionale.
Un albero bilanciato molto semplice è un albero AA . È invariante è più semplice e quindi più facile da implementare. Per la sua semplicità, le sue prestazioni sono comunque buone.
Come esercizio avanzato, puoi provare a utilizzare GADT per implementare una delle varianti di alberi bilanciati la cui invarianza è applicato dal tipo tipo di sistema.
Leggi altre domande sui tag functional-programming data-structures haskell binary-tree