有限双射的有效功能数据结构

Question

我正在寻找一种功能数据结构,它代表两种类型之间的有限双射,即节省空间和节省时间.

例如,考虑到大小为n的双射f,我会很高兴:

• 用一对新元素扩展f具有复杂度O(ln n)
• 查询f(x)或f ^ -1(x)具有复杂度O(ln n)
• f的内部表示比具有2个有限映射(表示f及其逆)更节省空间

我知道排列的有效表示,就像本文一样,但似乎并没有解决我的问题.

Answer 1

请看一下我相对类似问题的答案.该提供的代码可以处理一般的N×M的关系,也可以专门只双射(就像你对一个二叉搜索树).

为了完整性,在这里粘贴答案:

最简单的方法是使用一对单向映射.它有一些成本,但你不会变得更好(你可以使用专用二叉树更好一点,但如果你必须自己实现它,你需要支付巨大的复杂成本).从本质上讲,查找速度一样快,但添加和删除速度会慢一倍.这对于对数操作来说并不是那么糟糕.此技术的另一个优点是,如果有可用的键,则可以使用专用的地图类型作为键或值类型.使用特定的通用数据结构不会获得足够的灵活性.

另一种解决方案是使用四叉树(而不是将NxN关系视为一对1xN和Nx1关系,您将其视为类型的笛卡尔积(Key*Value)中的一组元素,即空间飞机),但我不清楚时间和内存成本比两张地图好.我想它需要进行测试.

Answer 2

虽然它不能满足你的第三个要求,但bimap似乎是要走的路.(他们只制作两个有限的地图,每个方向一个,方便使用.)