javascript - BST 的空间复杂度是多少？

Question

function validateBst(root, min=-Infinity, max=Infinity) { 
  if (!root) return true;
  if (root.value <= min || root.value > max) return false;
  return validateBst(root.left, min, root.value) && validateBst(root.right,root.value, max)
}  

谁能帮我解释一下...这个函数的空间复杂度是 O(log(n)) 还是 O(d) - 其中 d 是 BST 树的深度？

...我可以将它们归类为同一事物吗？

Answer 1

树本身的空间复杂度与树中的节点数成正比。因此，O(N)

validateBst 函数的空间复杂度是分配给递归搜索整个树的最大“堆栈”内存量(函数调用开销)。

堆栈的最大数量本质上是树从根节点到最下方的叶节点的高度。 在一般情况下(和最好的情况下) - 假设一棵树相当平衡，那么高度大约是 log₂ N。因此，空间复杂度将是 O(log₂ N) 或简单地 O(lg N) 在最坏情况的情况下，树只是一个排序的链表向右分支并增加值，然后是 O(N) 作为最坏的情况。