Assume the following notation/operations on AVL trees. An empty AVL tree is denoted E. A non-empty AVL tree T has three attributes:
• The key T.key is the root node’s key.
• The left child T.left is T’s left subtree, which is an AVL tree (possibly E).
• The right child T.right is T’s right subtree, which is an AVL tree (possibly E).
我正在尝试编写一个算法(伪代码会做)Count(T, lo, hi) 计算并返回根为 T 的 AVL 树中的节点数，其中键值在 lo ≤ 范围内关键≤喜。我希望它具有时间复杂度 O(n)，其中 n 是 AVL 树 T 中的节点数。我的一个想法是递归，但这似乎没有所需的复杂性。有什么想法吗？
最佳答案
你可以添加一个全局变量，比如counter，用Pre-order迭代树这有 (n+e) 的成本，每个节点加 1。
你也可以添加一个计数器，在数据结构中添加一个新节点时，你可以加1，如果你删除一个节点，你可以减1
关于计算 AVL 树中节点数的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56266956/