1

TreeMap（MyTreeMapと呼ばれる）の実装に取り​​組んでいますが、putメソッドで多くの問題が発生しています。私は誰かが私のコードを見て、物事がどこでうまくいかないかについて正しい方向に私を向けることができることを望んでいました。

public class MyTreeMap<K extends Comparable<? super K>,V> extends AbstractMap<K,V>  {

K key;
V value;
int height;
MyTreeMap<K,V> left,right;
int size;

public V put(K key, V value) {

    int compareValue = this.key.compareTo(key);

    if(!this.containsKey(key)) {
        if(this.key == null) {
            this.key = key;
            this.value = value;
        }

        if(this.isLeaf() || this.isEmpty()) {
            if(this.key.compareTo(key) > 0)
                this.left = new MyTreeMap<K,V>(key,value,null,null);
            else
                this.right = new MyTreeMap<K,V>(key,value,null,null);

            if(left.height > right.height + 1 || right.height > left.height + 1)
                restructure(this);
            this.size++;
            setHeight();
            return null;
        }
        else {
            if(compareValue > 0)
                return this.left.put(key, value);
            else
                return this.right.put(key, value);
        }
    }

    else {
        if(compareValue == 0) {
            V temp = this.value;
            this.value = value;
            return temp;
        }

        else if(compareValue < 0)
            return this.right.put(key, value);
        else 
            return this.left.put(key, value);
        }
}
4

1 に答える 1

0

あなたのロジックは少し裏返しになっていると思います。その結果、必要以上に複雑になっています。トップレベルifはおそらくチェックcompareValueを行うのではなく、を見る必要があります。containsKey

ロジックは次のようになります。

  • その場合compareValue==0、これは正しいキーが見つかったことを意味するので、値を更新して
  • それ以外の場合は、必要に応じて左または右のブランチを確認します（compareValueの符号に応じて）。
    • ブランチがnullの場合は、キーと値を含む新しいTreeMapブランチに変換します（これで完了です）
    • それ以外の場合（ブランチはnullではありません）、このブランチで再帰的にputを呼び出します。必要に応じて、この呼び出しの後にリバランスロジックを実行できます。

PS TreeMapでnullキーを許可しないことをお勧めします。これにより、作業が簡単になり、キーに対してnullチェックを実行する必要がなくなります。

于 2012-11-03T07:11:46.043 に答える