3.2.14

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

解答

minmaxselect 而言,它们是尾递归的,可以直接转换成迭代形式。
(简单的说,尾递归就是所有递归操作都出现在 return 语句上,且返回值不需要参与其他运算)

例如 min,递归形式为:

if (x.Left == null)
    return x;
return Min(x.Left); 

递归调用获得的值直接返回,不再参与运算,可以直接转换为递推:

while (true)
{
    if (x.Left == null) return x;
    x = x.Left;
}

ceilingfloor 会略微复杂一些,具体见代码。

代码

minmax 比较简单,用一个 while 循环就可以转换为递推形式,例如 min

while (x != null)
{
    if (x.Left == null) return x;
    x = x.Left;
}

return x;

floorceiling 则要稍微复杂一点,需要记录当前找到的最小/最大值,例如 floor

Node floor = null;
while (x != null)
{
    var cmp = key.CompareTo(x.Key);
    if (cmp == 0)
    {
        return x;
    }

    if (cmp < 0)
    {
        x = x.Left;
    }
    else
    {
        floor = x;
        x = x.Right;
    }
}

return floor;

rank 和它们类似,需要用一个变量记录当前排名。

var rank = 0;
while (x != null)
{
    var cmp = key.CompareTo(x.Key);
    if (cmp < 0)
    {
        x = x.Left;
    }
    else if (cmp > 0)
    {
        rank += 1 + Size(x.Left);
        x = x.Right;
    }
    else
    {
        rank += Size(x.Left);
        return rank;
    }

}

return rank;

select 比较简单,不需要维护变量。

while (x != null)
{
    var t = Size(x.Left);
    if (t > k)
    {
        x = x.Left;
    }
    else if (t < k)
    {
        x = x.Right;
        k = k - t - 1;
    }
    else
    {
        return x;
    }
}

return null;

另请参阅

尾递归-维基百科

BinarySearchTree 库

上一题 下一题