具有特殊操作的二进制搜索树

问题描述 投票:3回答:1

假设我们在整数上有正常的二叉搜索树。

我感兴趣的是3的倍数和大于给定数字x的元素数量。此外,我感兴趣的是3的倍数元素的数量,严格地在两个给定的数字x1,x2和x1 <x2之间。天真的方法是例如搜索数字x,然后检查每个数字是否是3的倍数。有没有办法修改二进制搜索树,这样这两个操作更有效率

algorithm binary-tree binary-search-tree
1个回答
1
投票

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

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

然后计算大于x的3的倍数,搜索x。无论何时离开某个节点(因为它> x),您都要从该节点添加计数,并从您移动到的节点中减去计数。

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

© www.soinside.com 2019 - 2024. All rights reserved.