计算AVL树中某个范围内的节点数

Question

有没有办法找到平衡二叉搜索树中两个给定节点之间的节点数（仅计数），使用它们在< O（log n）时间的等级？

我们可以假设我们已经将每个Node的rank（或height）动态地存储为Node类的成员变量。所以，我们可以直接访问它。

Answer 1

是的，使用lowest common ancestor查询可以计算在不同时间之间的节点。它需要线性时间对树进行一次预处理。

如果您知道两个节点的最低公共祖先的等级，则可以通过从子节点的等级中减去祖先的等级来计算节点和祖先之间有多少个节点。

nodes_between = a.rank + b.rank - 2*(lowest_common_ancestor(a, b).rank) + 1 

上面将返回节点a和b包括两个端点之间的路径的长度。 + 1是为最低的共同祖先本身。寻找lowest_common_ancestor可以在恒定的时间内完成，计算是恒定的时间。