3.2.28

上次更新:2019-10-08
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

修改一下 PutGet 方法,在实际操作之前先检查缓存是否符合要求,然后在操作之后更新缓存。

代码

private Node _cache;

public override TValue Get(TKey key)
{
    if (_cache != null && _cache.Key.CompareTo(key) == 0)
    {
        return _cache.Value;
    }

    return Get(root, key).Value;
}

protected override Node Get(Node x, TKey key)
{
    if (key == null)
    {
        throw new ArgumentNullException("calls get() with a null key");
    }

    if (x == null)
    {
        return null;
    }
    var cmp = key.CompareTo(x.Key);
    if (cmp < 0)
    {
        return Get(x.Left, key);
    }
    else if (cmp > 0)
    {
        return Get(x.Right, key);
    }
    else
    {
        _cache = x;
        return x;
    }
}

public override void Put(TKey key, TValue value)
{
    if (key == null)
    {
        throw new ArgumentNullException("calls Put() with a null key");
    }

    if (value == null)
    {
        Delete(key);
        return;
    }

    if (_cache != null && _cache.Key.CompareTo(key) == 0)
    {
        _cache.Value = value;
        return;
    }
    root = Put(root, key, value);
}

protected override Node Put(Node x, TKey key, TValue value)
{
    if (x == null)
    {
        _cache = new Node(key, value, 1);
        return _cache;
    }
    var cmp = key.CompareTo(x.Key);
    if (cmp < 0)
        x.Left = Put(x.Left, key, value);
    else if (cmp > 0)
        x.Right = Put(x.Right, key, value);
    else
        x.Value = value;
    x.Size = 1 + Size(x.Left) + Size(x.Right);
    return x;
}

另请参阅

BinarySearchTree 库

上一题 下一题