3.2.20

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

解答

勘误:英文版为 keys() 方法(而非 Size() 方法)。

先来观察一下 keys() 方法的实现:

public IEnumerable<TKey> Keys(TKey lo, TKey hi)
{
    var queue = new Queue<TKey>();
    Keys(root, queue, lo, hi);
    return queue;
}

private void Keys(Node x, Queue<TKey> queue, TKey lo, TKey hi)
{
    var cmplo = lo.CompareTo(x.Key);
    var cmphi = hi.CompareTo(x.Key);
    if (cmplo < 0)
        Keys(x.Left, queue, lo, hi);
    if (cmplo <= 0 && cmphi >= 0)
        queue.Enqueue(x.Key);
    if (cmphi > 0)
        Keys(x.Right, queue, lo, hi);
}

简单地说,就是从根结点同时向两侧查找,同时把中间的键加入到队列中(树高的倍数+范围内键的数量)。

于是 Keys() 的耗时可以分成两部分:
寻找小于 lo 的最大键值和大于 hi 的最小键值在最坏情况下需要的访问结点数——即树高。
(例如当 lo 小于树中的最小键或者 hi 大于树中最大键时)
以及访问 lohi 之间所有结点。

上一题 下一题