中序遍历两次递归调用自己，AVL树怎么会有O(log n)的复杂度？这不是 O(2^n) 吗？

Question

我有一个保存播放器对象的 AVL 树。每个玩家都有一个名字和一个等级。树节点根据玩家等级排序。我首先遍历树深度并将每个节点附加到按排名排序的玩家列表（按降序排列，因此从右到左遍历）。

我读到的所有内容都告诉我，AVL 树的复杂度为 O(log n)，但是当我查看我的中序遍历函数时，我注意到它递归调用自身两次，我认为这会使它成为 O (2^n)。有没有更有效的方法来遍历我不知道的树？还是我的大 O 计算有误？

def traverseRightToLeft(node, array = []):
# Base case
if node is None:
    return
# Recursively check if there are any right child nodes, append the current node data to the list then recursively check if there are any left child nodes
else:
    traverseRightToLeft(node.right, array)
    array.append(node.data)
    traverseRightToLeft(node.left, array)
return array

Answer 1

定义 n 作为树中的节点数。

Search、Insert 和 Erase 等操作是 O(log n) AVL树。

遍历一棵树是O(n)，不管是AVL树还是B-Tree还是红黑树，因为你在每个节点只递归一次（父节点的调用或对根的初始调用）。

Answer 2

你的错误在于“递归调用自己两次使得算法复杂度为 O(2^n)”。这不是真的。该算法在其大小的一半上递归调用自身。

假设我想数 n 个块。我可以数出 n 块。或者我可以将它们分成大致相等的两组，然后数左边，然后数右边，然后将它们相加。如果左侧或右侧太大，我可以递归地将其中一个（或两个）分成两半，并分别计算大约四分之一。但我仍然只计算每个元素一次。

中序遍历两次递归调用自己，AVL树怎么会有O(log n)的复杂度？这不是 O(2^n) 吗？

How can an AVL tree have a complexity of O(log n) when the in-order traversal calls itself recursively twice? Doesn't that make it O(2^n)?

python

big-o

time-complexity