计算 AVL 树中给定范围内的节点数
Count number of nodes within given range in AVL tree
假设我有一个 distinct 整数的 AVL 树。我需要确定位于区间 [a, b) 中的节点数，其中 a < b。请注意，[a, b) 是由用户提供的，因此我事先不知道 a 和 b 的值是多少。此外，树中可能根本不存在 a 和 b。例如，如果我有一棵包含整数 {1, 2, 4, 5, 6, 7} 的树，那么如果用户提供区间 [3, 7)，则他应该期望答案为 3。
一个天真的实现是遍历每个节点，并在给定间隔内每次找到节点时将计数递增 1。但这将具有 O(n) 的最坏情况时间复杂度，因为树中的每个整数都可能在给定范围内。我需要一个更快的算法，在做了一些研究后我发现它需要在每个节点中存储一个大小统计信息，以便可以轻松计算任何给定节点的排名。
我想做类似 rank(b) - rank(a) 的事情，但问题是树中可能不存在 a 和 b。在上面的示例中，rank(7) 会 return 6 但 rank(3) 不会 return 任何有意义的值。
任何人都可以提供有关如何解决此问题的建议吗？另外，我知道这个网站上还有另一个类似的问题，但是那个涉及C++，而这个涉及Java。另外，我在那里找不到满意的答案。
而不是
rank(b) - rank(a)
我会做的是
rank(X) - rank(Y)
X 是第一个值 > b 的节点。
Y 是第一个值 >= a 的节点。
很久以前，我已经为 AVL 树实现了一个基于堆栈的树迭代器。它应该像这样适合你的情况：
- 创建一个数组 "treestack" 来保存遍历信息的结构。该结构只需要一个 bool "visited" 和一个指向您的节点类型的指针。该数组可以是静态大小，例如持有 64 个信息元素（一个用于树的每个级别，所以这 64 个将意味着你的树包含最大 4G 节点）
- 更改您的 AVL 树的搜索方法，在开始搜索时将根节点放在 treestack[0]，并在搜索过程中跟随左右子节点时将所有其他节点放在 treestack 的顶部您的搜索。编辑：请注意，不成功的搜索将导致您的 treestack 具有一个具有下一个更小或下一个更高值的节点，这正是您想要的（如果它更小，请跳过计数，我们仍然有无效的迭代器启动誓言）。
您现在已经有了一条 treestack 路径，您可以使用它进行后续的有序遍历以找到下一个更高的值。使用栈的中序遍历是这样的：
- 从 treestack 中的最后一个元素开始，保留一个树索引，它最初是最后一个项目的数组索引。
- 当有一个右节点，并且没有标记为已访问时：尝试跟随当前节点右侧的ONE，然后是任何后续节点左侧的ENDLESS。无论你在哪里停下来（如果没有左节点只有一个右节点也是如此）是下一个更高的值。当您跟随它们时，将所有节点放在树堆栈的末尾，并在您跟随路径时包含您的树索引。并将选择的具有下一个更高值的最终节点标记为已访问。增加你的节点计数器+1.
- 现在要找到后续更高的值，通过将您的树堆栈中的 treeindex-1 作为当前节点在树中上升，重复上述步骤以找到下一个具有更高值的节点。
- 如果当前节点没有右子节点，且该节点未标记为已访问：标记为已访问，节点计数器加1
- 当您到达树索引为 0 的根节点或您的节点包含最大值时，您就完成了。
希望对您有所帮助。
假设我有一个 distinct 整数的 AVL 树。我需要确定位于区间 [a, b) 中的节点数，其中 a < b。请注意，[a, b) 是由用户提供的，因此我事先不知道 a 和 b 的值是多少。此外，树中可能根本不存在 a 和 b。例如，如果我有一棵包含整数 {1, 2, 4, 5, 6, 7} 的树，那么如果用户提供区间 [3, 7)，则他应该期望答案为 3。
一个天真的实现是遍历每个节点，并在给定间隔内每次找到节点时将计数递增 1。但这将具有 O(n) 的最坏情况时间复杂度，因为树中的每个整数都可能在给定范围内。我需要一个更快的算法，在做了一些研究后我发现它需要在每个节点中存储一个大小统计信息，以便可以轻松计算任何给定节点的排名。
我想做类似 rank(b) - rank(a) 的事情，但问题是树中可能不存在 a 和 b。在上面的示例中，rank(7) 会 return 6 但 rank(3) 不会 return 任何有意义的值。
任何人都可以提供有关如何解决此问题的建议吗？另外，我知道这个网站上还有另一个类似的问题，但是那个涉及C++，而这个涉及Java。另外，我在那里找不到满意的答案。
而不是
rank(b) - rank(a)
我会做的是
rank(X) - rank(Y)
X 是第一个值 > b 的节点。
Y 是第一个值 >= a 的节点。
很久以前，我已经为 AVL 树实现了一个基于堆栈的树迭代器。它应该像这样适合你的情况：
- 创建一个数组 "treestack" 来保存遍历信息的结构。该结构只需要一个 bool "visited" 和一个指向您的节点类型的指针。该数组可以是静态大小，例如持有 64 个信息元素（一个用于树的每个级别，所以这 64 个将意味着你的树包含最大 4G 节点）
- 更改您的 AVL 树的搜索方法，在开始搜索时将根节点放在 treestack[0]，并在搜索过程中跟随左右子节点时将所有其他节点放在 treestack 的顶部您的搜索。编辑：请注意，不成功的搜索将导致您的 treestack 具有一个具有下一个更小或下一个更高值的节点，这正是您想要的（如果它更小，请跳过计数，我们仍然有无效的迭代器启动誓言）。
您现在已经有了一条 treestack 路径，您可以使用它进行后续的有序遍历以找到下一个更高的值。使用栈的中序遍历是这样的：
- 从 treestack 中的最后一个元素开始，保留一个树索引，它最初是最后一个项目的数组索引。
- 当有一个右节点，并且没有标记为已访问时：尝试跟随当前节点右侧的ONE，然后是任何后续节点左侧的ENDLESS。无论你在哪里停下来（如果没有左节点只有一个右节点也是如此）是下一个更高的值。当您跟随它们时，将所有节点放在树堆栈的末尾，并在您跟随路径时包含您的树索引。并将选择的具有下一个更高值的最终节点标记为已访问。增加你的节点计数器+1.
- 现在要找到后续更高的值，通过将您的树堆栈中的 treeindex-1 作为当前节点在树中上升，重复上述步骤以找到下一个具有更高值的节点。
- 如果当前节点没有右子节点，且该节点未标记为已访问：标记为已访问，节点计数器加1
- 当您到达树索引为 0 的根节点或您的节点包含最大值时，您就完成了。
希望对您有所帮助。