如何从SortedDictionary中获取与我的密钥最近的项目？

Question

目前，我对SortedList<T,U>使用的是一个特定数字的二进制搜索，如果它不存在，我会得到最接近的下界绑定键。

我看到它在inserting unsorted data中很慢，我正在做很多。

有没有办法与SortedDictionary做类似的事情，还是应该坚持我的SortedList？

Answer 1

SortedList<K, V>当插入数据时非常慢，因为每次添加新元素时都会在内部数组中移动<=N元素。加法的复杂性是O(N)。不过，它支持二进制搜索，它允许在O(log N)中找到确切的元素或其邻居。

平衡二叉树是解决您的问题的最佳数据结构。 你就可以做以下操作W /对数的复杂性：

1. 添加项O(log N)与O(N)在SortedList<K, V>
2. 删除项O(log N)
3. 搜索项目或与其最接近的O(log N)

在二叉树中寻找元素或其最接近的下界很简单：

1. 垂直穿过从根到树的树，以便找到您的密钥。如果键<节点，那么去左边的孩子，否则到正确的一个。
2. 如果你找到了钥匙，返回
3. 如果没有找到关键的，最左侧的父母将是你正在寻找一个（最近的下限）
4. 如果没有左父母，只取最后访问节点，它是树中最小的节点。

有很多文章描述如何实现二叉树。尽管如此，我打算重新使用.NET框架集合使用一种破解:)

现在，我要提出SortedSet<T>它本身是红黑树。它有一个缺点，它无法快速找到最近的节点。但是我们知道树中的搜索算法（在1中描述），它在SortedSet<T>.Contains方法中实现（在底部*处反编译）。现在，我们可以使用我们的自定义比较器在遍历期间捕获从根节点到最后访问节点的所有节点。之后，我们可以使用上面的算法查找最近下界节点：

public class LowerBoundSortedSet<T> : SortedSet<T> { 

    private ComparerDecorator<T> _comparerDecorator; 

    private class ComparerDecorator<T> : IComparer<T> { 

     private IComparer<T> _comparer; 

     public T LowerBound { get; private set; } 

     private bool _reset = true; 

     public void Reset() 
     { 
      _reset = true; 
     } 

     public ComparerDecorator(IComparer<T> comparer) 
     { 
      _comparer = comparer; 
     } 

     public int Compare(T x, T y) 
     { 
      int num = _comparer.Compare(x, y); 
      if (_reset) 
      { 
       LowerBound = y; 
      } 
      if (num >= 0) 
      { 
       LowerBound = y; 
       _reset = false; 
      } 
      return num; 
     } 
    } 

    public LowerBoundSortedSet() 
     : this(Comparer<T>.Default) {} 

    public LowerBoundSortedSet(IComparer<T> comparer) 
     : base(new ComparerDecorator<T>(comparer)) { 
     _comparerDecorator = (ComparerDecorator<T>)this.Comparer; 
    } 

    public T FindLowerBound(T key) 
    { 
     _comparerDecorator.Reset(); 
     this.Contains<T>(key); 
     return _comparerDecorator.LowerBound; 
    } 
} 

你看，找到最近的节点时间可能比平常的搜索没有更多的，即O(log N)。所以，这是解决您的问题的最快解决方案。此集合的搜索速度最快为SortedList<K, V>，并且与SortedSet<T>一样快。

SortedDictionary<K, V>怎么样？它几乎与SortedSet<T>相同，除了一件事情：每个键都有一个值。我希望你能用SortedDictionary<K, V>做同样的事情。

*反编译的方法SortedSet<T>.Contains：

public virtual bool Contains(T item) 
{ 
    return this.FindNode(item) != null; 
} 

internal virtual SortedSet<T>.Node FindNode(T item) 
{ 
    for (SortedSet<T>.Node node = this.root; node != null; { 
    int num; 
    node = num < 0 ? node.Left : node.Right; 
    } 
) 
    { 
    num = this.comparer.Compare(item, node.Item); 
    if (num == 0) 
     return node; 
    } 
    return (SortedSet<T>.Node) null; 
}