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 的符号）：
    • 如果分支为空，则将其转换为包含您的键和值的新 TreeMap 分支（您现在完成了）
    • 否则（分支不为空），在这个分支上递归调用 put 。如果您愿意，可以在此调用之后执行重新平衡逻辑。

PS 我建议不要在 TreeMap 中允许空键，它会让你的生活更简单，并且避免需要对键进行空检查

于 2012-11-03T07:11:46.043 回答