Hello,
your project seems really intersting. But some more details are necessary, otherwise you'll get a suboptimal solution.
What exactly are the weights? Are they static or do the weights of a queried element change (get more "likely")?
What is the "main" operation of the tree: find elements, insert elements, remove elements?
How likely is it, that the same set of elements is queried (or inserted elements are queried shortly after)? If the probability is high, it is maybe better to ignore the weights completely and use a Splay tree. The most current elements are washed up close to the root, so queries are very fast.
If it is not possible to predict the behaviour of insertions and queries, I would suggest a partially rubuildable and weighted Huffman tree. That means: weights are added and balanced and a partial rubuilding would be lauched, if the weights differ by a threshold of a (user defined) factor alpha.
How flexible should the tree be? I would suggest a templated implementation: the type of elements as the first parameter and an optional comapre operator as second. This would allow the usage of "normal" types and pointers.
I have several years professional experience with C++ and will finish my PhD in computer science this year. I think my offer is fair and your project would by in good hands if you choose my bid.
It would be nice to hear from you. Please write me a message, if you have any questions.
Sincerely yours,
Sebastian