[c++]alberi binari

[giuseppe500]

ciao,
Ho il seguente problema :
Ho una serie di ID numerici che mi arrivano in modo dinamico e io devo registrarli creando una numerazione , se il numero è gia presente gli devo dare un valore che sia il max dei numeri letti e cosi via(questo è solo un esempio per una numerazione).
Il problema è che per fare questo devo, prima di inserire un numero che c'è gia scorrere tutti i numeri presenti.
E questo è piuttosto inefficente.
E' possibile risolvere con gli alberi binari in modo piu veloce?
Quel po di teoria che conosco è che a destra si posizionano i nodi maggiori e a sinistra i nodi minori (e quelli uguali? è qui il punto)e questo crea una specie di "strada guidata" per posizionare o togliere.
ho letto che è piu veloce posizionare un numero in un albero binario o estrarlo .
ma non ho mai usato un albero binario quindi chiedo a voi.
tipo questa discussione che ho trovato dopo il post:
http://data-structures-demystified.o...l/lib0051.html
ciao.

[Celebron]

di solito nei bst non sono presenti nodi uguali. Questo perché sarebbero a tutti gli effetti due dati uguali e quindi poi potresti incorrere in problemi logici quando vuoi cancellarne solo uno di essi.

Ad ogni modo, se ti è necessario inserire valori uguali, allora puoi decidere liberamente se porli a destra o a sinistra del padre (io ricordo che per convenzione li si fa andare a sinistra)

Il valore MAX presente in un bst sarà sempre il figlio più a destra di tutti. Se la radice non ha figli destri, allora il MAX è la radice. Quindi è evidente che se vuoi ottenere il valore max ti basta farti restituire il vale del nodo il cui nodo->puntatoredestra sia == NULL (ovviamente controllando prima che l'albero non sia vuoto)

La cancellazione da un albero binario in realtà non è propriamente banale, perciò ti consiglio di leggere approfonditamente la documentazione che troverai con una ricerca su google.

[giuseppe500]

su google ho trovato molta roba confusa(ma forse sono io che non capisco) , ho visto pero' che il set è implementato come binary tree nell stl, pero' non ha funzioni max intrinseche , solo utilizzando std::max_element possosapere l'elemento max da assegnare al nuovo id.
Il problema è che devo usare anche una mappa , in cui ho l'id da assegnare e un valore di trascodifica che mi serve.

Ho provato ad utilizzare il std::max_element su una mappa ma non funziona come vorrei ( tirare fuori il max id tra gli elementi che gli passo) mi estra il primo e l'ultimo valore , se ho elementi intermedi non li considera , come invece giustamente fa il set .

secondo te :
1)creare una classe binary tree con una chiave e un valore e la fuzioone max è complicarsi la vita?o è semplice
2)come funzionerebbe un binary tree con il valore di trascodifica che mi serve?
3)esistono semplici librerie o implementazioni che hai usato ?

grazie.