Albero C ++ FP o prefisso

Question

Ho alcune sequenze come queste

(100) - (102) - (103) - (104,106) - (108)
(101) - (103)
(102) - (106)

Esiste un'implementazione efficiente un albero di prefisso o un albero FP o simile in C + +?

Answer 1

Non capisco cosa stai dicendo ... ma se hai bisogno di costruire un albero FP qui è la migliore pagina che ho trovato

Algoritmo dell'albero FP

Answer 2

Non è chiaro esattamente quello che hai perché i dati dati non sembrano essere in nessuna notazione standard.

Se i prefissi sono solo alcune cifre decimali iniziali condivise tra i valori interi, probabilmente non faranno alcuna differenza significativa per l'archiviazione dei dati. Potresti sottrarre 100 Prima di inserire valori nella struttura dei dati, memorizzare i valori come char, e aggiungi 100 indietro dopo il recupero, ma probabilmente non vale la pena.

Probabilmente dovresti archiviare la sequenza di sequenze come a std::deque< std::vector< int > > dove il vector Gli elementi sono ordinati. A meno che non ci sia uno schema che non riesco a vedere o sto interpretando male il problema, prestazioni ottimali nel trovare quali sequenze contengono un determinato numero deve essere O (n) nel numero di sequenze tempi O (lg n) nella lunghezza della sequenza .