设计小比较的对象

考虑你有键/值对的列表：

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

你有一个功能，即插入两个电流对之间的新的价值，你需要给它一个保持顺序的密钥：

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

这里新密钥被选为边界对的密钥平均值之间的平均值。

问题是，你列出的可能有数以百万计的插入。如果这些插页全部彼此贴近，则最终可能会出现2^(-1000000)等密钥，这些密码在任何标准和特殊号码类别中都不容易储存。

问题

你怎么能设计一个系统，用于生成密钥：

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

我尝试

首先我尝试了不同数量的类别。就像分数甚至polynomium一样，但我始终可以找到示例，其中密钥大小与插入次数成线性关系。
然后我想到了保存指向其他许多按键的指针，并保存了低于/高于关系，但这总是需要至少O(sqrt)的内存和时间进行比较。

其他信息：理想情况下，当从列表中删除配对时，算法不应该中断。

来源

2010-06-06 Thomas Ahle

也许你应该用树代替？ – 2010-06-06 18:38:07

你期望得到O（log n）内存 - 每个关键值或整组关键值？ – 2010-06-06 18:49:24

@snowlord实际上，键/值对存储在树中。但是对于我解决的任务，我需要能够插入树中的特定位置。 @HPM每个键 – 2010-06-07 02:51:10

我同意snowlord。在这种情况下，树将是理想的。一棵红黑色的树可以防止东西变得不平衡。但是，如果你真的需要密钥，我敢肯定，你无法比使用需要插入的值的任何一边的平均密钥做得更好。这会使您的密钥长度每次增加1位。我推荐的是定期重新规范化密钥。每插入一个x，或者每当您检测到密钥过于靠近时，都会将所有内容从1重新编号为n。

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

来源

2010-06-06 18:47:50

错误...如何？谨慎解释？什么是用于插入红黑树的比较函数？ – 2010-06-06 19:07:30

@Moron：如果您想了解更多关于红黑树的信息，可以在wikipedia上阅读，但有一句有趣的引语是'它可以在O（log n）时间内搜索，插入和删除“。红黑树：http://en.wikipedia.org/wiki/Red-black_tree – 2010-06-06 19:21:59

@snowlord！我知道什么是红黑树。关键是，对于使用红黑树，你需要有一个已经定义的比较函数，它可以比较任何两个给定的元素，以决定在插入一个新元素时树的哪个分支。似乎你心中有完全不同的东西。 -1直到你编辑你的帖子，说明你打算如何使用红黑树。哦，对不起，这不是龙人的答案，但仍然是投票的立场。 – 2010-06-06 19:33:48

我不认为你可以避免在操作过程中不用重新分配密钥就可以获得大小为O（n）的密钥。

作为一种实用的解决方案，我将构建一个倒排搜索树，从孩子到父母的指针，每个指针标记是来自左侧还是右侧的孩子。为了比较两个元素，你需要找到最接近的共同祖先，其中元素的路径分歧。

重新分配键然后重新平衡树，你可以做一些不改变顺序的旋转。

来源

2010-06-06 20:29:55 starblue

啊对了。密钥实际上是为了在重新平衡的情况下锁定订单而设计的。也许相反，我应该专注于更智能的轮换方案。 – 2010-06-07 03:16:14

设计小比较的对象

回答

相关问题