ディクショナリインターフェイスのバイナリ検索ツリーの実装方法は？

Question

私は次のように辞書のインタフェースを与えている：私はかなり混乱しているので、

public interface Dictionary<E extends Comparable<E>> extends Iterable<E> { 

は今、私は、しかし、私が開始する方法がわからない、二分探索木を使用して、このインタフェースを実装するように求めています上記のDictionaryインタフェースを実装する理論的な概念

これは私の実装クラスである：だから

// Red-black binary search tree 
public class DictionaryImp implements Dictionary<DictionaryImp>, Comparable<DictionaryImp> { 

、どのように私はこれらの次のメソッドを実装するだろうか？どのインスタンス変数がDictionaryImpクラスによって運ばれますか？

public boolean isEmpty(); 
public boolean contains(E item); 
public boolean hasPredecessor(E item); 
// etc. 

Answer 1

私は赤黒木の実装を知らないが、基本的にすべてのあなたの言及した方法は赤黒木のメソッドを対応する呼び出します。

のisEmpty：ツリーが空であるかどうかを確認

は、（E項目）が含まれます要素を見つけるために、木の上でバイナリ検索を実行します。見つかった場合はtrueを返します。

add（E item）：if（！contains（item））tree.add（item）;

など。

Answer 2

あなたが持っているクラス宣言はあまり意味がありません。 Dictionaryのタイプパラメータは、辞書の要素タイプのようです。彼らが要素を自分自身に匹敵するように要求した理由です。あなたの宣言は、DictionaryImpが意味を持たないDictionaryImpの要素を持つ辞書だと言われています。あなたが望むものはDictionaryImpであり、その要素タイプはそれ自体に匹敵し、同じ型パラメータを持つ辞書を以下のように実装しています：