二叉搜索树与特殊操作

Question

3

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

我对大于给定数字x且为3的倍数的元素数量感兴趣。此外，我还对在两个给定数字x1，x2之间严格为3的倍数的元素数量感兴趣，其中x1 < x2。

朴素的方法是例如搜索数字x，然后检查每个数字是否为3的倍数。是否有一种方法可以修改二叉搜索树，使这两个操作更有效？

- eafier

它是否总是3的倍数？那么在插入元素时可以过滤它们。 - Nico Schertler

在这种情况下，我只对3的倍数感兴趣。但是过滤不是我的选择，因为也许我以后想对树进行其他操作。 - Anna Saabel

1

你可以始终保持两棵树——一棵完整的树，另一棵只有3的倍数。这取决于你真正想做什么。 - Nico Schertler

x < x1 < x2成立吗？如果是，那么您只需要关心x1和x2。 - nice_dev

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Matt Timmermans · Accepted Answer

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

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

然后，要计算大于x的3的倍数的数量，您搜索x。每当您向左移动到一个节点（因为它> x），您将从该节点添加计数，并从移动到的节点中减去计数。

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