algorithm - 排行榜的高效数据结构，即记录列表(名称、积分) - 高效搜索(名称)、搜索(排名)和更新(积分)

Question

请提出一个数据结构来表示内存中的记录列表。每条记录由以下部分组成:

• 用户名
• 积分
• 排名(基于积分)- 可选字段- 可以存储在记录中或可以动态计算

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

1. Insert(record) - 可能会改变现有记录的排名
2. 删除(记录)- 可能会改变现有记录的排名
3. GetRecord(name) - 可能哈希表就可以了。
4. 获取记录(排名)
5. Update(points) - 可能会改变现有记录的排名

我的主要问题是 GetRecord(rank) 的高效实现，因为排名会经常变化。

我想内存中的 DBMS 会是一个很好的解决方案，但请不要推荐它；请提出一个数据结构。

Answer 1

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

1. 用户名
2. 分值
3. 排名
4. 指向名称树中引用该对象的节点的指针
5. 指向点树中引用对象的节点的指针。

只有在添加新记录和删除记​​录时才会修改名称树。点树针对插入和删除进行了修改，但也针对更新进行了修改，在找到适当记录的地方，删除了点树指针，更新了点计数，然后将新指针添加到点树。

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

---

点树将是 order statistic tree 的一些变体，它不是特定的数据结构，而是二叉搜索树的总称，其操作被修改以保持不变性，这使得请求的与排名相关的操作比遍历树更有效。如何维护不变量的细节取决于所使用的底层平衡搜索树(红黑树、avl 树等)。