通过密钥和索引进行有效操作和检索的数据结构

Question

我正在寻找具有例如功能的数据结构.在OrderedDictionary.NET中,也就是关联集合(即一个相关联的密钥与值)维护元素的顺序(就像一个正常的List一样).

它必须通过索引和键快速查找.它还应该有一个快速"追加"操作(在最后插入一个新项目),以及快速删除任何索引(基于索引或键)的项目.

在OrderedDictionary.NET中同时使用哈希表和一个数组来存储它的项目,如果我没有记错.因此,基于键重新获取索引(反之亦然)是O(n),当然从数组中间删除项目的是O(n)开头,加上从中添加的索引查找如果按键删除键.

我的问题是,是否存在满足我条件的更有效的数据结构,或者这确实是我最好的选择？

Answer 1

我认为你可以用两棵红黑树来做到这一点：一个键查找树用于存储按比较函数排序的键，另一个是索引查找树，其中键按任意顺序排列，就像在列表中一样。每个索引查找节点必须有一个“大小”字段 - 如果每个节点中都包含“大小”字段，则红黑树可以通过索引进行查找。例如，请参阅C5 通用集合库中的 RedBlackTreeSet 实现。

键查找树中的每个条目都需要一个指向索引查找树中相应条目的指针。除了左节点和右节点指针外，索引查找树还需要一个父指针字段以允许从下到上- 顶部导航以及从上到下的导航。

总共，每个键需要六个指针：两个节点中通常的左指针和右指针，加上从键查找节点到索引查找节点的指针，加上每个索引查找节点中的父指针-节点。您还需要每个节点中都有一个指针来指向存储的值。

运营：

追加 - 追加操作会将键插入到两棵树中 - 一次插入键查找树中由比较函数确定的位置，然后再次插入索引查找树的最右侧位置。插入红黑树是一个对数时间操作。

按键查找 - 这是在键查找树上完成的，使用比较函数找到正确的位置 - O(log(n))

按索引查找 - 这可以在索引查找字段上完成，如上所述 - O(log(n))

从键获取索引 - 首先在键查找树中查找键 O(log(n))。跟随指针到达索引查找树。沿着父指针向上到达根节点（平衡树的 O(log(n))）。使用向上的“大小”字段来确定键的索引。- 总体 O(log(n))。

按索引删除 - 在索引查找树中查找项目。从索引查找树中删除。在键查找树中查找找到的键。从键查找树中删除。所有操作都是 O(log(n)) ，因此删除总体上是 O(log(n)) 。

按键删除 - 使用“从键获取索引”来获取键的索引。从索引查找树中按索引删除。从键查找树中按键删除。总体而言，O(log(n))。

该结构还支持在任意位置插入 O(log(n))，而不仅仅是在末尾。

存储开销显然相当大，但仍然是 O(n)。时间复杂度满足所有要求。

不幸的是我不知道这个结构的任何实现。

更新：我觉得你可以将树与哈希表结合起来以获得 O(1) 按键查找。正如我上面建议的那样，不要使用两棵树，而是使用哈希表进行按键查找，使用平衡顺序统计树进行按位置查找，如上所述，但哈希表的槽包含指向用于执行按键获取列表位置查找的平衡树的节点。按键查找现在为 O(1)，其他所有内容平均保持为 O(ln(n))。当然，与任何哈希表一样，您现在偶尔会受到 O(n) 重新哈希惩罚。