当索引遍历递归调用自身两次时，AVL树的复杂度如何达到O（logn）？这不就是O（2^n）吗？

Question

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

我读到的所有东西都告诉我，AVL树的复杂度为O（logn），但当我查看顺序遍历函数时，我注意到它递归调用自己两次，我认为这会使它成为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定义为树中的节点数

像搜索、插入和擦除这样的操作在AVL树中O(log n)

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

Answer 2

您的错误是“递归调用自己两次会使算法为O（2^n）”。事实并非如此。该算法递归地调用其自身大小的一半

想象一下，我想数n个街区。我可以数n个街区。或者我可以将它们分成两个大致相等的集合，然后计算左侧，然后计算右侧，再将它们相加。如果左侧或右侧太大，我可以递归地将其中一个（或两个）分成两半，然后分别计算大约四分之一。但我仍然只计算了一次每个元素