使用nextInOrder迭代avl树的时间复杂度

Question

假设我们有一个二进制AVL-tree，每个节点都有一个指向父节点的指针。

我们还有一个名为treeSuccesor的函数，它提供下一项inorder。我们可以假设它的时间复杂度是O(log(N))。

从最低值开始，到最高值结束，用它来遍历树的时间复杂度是多少？

对于给定的AVL-tree，使用treeSuccesor函数从17的节点迭代到85的节点的时间复杂度是多少？

​

迭代算法：

while (L != L2) // L2 is the ending node, 85 in the image
{
   L = treeSuccesor(L);
}

Answer 1

遍历任何二叉树都可以在time O(n)中完成，因为每个链接都会传递两次:一次向下，一次向上。对于每个节点，工作是恒定的。

复杂度不是O(n log n)，因为即使在AVL树的最坏情况下寻找下一个节点的工作是O(log n)的(对于一般的二叉树，它甚至是O(n))，树中所有节点的平均工作是恒定的。