添加到SortedSet< T>及其复杂性 [英] Add to SortedSet<T> and its complexity

问题描述

MSDN声明以下 SortedSet(T).添加方法:

如果Count小于内部数组的容量，则此方法为O(1)操作.

If Count is less than the capacity of the internal array, this method is an O(1) operation.

有人可以解释如何"吗?我的意思是，当添加新值时，我们需要找到一个正确的位置来添加一个值(将它与另一个值进行比较)，并且内部实现看起来像是插入复杂度为O(log N)的红黑树".

Could someone please explain "how so"? I mean when adding new value we need to find a correct place to add a value (comparing it with another values) and internal implementation looks like a "Red-Black tree" with O (log N) insertion complexity.

推荐答案

注释完全是错误的.是的，它是一棵红黑树，用于插入的O(log(n)).看看Reflector可以证明这一点，私有的AddIfNotPresent()方法包含一个while()循环，可以使用正常的红黑节点遍历来查找插入点.

The comment is simply wrong. Yes, it is a red-black tree, O(log(n)) for inserts. Taking a look with Reflector bears this out, the private AddIfNotPresent() method contains a while() loop to find the insertion point, using normal red-black node traversal.

此文档错误已经 由您知道的人提交.

This doc bug has already been submitted by you-know-who.

这篇关于添加到SortedSet< T>及其复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！