3.2.21

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

解答

要注意保持每个键的出现概率相等,可以先随机一个排名,然后从树中将对应排名的键取出来。

private static readonly Random Random = new Random();

public TKey RandomKey()
{
    var rank = Random.Next(1, Size() + 1);
    return GetKeyWithRank(root, rank);
}

private TKey GetKeyWithRank(Node x, int rank)
{
    var left = (x.Left == null ? 0 : x.Left.Size) + 1;
    if (left > rank)
    {
        return GetKeyWithRank(x.Left, rank);
    }
    else if (left == rank)
    {
        return x.Key;
    }
    else
    {
        return GetKeyWithRank(x.Right, rank - left);
    }
}

可以观察到每个键的出现概率都是差不多的。

另请参阅

BinarySearchTree 库

上一题 下一题