Write AvlRanking: an AVL tree whose nodes store their height and the size of their subtree, used as a game leaderboard of distinct scores. Commands until the end of input:
add S— insert score S (ignore duplicates);top K— print the K-th best score (no such rankif K is out of range);better S— print how many scores are strictly greater than S.
Finish with the number of scores, the tree height and the median score (the ⌈n/2⌉-th smallest). top and better must run in O(log n) using the sizes.
For the input
add 520 add 480 add 610 add 550 add 430 top 1 top 3 better 500 top 9
the program prints
top 1: 610
top 3: 520
scores above 500: 3
top 9: no such rank
Scores: 5, tree height: 2
Median score: 520