algorithm - 计算 AVL 树算法的时间复杂度

Question

---

我正在计算以下算法的时间复杂度。我有一个 AVL 树和一对两个数字 (x,y) 这样 x<y .该算法的目的是打印树中 x 和 y 之间的所有数字。x 和 y 肯定不在树中。

我的目标是制作一个运行时间为 O(logn + k) 的算法，其中 k 是 x 和 y 之间的节点数，n 是树中节点的总数。

我的算法是这样的:

一个接收 x 和 y 的函数，从树的根开始，如下所示:

如果当前节点在 x 和 y 之间 - 打印它并递归调用左节点(x，当前节点值)和右节点(当前节点值，y)。

如果当前节点小于 x - 用 (x,y) 递归调用正确的节点

如果当前节点大于 y - 用 (x,y) 递归调用左节点该函数在到达叶子(没有其他节点附加到它的节点)时停止。我的函数是否满足运行时要求？

Answer 1

是的。您可以通过注意到您的算法除了访问节点之外什么都不做，并且每次访问节点都需要 O(1) 时间来证明这一点。发现范围内值的每次访问都可以“计费”到时限的 O(k) 部分。

但是有一些访问 - 那些找到小于或大于范围的节点 - 没有发现值。这些必须“计费”到时限的 O(log n) 部分。

剩下的证明就是证明确实不超过O(log n)次这样的访问。关键是要证明在从根开始的每个深度最多可以有一个常数 c。这需要对 BST 的结构进行一些推理。我会让你享受解决细节的乐趣。有 O(log n) 深度，所以这些访问的次数是 O(c log n) = O(log n)。 qed

补充说明

您的算法不必要地打乱了值。很容易调整，以便按排序顺序发现值。我将再次让您了解详细信息。