3.2.21 #
解答 #
要注意保持每个键的出现概率相等，可以先随机一个排名，然后从树中将对应排名的键取出来。
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);
}
}
可以观察到每个键的出现概率都是差不多的。
