假设在AVL树上有以下表示法/操作。空的AVL树表示为E。非空的AVL树T具有三个属性：
•密钥T.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
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句