它必须通过索引和键快速查找.它还应该有一个快速“追加”操作(在最后插入一个新项目),以及快速删除任何索引(基于索引或键)的项目.
如果我没有弄错的话,.NET中的OrderedDictionary使用哈希表和数组来存储它的项目.因此,基于键重新获取索引(反之亦然)是O(n),当然从数组中间删除项目的是O(n)开头,加上从中添加的索引查找如果按键删除键.
我的问题是,是否存在满足我条件的更有效的数据结构,或者这确实是我最好的选择？
我认为你可以使用两个红黑树来实现这一点：一个用于存储由比较函数排序的键的键查找树,以及一个索引查找树,其中的键具有任意排序,如列表中所示.每个索引查找节点必须具有“大小”字段 – 如果每个节点中包含“大小”字段,则红黑树可以通过索引进行查找.例如,参见 C5 Generic Collection Library中的RedBlackTreeSet实现.密钥查找树中的每个条目都需要一个指针,指向索引查找树中的相应条目.除了左节点和右节点指针之外,索引查找树还需要一个父指针字段来允许底部到 – 顶部导航以及从顶部到底部.
总的来说,每个键需要六个指针：两个节点中通常的左右指针,加上从键查找节点到索引查找节点的指针,以及每个索引查找中的父指针-nodes.您还需要在每个节点中指针指向存储的值.
操作：
追加 – 追加操作会将密钥插入到两个树中 – 一次在密钥查找树中,在由比较函数确定的位置,并再次在索引查找树的最右边位置.插入红黑树是对数时间操作.
按键查找 – 这是在键查找树上完成的,使用compare函数查找正确的位置 – 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)重新哈希惩罚,就像任何哈希表一样.