java - 统计AVL Tree中一定范围内的节点数

Question

有没有办法使用它们在 < O(log n) 时间内的秩来查找平衡二叉搜索树中 2 个给定节点之间的节点数（仅计数）？

我们可以假设我们已经将每个节点的等级（或高度）动态地存储为节点类的成员变量。所以，我们可以直接访问它。

Answer 1

是的，使用最低公共祖先查询可以在恒定时间内计算其间的节点。它需要在线性时间内对树进行一次预处理。

如果您知道两个节点的最低共同祖先的排名，那么您可以通过从子节点的排名中减去祖先的排名来计算一个节点和祖先之间有多少个节点。

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

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