algorithm - Data structure to support optimal operations for a scoreboard -

there scoreboard required maintained , supported following 2 operations:

void insert(string playername, int score); list<string> getplayersbyrank(int rank);  

the insert function may insert playername along score or update score of player in case player present in scoreboard.

provide data structure support above 2 operations making them optimal possible. both functions called frequently.

homework?

a balanced binary tree springs mind, gives o(log(n)) insertion , (o(n)) in-order traversal.

check out avl trees, example: http://en.wikipedia.org/wiki/avl_tree

edit:

thanks tmyklebu's commit, realized overlooked fact getplayersbyrank takes parameter, it's lookup rank instead of complete traversal.

the approach still works, should use variant each node knows how many descendants has in each branch. way, can descend directly desired rank.

example:

(<p1s1l1r1> = player 1 score 1 left 1 right 1)               <p1s6l3r2>             /            \       <p2s8l1r1>        <p5s3l0r1>       /        \           \ <p3s10l0r0>    <p4s8l0r0>    <p6s1l0r0> 

now tree if want players ranked 2nd, @ root , see there 3 left nodes, player @ root node (p1) ranked 4th. descend left p2 , see there 1 left node, p2 ranked 2nd. however, players ranked 2nd still need descend right , find p4 also, has same score (assuming same-scored players inserted @ right).

so current rank of every node is:

 (rank of parent node) + (number of left children)      + (0 if (score same score of parent node) or        1 otherwise)) 

when inserting or deleting node, update balancing , weight information (how many left , right children there are). when updating score, delete node , reinsert new score.