Che cos'è un'implementazione dell'albero C ++ valida e stabile?

Question

Mi chiedo se qualcuno può consigliare una buona implementazione dell'albero C ++, speriamo che lo sia compatibile se possibile,

Per la cronaca, ho già scritto molte volte algoritmi ad albero e so che può essere divertente, ma voglio essere pragmatico e pigro se possibile. Quindi un vero collegamento a una soluzione funzionante è l'obiettivo qui.

Nota: sto cercando un albero generico, non un albero bilanciato o una mappa / set, in questo caso la struttura stessa e la connettività dell'albero sono importanti, non solo i dati all'interno. Pertanto, ogni ramo deve essere in grado di contenere quantità arbitrarie di dati e ogni ramo dovrebbe essere iterabile separatamente.

Answer 1

Non conosco i tuoi requisiti, ma non saresti migliore con un grafico (implementazioni per esempio in Boost Graph ) se sei interessato principalmente alla struttura e non tanto ai vantaggi specifici dell'albero come la velocità attraverso il bilanciamento? Puoi "emulare" un albero attraverso un grafico e forse sarà (concettualmente) più vicino a ciò che stai cercando.

Answer 2

Dai un'occhiata a questo .

La libreria tree.hh per C ++ fornisce una classe contenitore simile a STL per alberi n-ary, basata su dati memorizzati nei nodi. Sono disponibili vari tipi di iteratori (post-ordine, pre-ordine e altri). Ove possibile, i metodi di accesso sono compatibili con l'STL o sono disponibili algoritmi alternativi.

HTH

Answer 3

Suggerirò di usare std :: map invece di un albero.

Le caratteristiche di complessità di un albero sono:

Inserisci: &; &; &; &; &; &; & Nbsp nbsp nbsp nbsp nbsp nbsp nbsp; O (ln (n))
Rimozione: &; & Nbsp nbsp; O (ln (n))
Trovare: &; &; &; &; &; &; &; &; & Nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp; O (ln (n))

Queste sono le stesse caratteristiche che std :: map garantisce.
Di conseguenza, la maggior parte delle implementazioni di std :: map usano un albero (albero rosso-nero) sotto le copertine (anche se tecnicamente non è necessario).

Answer 4

Ok gente, ho trovato un'altra libreria di alberi; stlplus.ntree . Ma non l'ho ancora provato.

Answer 5

Se non hai coppie (chiave, valore), ma semplicemente chiavi, usa std :: set. Che usa lo stesso albero rosso-nero di std :: map.

Answer 6

Supponiamo che la domanda riguardi alberi binari bilanciati (in qualche forma, per lo più albero nero rosso), anche se non è così.

Gli alberi binari bilanciati, come il vettore, consentono di gestire alcuni ordini di elementi senza bisogno di chiave (come inserendo elementi ovunque nel vettore), ma:

• Con O (log (n)) ottimale o migliore complessità per tutte le modifiche di un elemento (aggiungi / rimuovi all'inizio, fine e prima dell'amplificatore &; dopo ogni iteratore)
• Con persistenza di iteratori attraverso eventuali modifiche tranne la distruzione diretta dell'elemento puntato dall'iteratore.

Opzionalmente si può supportare l'accesso per indice come nel vettore (con un costo di una dimensione_t per elemento), con complessità O (log (n)). Se utilizzati, gli iteratori saranno casuali.

Facoltativamente, l'ordine può essere applicato da alcune funzioni di confronto, ma la persistenza degli iteratori consente di utilizzare uno schema di confronto non ripetibile (es: cambio arbitrario di corsie automobilistiche durante l'ingorgo).

In pratica, l'albero binario bilanciato ha un'interfaccia di vettore, elenco, doppio elenco collegato, mappa, multimappa, deque, coda, priorità_queue ... con raggiungimento della complessità teorica ottimale O (log (n)) per tutte le operazioni a singolo elemento.

&

lt; & Sarcastico gt; questo è probabilmente il motivo per cui c ++ stl non lo propone < / sarcastic >

Gli individui non possono implementare da soli l'albero dell'equilibrio generale, a causa delle difficoltà di ottenere una corretta gestione del bilanciamento, specialmente durante l'estrazione degli elementi.

Non esiste un'implementazione ampiamente disponibile di albero binario bilanciato perché l'albero nero rosso all'avanguardia (in questo momento il miglior tipo di albero bilanciato a causa del numero fisso di costose riorganizzazioni degli alberi durante la rimozione) conosce l'implementazione, copiata con eleganza da ogni implementatori # 8217 &; dal codice iniziale dell'inventore della struttura, non consente la persistenza dell'iteratore. Probabilmente è la ragione dell'assenza di un modello di albero completamente funzionale.