3.1.16

3.1.16 #

解答 #

官方实现：https://algs4.cs.princeton.edu/31elementary/BinarySearchST.java.html

先通过二分查找获得下标，然后后面的元素依次向前移动一位。

public void Delete(TKey key)
{
    if (key == null)
        throw new ArgumentNullException(nameof(key), "argument to Delete() is null");
    if (IsEmpty())
        return;

    var i = Rank(key);

    if (i == _n && _keys[i].CompareTo(key) != 0)
        return;

    for (var j = i; j < _n - 1; j++)
    {
        _keys[j] = _keys[j + 1];
        _values[j] = _values[j + 1];
    }

    _n--;
    _keys[_n] = default;
    _values[_n] = default;

    if (_n > 0 && _n == _keys.Length / 4)
        Resize(_keys.Length / 2);

    Debug.Assert(Check());
}

另请参阅 #

SymbolTable 库