二叉搜索树中 Java 方法的成本

Question

我们有 Java 方法 rangeQuery_count(BSTNode,int,int)。给定一个 BST 的根（keys int）和一个区间 [a,b]，这个方法 returns 个 BST 的 keys 属于这个区间。

static int rangeQuery_count(BSTNode v, int a, int b) { //a<=b
   if(v==null) return 0;
   if(v.key < a) return rangeQuery_count(v.right, a, b);
   else if(v.key > b) return rangeQuery_count(v.left, a, b);
   else return 1 + rangeQuery_count(v.right, a, b) + rangeQuery_count(v.left, a, b);
}

我必须根据 BST 的节点数 n 来确定算法成本的渐近估计。我刚刚开始研究这些主题，我想了解如何计算程序的成本。

Answer 1

首先要认识到成本取决于输入参数的特定值，例如，在您的情况下，它取决于搜索树中有多少节点落在区间内。这里所做的通常简化假设是计算最坏的可能情况。在这种情况下，这将是树中的所有节点都位于区间内时。在那种情况下，只要 v 不为空，您将始终采用 else 的最后一个子句，您将访问树的每个节点一次，如果树中有 n 个节点，则成本将大致与 n 线性上升。

二叉搜索树中 Java 方法的成本

Cost of a Java method in a binary-search-tree

java

algorithm

binary-search-tree