3.2.20

3.2.20 #

解答 #

勘误：英文版为 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 大于树中最大键时）

以及访问 lo 和 hi 之间所有结点。