假设在AVL树上有以下符号/操作空的avl树表示为e.a
非空AVL树T有三个属性：
•key t.key是根节点的key。
•左子t.left是t的左子树，它是avl树（可能是e）。
•右边的子T.right是T的右边子树，它是AVL树（可能是E）。
我正在尝试编写一个算法（伪代码可以做到）count（t，lo，hi），它计算并返回根为t的avl树中的节点数，其中键值在lo≤key≤hi的范围内。我希望它具有时间复杂度O（n），其中n是AVL树T中节点的数目。我有一个想法是递归，但这似乎不具有所需的复杂性。有什么想法吗？
最佳答案
您可以添加一个全局变量，比如counter，用Pre-order遍历树，代价是（n+e），并为每个节点添加1。
也可以添加计数器，当在数据结构中添加新节点时，可以添加1，如果删除节点，则可以减去1
关于algorithm - 计算AVL树中节点数的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/56266956/