スプレーツリーを使用する必要がありますか？

Question

したがって、割り当てのために、与えられたシーケンスに対してシーケンスから最大の周波数を見つける疑似コードを書くことを求められます。したがって、簡単な例は次のようになります。

[1,8,5,6,6,7,6,7,6,1,1,8,8] =>最大頻度の数値は6です。 "勝者"は6です。

私はそれをO（nlogm）時間に実装する必要があります。ここで、mは別個の番号の数です。したがって、上記の例では、5つの異なる数字があります（m = 5）。

私のアプローチは、シーケンス内の各数字を調べ、それがバイナリツリーに追加されていない場合は、周波数を増やすことでした。したがって、シーケンス内のすべての数値に対して、私のプログラムはバイナリツリーに行き、要素を見つけ（logm時間で）、周波数を1つ増分します。それはn回のログオンを行うので、プログラムはO（nlogm）で実行されます。しかし、どの周波数が最大の周波数を有するかを知るためには、別のO（m）が必要である。私はO（nlogm + m）を残していますが、これは教授が求めているものではないO（m）で私を残します。

私は、最も頻繁にアクセスするアイテムをルートに保つために、スプレイツリーを使うのが良いオプションになることを覚えています。したがって、私にO（1）またはO（logn）勝者"？私はスプレイツリーの実装をどこから始めるべきかわかりません。

洞察力を提供できる場合は、非常に感謝します。

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); 
     } 
    } 
} 

Answer 1

スプレイツリーは必要ありません。 O(n log m + m)はO(n log m)であり、別個の要素の数はであり、要素の総数はnである。したがって、入力シーケンスを処理して最大値を見つけると、ツリー内のすべての要素を繰り返し処理できます。