Ok, so I got this for homework and been struggling for a while now. The full assignment requires this:
While N = number of elements in given array and n = number of different elements,
init(S,A[1...N]) - accept an array A as input and initialize S data structure in O(Nlogn) time
insert(S,x) - insert the key x to S in $O(\log n)$ time
freq(S,x) - return the number of appearances of x in S, in O(logn) time
mostFreq(S) - return the most frequent element in S, in O(1) time
I was thinking of using a balanced bst, inserting elements from the array one by one, but it would be $O(n \log n)$ and not O(Nlogn) as required.
As for the frequency functions, I was thinking of storing each element with an int attached to it or something, indicating number of appearances so far, thus enabling me to just search for some element to know the number of times he appears in S, but that's messy too.
as for the last function (mostFreq) - I have no idea how to deal with it whatsoever. I guess it involves holding some variable that will be updated on each insert, but I got nothing.
So it's clear I'm pretty lost :) any suggestions?