排行榜的高效数据结构,即记录列表(名称,点) - 高效搜索(名称),搜索(排名)和更新(点)

Question

请建议一个表示记录列表的数据结构memory.每条记录由以下内容组成:

• 用户名
• 点
• 秩(基于点) - 可选字段 - 可以存储在记录中,也可以动态计算

数据结构应该有效地支持以下操作的实现:

1. 插入(记录) - 可能会改变现有记录的等级
2. 删除(记录) - 可能会更改现有记录的等级
3. GetRecord(名称) - 可能是一个哈希表.
4. GetRecord(秩)
5. 更新(点数) - 可能会更改现有记录的排名

我的主要问题是GetRecord(rank)的有效实现,因为排名可以经常变化.

我猜内存DBMS是一个很好的解决方案,但请不要建议; 请建议一个数据结构.

Answer 1

基本上,你只需要一对平衡的搜索树,它将允许O(lg n)插入,删除和getRecord操作.诀窍是,不是将实际数据存储在树中,而是存储指向一组记录对象的指针,其中每个记录对象将包含5个字段:

1. 用户名
2. 点值
3. 秩
4. 指针返回引用该对象的名称树中的节点
5. 指针返回引用该对象的点树中的节点.

只有在添加新记录和删除记​​录时才会修改名称树.点树被修改用于插入和删除,但也用于更新,其中找到适当的记录,删除其点树指针,更新其点数,然后将新指针添加到点树.

如您所愿,如果您愿意,可以使用哈希表代替名称树.这里的关键是你只需将单独的排序索引维护成一组其他无序记录,这些记录本身包含指向其索引节点的指针.

点树将是订单统计树的一些变体,它不是特定的数据结构,而是二元搜索树的总称,其操作被修改以维持不变量,这使得所请求的与秩相关的操作比走树.不变量如何维护的细节取决于使用的底层平衡搜索树(红黑树,avl树等).