time-complexity - 区间树的时间复杂度分析

Question

我目前正在学习的区间树对于每个节点都有以下数据结构：

• key: 所有区间端点的中位数
• left, right: 指向左右子树
• intervals：包含区间的区间列表key。

可以在此链接中找到更准确的信息。

我了解到使用区间树进行查询的时间复杂度为 O(logn + k)，其中 n 是区间数，k 是报告结果的数量。

我不太明白这logn部分。假设v为区间树中的当前节点，Q为查询区间。该算法将是这样的：

if v.key is in Q,
  add v.intervals into results
  search_on_left_subtree
  search_on_right_subtree
else if Q.right < key,
  add some intervals
  search_on_left_subtree
else
  add some intervals
  search_on_right_subtree

似乎首先if我们可能需要进入两个子树。那么是不是最坏的情况下我们可能不得不遍历所有的树节点，使得时间复杂度为 O(n + k)？

Answer 1

它来自一个观察，如果你有一个长度为 n 的区间，那么我们可以将它分成 k 个段，其中 k <= log2(n) （二进制系统证明了这一点）

所以我们需要访问最坏的 log2(n) 个节点：时间复杂度是对数的。