数据结构来保持数

请提出一个数据结构来维护这样的方式，我可以回答下面的查询号码 -数据结构来保持数

查找（INT N） - （的log（n））

计数Ø小于K = O（日志（n））的

插入数数 - O（日志（n））的

这不是功课，而是我遇到解决一个更大的一个小问题 - Number of students with better grades and lower jee rank

我虽然有一棵avl树，每个节点在子树上都有维护节点数。但是当插入完成并重新平衡完成时，我不知道如何在每个节点维护此计数。

2011-11-08 Nitin Garg

闻到家庭作业......你到目前为止想过什么？ – m0skit0

@ m0skit0查看已编辑的问题。 –

我也会尝试使用AVL树。没有深入研究，我认为这不会太难补充。在AVL树的情况下，总是需要知道每个节点的每个子树的深度（或者至少是平衡因子）。因此，传播子树的大小不应该太难。在轮换的情况下，你知道每个节点和每个子树都会在哪里着陆，所以它应该只是简单地重新计算那些被旋转的节点。

2011-11-08 09:23:59 LiKao

在二叉树中查找O（log（n）），也插入。如果存储在节点的子树的大小：

因此，子树大小就像一个find，O（log（n））。

2011-11-08 08:51:37

这些操作仅在平衡二叉搜索树中记录（n）。以及如何在我的问题中更新其中的相关节点。 –

@NitinGarg：无论何时，当有人提到一棵二叉树时，它们最有可能是一棵平衡的树。在节点上进行任何操作时，节点上的额外数量信息只是维护不变式的问题 – hugomg

-1

查看堆数据结构的不同变体，例如， here。

2011-11-08 09:05:42 jmg

堆只适用于查找最大值/最小值元素。 – hugomg

堆也很适合找到n个最小的数字。 OP要求“计数小于k的数字”。我明白他对小于k的元素数目感兴趣。通过重复采用最小的元素或通过检查堆数据结构可以解决这个问题。 – jmg

回答