c - 在 BST 中查找 sum=0 的三元组 - 使用以下代码的时间复杂度

Question

我编写了以下代码，用于在 BST 中查找加起来为 0 的三元组。但是很难确定时间复杂度。

find() 方法的时间复杂度为 O(logn)。 isTriplet() 的时间复杂度是 O(n^2) 吗？

bool find(Node* root, int target) {
  if (root == NULL)
      return false;

  if (root->data == target)
      return true;

  return (target < root->data) ?  find(root->left, target) :  find(root->right, target);
}

bool isTriplet(Node* root, Node* actualRoot) {
  if (root == NULL)
     return false;

  if (root->left == NULL && root->right == NULL)
      return false;

  int sum = root->data;
  if (root->left)
      sum += root->left->data;
  else if (root->right)
      sum += root->right->data;

  sum = -1 * sum;

  return (find(actualRoot, sum) || isTriplet(root->left, actualRoot) || isTriplet(root->right, actualRoot));
}

Answer 1

sum = 0 的三元组表示一个节点、一个左子节点和一个右子节点，三个元素之和等于 0。

让我们逻辑思考一下。我们应该从树的根部开始在哪里搜索这样的三元组？基本上，如果根是正数，则向左，如果根是负数，则向右。

我们什么时候应该检查是否找到了这样的三元组？三个数中至少有一个负数且至少有一个正数的情况。 0是特殊情况，我会单独处理。

如果找到这样的总和，那么我们应该返回它并停止算法。因此，如果节点不为 0 并且没有三元组，那么我们就知道要在哪个子树中搜索。如果它是三元组，那么我们就有一个简单的情况，因为找到了解决方案。如果当前节点是0，那么我们应该检查它的三元组是否为0。如果不是，那么我们可以停止搜索，因为没有子树将包含正数和负数。当然，异常(exception)情况是当前节点为 0 并且其子节点之一也为 0。在这种情况下，我们还需要检查该子树。

对于最坏的情况，算法的复杂度应以 2 为底。证明:

1. 当找到这样的三元组时，算法应该停止。

2. 如果尚未找到这样的三元组且当前节点不为 0，则我们有一个有趣的子树和一个不有趣的子树。

3. 如果尚未找到这样的三元组且当前节点为 0，则:

3.1。它的两个 child 都是0，我们找到了这样一个三元组，

3.2。它的子节点都不为 0，因此可以证明不存在这样的三元组，或者

3.3。它的一个 child 是 0，但另一个不是，在这种情况下，0 child 定义有趣的子树，另一个 child 定义不感兴趣的子树。

由于所有情况要么由于解决方案的存在或不存在而轻微地停止算法，要么将树分成感兴趣和不感兴趣的子树，所以该算法在每个级别上遍历单个节点最多，因此其复杂性在最坏的情况下等于树的高度，它是二进制对数。