二叉搜索树验证的空间复杂度 [英] Space complexity of validation of a binary search tree

问题描述

以下给出了验证二叉树是否为BST的最佳算法

The best algorithm to verify if a binary tree is a BST is given as follows

IsValidBST(root,-infinity,infinity);

bool IsValidBST(BinaryNode node, int MIN, int MAX) 
{
    if(node == null)
        return true;
    if(node.element > MIN 
        && node.element < MAX
        && IsValidBST(node.left,MIN,node.element)
        && IsValidBST(node.right,node.element,MAX))
        return true;
    else 
        return false;
}

此逻辑的空间复杂度显然是 O（ logN），我假设这是递归的费用。值是如何得出的？

The space complexity of this logic is apparently O(logN) which I'm assuming is the cost of recursion. How was the value arrived at?

推荐答案

我的评论已升级为答案：

My comment upgraded to answer:

除了方法变量和返回值外，没有使用其他数据，因此，实际上，所有内存都是递归成本。因此，总成本将与树的深度成线性比例。

There is no additional data used other than the method variables and the return value, so indeed, all memory is "cost of recursion". The total cost would hence be linearly proportional to the depth of the tree.

在平衡二叉搜索树中，深度为 O（log n） ，因此的确，空间复杂度也将为 O（log n）。但是，通常BST不一定是平衡的，它甚至可以是长度为n的链，如果根是最小，其右子元素是第二个最小元素，依此类推。在这种情况下，此递归的空间复杂度为 O（n）。

In a balanced binary search tree, the depth is O(log n), so indeed, the space complexity would be O(log n) too. However, in general a BST is not necessarily balanced, it could even be a chain of length n, if the root is the minimum, its right child is the second smallest element, and so on. In that case the space complexity of this recursion is O(n).

这篇关于二叉搜索树验证的空间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！