2

我正在寻找一种具有高效插入、删除和查找的数据结构，二叉树通常符合条件，但是我的项目不是根据它们的值排序的——而是我需要根据它们的实际插入位置对它们进行排序（即像一个数组）。所有操作都将基于此位置访问、插入或删除项目，就像使用数组一样。

  • getItem(int 位置)
  • addItem(int insertPosition, 对象项)
  • removeItem(int 位置)

所以基本上问题是插入/删除一个项目会导致它之后的所有项目的索引移动 1。显然存储索引永远不会产生比 O(n) 更好的结果，所以基本的二叉树/哈希表已经不存在了。

是否有一种结构能够在亚线性时间内实现所有这些操作？我一直认为可以以某种方式调整二叉树，并且我会通过让每个节点存储其左分支中的节点数来支持按索引查找。

4

2 回答 2

0

2-3 用索引注释的手指树应该能够做到这一点。它们是持久的（在函数式编程意义上），这可能是好是坏。如果你非常想要一个可变的变体，它至少是一个想法的来源。2-3 手指树支持

  1. 对数时间访问，以及
  2. 在摊销的常数时间内在开始和结束时添加和删除，以及
  3. 在较小部分的大小上按时间对数拆分和连接。

因此，要在任意位置插入，您可以在该位置拆分，添加到其中一个部分的末尾，然后连接。同样，要删除一个项目，您可以在该索引处拆分，删除该项目，然后再次连接。两者都花费少于 O(log n) 的时间，这是一个过度近似。

Data.SequenceHaskell中的模块是现有的实现（针对索引注释的特殊情况，并针对性能进行了调整） 。介绍它们的论文比它需要的更难阅读。有一篇文章更清楚地解释了总体思路，但省略了许多细节，因此不足以实现它们。

于 2013-05-30T16:54:17.530 回答
-1

List 支持这些功能，如果容量 > 计数，则添加的时间为 O(1)

List.Add 方法

其他一切都是 O(N) 但实际上更好。
如果你在位置 0 插入，那么它是 O(N)，但如果你在倒数第二个位置插入，你会发现它比 O(N) 更好。

    List<simple> ls = new List<simple>();
    simple ss = new simple(0);
    ls.Add(ss);
    ls.Add(new simple(2));
    ls.Insert(0, new simple(1));
    ls.Add(new simple(3));
    ls.Add(new simple(4));
    ls.RemoveAt(2);
    foreach(simple s in ls) 
    {
        System.Diagnostics.Debug.WriteLine(s.ID);
    }
    System.Diagnostics.Debug.WriteLine(ls[1].ID.ToString());
    System.Diagnostics.Debug.WriteLine(ls.IndexOf(ss).ToString());
}
public class simple
{
    public Int32 ID { get; private set; }
    public simple(Int32 id) { ID = id; }
}
于 2013-05-30T16:38:09.070 回答