CODEWITHSUNDEEP
javaalgorithmtreebinary-treecomputer-science
mamajava
mamajava

Reputation: 75

Should I use a splay tree?

So, for an assignment we're asked to find write a pseudocode that for a given sequence, find the largest frequency of a number from the sequence. So, a quick example would be:

[ 1, 8, 5, 6, 6, 7, 6, 7, 6, 1, 1, 5, 8 ] => The number with the largest frequency is 6. The "winner" is 6.

We have to implement it in O(nlogm) time where m is the number of distinct numbers. So, in the example above, there are 5 different numbers (m=5).

My approach was to go through each number in the sequence and add it to a binary tree (if not already there) and increment the frequency. Thus, for every number number in the sequence, my program goes to the binary tree, finds the element (in logm time) and increments the frequency by one. It does logm in n amount of times, so the program runs in O(nlogm). However, to find out which number had the largest frequency would take another O(m). I'm left with O(nlogm + m), by dropped the lower-order terms this leaves me with O(m) which is not what the professor is asking for.

I remember from class that a splay tree would be a good option to use in order to keep the most frequently access item at the root, thus giving me O(1) or maybe O(logn) at most to get me the "winner"? I don't know where to begin to implement a splay tree.

If you could provide any insight, I would highly appreciate it.

public E theWinner(E[] C) {
    int i = 0;
    while (i < C.length) {
        findCandidate(C[i], this.root);
    }
    // This is where I'm stuck, returning the winner in < O(n) time.

}

public void findNumber(E number, Node<E> root) {
    if (root.left == null && root.right == null) {
        this.add(number); 
        //splay tree?
    } else if (root.data.compareTo(number) == 0) {
        root.freqCount = root.freqCount + 1;
        //splay tree?
    } else {
        if ( root.data.compareTo(number) < 0) {
            findNumber(number, root.right);
        } else {
            findNumber(number, root.left);
        }
    }
}

Upvotes: 1

Views: 58

Answers (1)

kraskevich
kraskevich

Reputation: 18566

You don't need a splay tree. O(n log m + m) is O(n log m) as the number of distinct elements m is not greater than the total number of elements n. So you can iterate over all the elements in the tree after processing the input sequence to find the maximum.

Upvotes: 2

Related Questions