algorithm - 设计小型可比对象

Question

简介

假设您有一个键/值对列表:

(0,a) (1,b) (2,c)

你有一个函数，它在两个当前对之间插入一个新值，你需要给它一个保持顺序的键:

(0,a) (0.5,z) (1,b) (2,c)

这里选择新键作为边界对键的平均值之间的平均值。

问题是，您列出的可能有数百万个插入内容。如果这些插入都彼此靠近，您最终可能会得到诸如 2^(-1000000) 之类的键，这些键在任何标准或特殊数字类中都不容易存储。

问题

如何设计一个生成 key 的系统:

• 与所有其他键相比，给出正确的结果(大于/小于)。
• 仅占用 O(logn) 内存(其中 n 是列表中的项目数)。

我的尝试

• 首先，我尝试了不同的数字类别。就像分数甚至多项式一样，但我总能找到 key 大小随插入次数线性增长的示例。
• 然后我考虑保存指向许多其他键的指针，并保存小于/大于关系，但这总是至少需要 O(sqrt) 内存和时间进行比较。

额外信息:理想情况下，当从列表中删除对时，算法不应中断。

Answer 1

我同意雪王的观点。在这种情况下，一棵树是理想的。红黑树可以防止事情变得不平衡。但是，如果您真的需要键，我敢肯定，最好的办法就是在需要插入的值的两边使用键的平均值。这将使您的 key 长度每次增加 1 位。我推荐的是定期重新规范化 key 。每个 x 插入，或者每当您检测到生成的 key 靠得太近时，将所有内容从 1 重新编号到 n。

编辑:如果您按位置而不是键插入，则不需要比较键。红黑树的比较函数将只使用概念列表中的顺序，它与树中的顺序对齐。如果您要插入列表中的位置 4，请在树中的位置 4 插入一个节点(使用排序)。如果您在某个节点(例如“a”)之后插入，则相同。如果您使用的任何语言/库需要 key ，您可能必须使用自己的实现。