计算 AVL 树中节点数的算法

Question

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 中的节点数。我的一个想法是递归，但这似乎没有所需的复杂性。有什么想法吗？

Answer 1

你可以添加一个全局变量，比如counter，用Pre-order迭代树这有 (n+e) 的成本，每个节点加 1。

你也可以添加一个计数器，在数据结构中添加一个新节点时，你可以加1，如果你删除一个节点，你可以减1