algorithm - 具有特殊操作的二叉搜索树

Question

假设我们有一个普通的整数二叉搜索树。

我对 3 的倍数且大于给定数字 x 的元素数量感兴趣。此外，我对元素的数量感兴趣，这些元素是 3 的倍数并且严格介于两个给定数字 x1、x2 之间且 x1 < x2。天真的方法是例如搜索数字 x 然后检查每个数字是否是 3 的倍数。有没有办法修改二叉搜索树，使这两个操作更有效

Answer 1

在每个节点中，您可以保留该节点的子树中 3 的倍数的计数。

可以在不改变添加/删除/旋转/重新平衡操作的复杂性的情况下维护这些计数。

然后要计算大于 x 的 3 的倍数的个数，您搜索 x。每当您在一个节点向左(因为它 > x)时，您都会添加该节点的计数，并减去您移动到的节点的计数。

如果您在内部节点中找到 x，请从其右子节点中添加计数。